回溯算法四例.docx
- 文档编号:3296986
- 上传时间:2023-05-05
- 格式:DOCX
- 页数:13
- 大小:26.22KB
回溯算法四例.docx
《回溯算法四例.docx》由会员分享,可在线阅读,更多相关《回溯算法四例.docx(13页珍藏版)》请在冰点文库上搜索。
回溯算法四例
第三章回溯算法四例
第一节回溯方法
在程序设计中,有很多问题是无法运用某种公式推导或采用循环的方法求解的.例如,完成某一件事需要经过若干步骤,而每一步又都有若干种可能的方案供选择.显示完成这整个事件就有许许多多方法。
问题是要在其中找出满足题目条件的一种或多种方法。
这类问题一般只能借助搜索与回溯算法求解。
回溯法的基本思想是:
“试探着走”。
如果试的不成功退回一步,再换一个办法试试。
反复进行这种试探性选择与返回纠错过程,直到求出问题的解为止。
回溯算法比前面介绍的其它方法复杂,但它是程序设计中最重要的基础算法之一。
【主要思想】回溯法是一个既带有系统性又带有跳跃性的的搜索算法。
它在包含问题的所有解的解空间树中,按照深度优先的策略,从根结点出发搜索解空间树。
算法搜索至解空间树的任一结点时,总是先判断该结点是否肯定不包含问题的解。
如果肯定不包含,则跳过对以该结点为根的子树的系统搜索,逐层向其祖先结点回溯。
否则,进入该子树,继续按深度优先的策略进行搜索。
回溯法在用来求问题的所有解时,要回溯到根,且根结点的所有子树都已被搜索遍才结束。
而回溯法在用来求问题的任一解时,只要搜索到问题的一个解就可以结束。
这种以深度优先的方式系统地搜索问题的解的算法称为回溯法,它适用于解一些组合数较大的问题。
【算法框架】
1、问题的解空间:
应用回溯法解问题时,首先应明确定义问题的解空间。
问题的解空间应到少包含问题的一个(最优)解。
2、回溯法的基本思想:
确定了解空间的组织结构后,回溯法就从开始结点(根结点)出发,以深度优先的方式搜索整个解空间。
这个开始结点就成为一个活结点,同时也成为当前的扩展结点。
在当前的扩展结点处,搜索向纵深方向移至一个新结点。
这个新结点就成为一个新的活结点,并成为当前扩展结点。
如果在当前的扩展结点处不能再向纵深方向移动,则当前扩展结点就成为死结点。
换句话说,这个结点不再是一个活结点。
此时,应往回移动(回溯)至最近的一个活结点处,并使这个活结点成为当前的扩展结点。
回溯法即以这种工作方式递归地在解空间中搜索,直至找到所要求的解或解空间中已没有活结点时为止。
【回溯步骤】
(1)针对所给问题,定义问题的解空间;
(2)确定易于搜索的解空间结构;
(3)以深度优先的方式搜索解空间,并且在搜索过程中用剪枝函数避免无效搜索;
3、递归回溯:
由于回溯法是对解空间的深度优先搜索,因此在一般情况下可用递归函数来实现回溯法如下:
PROCEDURETRY(I:
INTEGER);
VAR
BEGIN
IFI>NTHEN输出结果
ELSEFORJ:
=下界TO上界DO
BEGIN
X[I]:
=H[J];
IF可行{满足限界函数和约束条件}THENBEGIN置值;TRY(I+1);END;
END;
END;
说明:
I是递归深度;
N是深度控制,即解空间树的的高度;
可行性判断有两方面的内容:
不满约束条件则剪去相应子树;若限界函数越界,也剪去相应子树;两者均满足则进入下一层;
第二节例题分析
例1【问题描述】有一个N*M的棋盘(2<=N<=50,2<=M<=50),如下图,在棋盘上左下角有一个中国象棋马,
马走的规则为:
1.马走日字2.马只能向右走
即如下图所示:
当N,M给出之后,同时给出马起始的位置和终点的位置,试找出从起点到终点的所有路径的数目.
例如:
(N=10,M=10),(1,5)(起点),(3,5)(终点)
有2条路径,(即由(1,5)到(3,5)共有2条路径)
【输入文件】
有多组测试数据,每组格式如下:
第一行,两个数,N,M;
第二行,四个数,X1,Y1,X2,Y2(分别表示马的起点坐标,终点坐标)
【输出文件】
与输入对应,有多组输出,每组仅有一行,一个数,路径数目(若不存在从起点到终点的路径,输出0)
【输入样例】
1010
1535
【输出样例】
2
【算法分析】
1、马从A点出发,根据上面两条马走的规则,有4种走法,但是那条路径才能到达B点呢,无法得到答案,只能任意选择其中的一种走法。
2、当马到达下一个顶点后又有4种走法,由于无法知道走那条路,所以还是要先选择任意一个点,一直到最后,如果没有到达终点的点,那么要返回一步,走第二种走法,一直到所有的走法走完。
上面就是一个简单的回溯过程,核心思想有两条:
(1)在无法知道走那条路的时候,只能任选区一条路试试看。
(2)当从某点出发,所有可能的路径都不能达到目标时,说明到达此点是错误的,必须回到上一个点,然后重新选择另一个点来进行。
【程序清单】
略.
例2【问题描述】
马的遍历问题。
在N*M的棋盘中,马只能走日字。
马从位置(X,Y)处出发,把棋盘的每一格都走一次,且只走一次。
找出所有路径。
【算法分析】
骑士在棋盘中某一点可以移动到下一步的点有8个(当然有些边上和角上的位置没有那么多选择,不过如果将棋盘延伸看来它们还是可以选8个方向,只不过有些位置超出了棋盘。
)。
骑士每次移动会先判断下一点是否可以移动——根据一个事先安排好的顺序(可以是顺时针或者逆时针或者其他更能优化算法的顺序)看下一个点是否可以走到,如果可以走到就将骑士移动到那一点,然后走下一步;有可能这个点已经超出了棋盘边界或者已经走过一次了,那就对下一个点进行判断;如果所有的8个选择点都不可行,则骑士回退一步,从当前位置之前一个点继续。
【程序设计】棋盘大小:
INTCHESSBOARD[8][8]
骑士所处位置:
CAVX,CAVY
骑士走过的路径记录:
CAVPATH[65][2]
为了使用1-64步更直观,我将该数组定义为65,同样的CAVPATH[I][0]代表水平方向的坐标值,CAVPATH[I][1]代表垂直方向。
骑士在每一点可以尝试移动的方向:
INTMOVENEXT[][]={{2,1},{1,2},{-1,2},{-2,1},{-2,-1},{-1,-2},{1,-2},{2,-1}};
每一个点可以尝试向8个方向移动,MOVENEXT[I][0]代表移动方向在水平方向的移动,MOVENEXT[I][1]代表在垂直方向的移动。
骑士在每一个点上已经尝试移动过的方向个数:
CAVDIRECT[65]
跟着骑士移动的步伐记录每个移动点上尝试了多少方向,当骑士回退时,会知道它在这个点上已经尝试过多少点是不可移动到的。
骑士已经走过的点的个数
CAVNUM
骑士的出发点:
CAVX,CAVY的初始值
1、骑士的移动:
判断骑士是否可以移动到下一点,记录尝试过的点;如果可以移动则移动骑士当前的坐标;
2、修改棋盘的状态,做骑士的路径记录,骑士移动的步数+1;
3、棋盘抹去刚刚骑士走过的痕迹,抹去骑士这一步的路径记录,抹去骑士在这个点尝试点的记录,将骑士当前的点还原到上一步;
【程序清单】{深度优先搜索法}
TYPE
XTP=ARRAY[1..8]OFINTEGER;
ATP=ARRAY[1..20,1..20]OFINTEGER;
VAR
K,I,J,X,Y,N,H:
INTEGER;
DX,DY:
XTP;
A:
ATP;
PROCEDUREHORSE(VARA:
ATP;VARH,N,X,Y,K:
INTEGER);
VARM:
INTEGER;
BEGIN
H:
=1;
REPEAT
IF(X+DX[H]<=N)AND(Y+DY[H]<=N)AND(X+DX[H]>=1)AND(Y+DY[H]>=1)AND(A[(X+DX[H]),(Y+DY[H])]=0)THEN
BEGIN
K:
=K+1;A[X,Y]:
=K;
IFK=N*NTHEN
FORI:
=1TONDO
BEGIN
FORJ:
=1TONDO
WRITE(A[I,J]:
4);
WRITELN;
END;
X:
=X+DX[H];Y:
=Y+DY[H];
M:
=H;
HORSE(A,H,N,X,Y,K);
K:
=K-1;
X:
=X-DX[M];Y:
=Y-DY[M];
H:
=M+1;
A[X,Y]:
=0;
END
ELSEH:
=H+1;
UNTILH=8;
END;
BEGIN
FORI:
=1TO20DO
FORJ:
=1TO20DO
A[I,J]:
=0;
DX[1]:
=2;DY[1]:
=1;DX[2]:
=1;DY[2]:
=2;
DX[3]:
=-2;DY[3]:
=1;DX[4]:
=-1;DY[4]:
=2;
DX[5]:
=2;DY[5]:
=-1;DX[6]:
=1;DY[6]:
=-2;
DX[7]:
=-2;DY[7]:
=-1;DX[8]:
=-1;DY[8]:
=-2;
WRITE('INPUTTHEPOSITION:
');
READ(X,Y);WRITELN;
WRITE('INPUTTHELARGE:
');
READ(N);
H:
=1;K:
=0;HORSE(A,H,N,X,Y,K);
END.
例3【问题描述】
求迷宫中一条从入口到出口的路径的算法
【程序设计】
设定当前位置的初值为入口位置:
DO{
若当前位置可通,
则{将当前位置插入堆栈顶;
若该位置是出口位置,则结束;
否则切换当前位置的东邻块为新的当前位置;
}
否则,
若堆栈不空且栈顶位置尚有其他方向未经探索;
则设定新的当前位置为沿顺时针方向转到的栈顶位置的下一相邻块;
若栈不空但栈顶位置的四周均不可通,
则{删去栈顶位置;
若栈不空,则重新测试新的栈顶位置,
直至找到一个可通的相邻或出栈至栈空;
}
}
【程序清单】{本程序假设迷宫是一个4X4的矩阵,入口在A[1,1],出口在A[4,4]}
{矩阵数据放在文件中}
PROGRAMMIKONG;
VAR
A,B,C:
ARRAY[1..4,1..4]OFINTEGER; {数组A用来存放迷宫路径,约定元素值为0表示通,1表示不通}
{数组B用来存放方向增量}
{数组C用来记录结果,当第I步移到某一元素时,该元素就等于I}
I,J,K,M,N:
INTEGER;
FV:
TEXT;
Q:
BOOLEAN; {用来标记迷宫是否有出路}
PROCEDUREPRINT;
VAR
M,N:
INTEGER;
BEGIN
Q:
=TRUE; {如果打印步骤,表示肯定有出路}
WRITELN;
WRITELN;
WRITELN('穿越迷宫的步骤是:
');
FORM:
=1TO4DO
BEGIN
FORN:
=1TO4DO
WRITE(C[M,N]:
4);
WRITELN;
END
END;
PROCEDURETRY(X,Y,I:
INTEGER);
VAR
U,V,K:
INTEGER;
BEGIN
FORK:
=1TO4DO {可以有4个方向选择}
BEGIN
U:
=X+B[K,1]; {当前坐标加上方向增量}
V:
=Y+B[K,2];
IF(U>=1)AND(U<=4)AND(V>=1)AND(V<=4)THEN {判断是否越界}
IF(A[U,V]=0)AND(C[U,V]=0)THEN {判断是否为0,为0就表示通,为1就表示不通}
BEGIN
IF(X=2)AND(Y=3)THENWRITELN('AAAAAAAAAAAA');
C[U,V]:
=I; {数组C打上记号,表示此元素是第I步到达}
IF(U<>4)OR(V<>4)THEN {判断是否到出口}
TRY(U,V,I+1) {没有就继续走}
ELSE PRINT;
C[U,V]:
=0 {下一路所有方向都不通,清除本次所做的标记}
END
END
END;
BEGIN
ASSIGN(FV,'SHUJU3.TXT');
RESET(FV);
FORI:
=1TO4DO
BEGIN
FORJ:
=1TO4DO
READ(FV,A[I,J]);
READLN(FV)
END;
B[1,1]:
=-1; B[1,2]:
=0;
B[2,1]:
=0; B[2,2]:
=1;
B[3,1]:
=1; B[3,2]:
=0;
B[4,1]:
=0; B[4,2]:
=-1;
CLOSE(FV);
FORI:
=1TO4DO {首先标记数组C所有元素全部为0}
FORJ:
=1TO4DOC[I,J]:
=0;
C[1,1]:
=1;
FORI:
=1TO4DO {显示迷宫具体线路,0表示通,1表示不通}
BEGIN
FORJ:
=1TO4DO
WRITE(A[I,J]:
4);
WRITELN
END;
Q:
=FALSE; {假设迷宫没有出路}
TRY(1,1,2);
IFQ=FALSETHENWRITELN('此迷宫没有出路')
END.
例4【问题描述】砝码称重问题
设有1G,2G,3G,5G,10G,20G的砝码各若干枚(其总重<=1000G),要求:
输入方式:
A1 A2 A3 A4 A5 A6
(表示1G砝码有A1个,2G砝码有A2个,......20G砝码有A6个)
输出方式:
TOTAL=N
(N表示用这些砝码能称出的不同重量的个数,但不包括一个砝码也不用的情况)
如:
输入:
1 1 0 0 0 0
输出:
TOTAL=3表示可以称出1G,2G,3G三种不同的重量
【算法分析】
本题采用全组合的算法,用D1 D2 D3 D4 D5 D6分别代表每种砝码的个数。
例如:
D1=3 D2=4 D3=5 D4=0 D5=2 D6=7
开始时:
取1克砝码1个,可称1克重量,此时总数为1;
取1克砝码2个,可称2克重量,此时总数为2;
取1克砝码1个,可称1克重量,此时总数为3;
此时1克砝码已全部取完,再从2克砝码开始取:
取2克砝码1个,1克砝码0个,可称2克重量,由于前面已称出2克,因此总数不增加。
取2克砝码1个,1克砝码1个,可称3克重量,总数不增加。
取2克砝码1个,1克砝码2个,可称4克重量,总数为4。
取2克砝码1个,1克砝码1个,可称3克重量,总数为5。
……
用此方法直到全部取完,可得到称重:
D1+2D2+5D3+10D4+20D5+50D6
【程序设计】
在上面的算法过程中,必须解决下面的三个问题:
1、如何能从难从1,0,0…0依次取到D1,D2……D6。
2、当给出某个取法后,如何计算出可称重量。
3、当知名人士重计算出以后,如何断定重复,以及如何计算总数。
下面给出上面三个问题的回答:
1、为了能从1,0,0…0依次取到D1,D2……D6,可引入一个数组B:
ARRAY[1..6]OFINTEGER,初值为0,然后给出加1的算法,开始时设J:
=1;
WHILEB[J]=D[J]DOJ:
=J+1;
B[J]:
=B[J]+1;
FORI:
=1TOJ-1DOB[I]:
=0;
2、当砝码取出以后用公式W=B1+2B2+5B3+10B4+20B5+50B6
3、引入一个数组P:
ARRAY[1..1000]OF0..1;
当计算出一个W后,仅做P[W]:
=1,不必判重,这样最后的可称总数为:
P[1]+P[2]+……+P[W]
【程序清单】
PROGRAMCOUNTERWEIGHT;
TYPE
ATP=ARRAY[1..100]OFINTEGER;
ARR=ARRAY[1..30000]OFINTEGER;
VAR
A,B,D:
ATP;
C:
ARR;
TOTAL,MAX:
LONGINT;
I,N:
INTEGER;
PROCEDUREMAKE(K:
INTEGER);
VAR
I,J:
INTEGER;
BEGIN
IFK>=1THENBEGIN
FORI:
=0TOB[K]DO
BEGIN
D[K]:
=I;
MAKE(K-1);
END;
END
ELSE
BEGIN
TOTAL:
=0;
FORJ:
=1TONDO
TOTAL:
=TOTAL+A[J]*D[J];
C[TOTAL]:
=TOTAL;
END;
END;
BEGIN
MAX:
=0;TOTAL:
=0;
WRITELN('INPUTTHENUMBEROFTHECOUNTERWEIGHT:
');
READ(N);
WRITELN('INPUTTHEWEIGHTOFEACHCOUNTERWEIGHT:
');
FORI:
=1TONDO
READ(A[I]);
WRITELN('INPUTTHENUMBEROFEACHCOUNTERWEIGHT:
');
FORI:
=1TONDO
READ(B[I]);
FORI:
=1TONDO
MAX:
=MAX+A[I]*B[I];
FORI:
=1TOMAXDO
C[I]:
=0;
MAKE(N);
WRITELN('THEWEIGHTCANTHECOUNTERWEIGHTSWEIGHIS:
');
FORI:
=1TOMAXDO
BEGIN
IFC[I]=ITHENWRITE(I:
5);
IF(IMOD10=0)THENWRITELN;
END;
END.
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 回溯 算法
![提示](https://static.bingdoc.com/images/bang_tan.gif)