回溯算法四例

1、第三章 回溯算法四例第一节 回溯方法在程序设计中,有很多问题是无法运用某种公式推导或采用循环的方法求解的.例 如,完成某一件事需要经过若干步骤，而每一步又都有若干种可能的方案供选择.显 示完成这整个事件就有许许多多方法。问题是要在其中找出满足题目条件的一种或 多种方法。这类问题一般只能借助搜索与回溯算法求解。 回溯法的基本思想是：“试探着走”。如果试的不成功退回一步，再换一个办 法试试。反复进行这种试探性选择与返回纠错过程，直到求出问题的解为止。 回溯算法比前面介绍的其它方法复杂, 但它是程序设计中最重要的基础算法之一。【主要思想】回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题

2、的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。【算法框架】1、问题的解空间：应用回溯法解问题时，首先应明确定义问题的解空间。问题的解空间应到少包含问

3、题的一个（最优）解。2、回溯法的基本思想：确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。换句话说，这个结点不再是一个活结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。【回溯步骤】 （1）针对所给

4、问题，定义问题的解空间； （2）确定易于搜索的解空间结构； （3）以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索； 3、递归回溯：由于回溯法是对解空间的深度优先搜索，因此在一般情况下可用递归函数来实现回溯法如下：PROCEDURE TRY(I:INTEGER);VARBEGINIF I>N THEN 输出结果ELSE FOR J:=下界 TO 上界 DOBEGINXI:=HJ;IF 可行满足限界函数和约束条件 THEN BEGIN 置值；TRY(I+1); END;END;END; 说明：I是递归深度； N是深度控制，即解空间树的的高度；可行性判断有两方面的内容：不满

5、约束条件则剪去相应子树；若限界函数越界，也剪去相应子树；两者均满足则进入下一层；第二节 例题分析例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,X

6、2,Y2(分别表示马的起点坐标,终点坐标)【输出文件】与输入对应，有多组输出，每组仅有一行，一个数，路径数目(若不存在从起点到终点的路径,输出0)【输入样例】10 101 5 3 5【输出样例】2【算法分析】1、马从A点出发，根据上面两条马走的规则，有4种走法，但是那条路径才能到达B点呢，无法得到答案，只能任意选择其中的一种走法。2、当马到达下一个顶点后又有4种走法，由于无法知道走那条路，所以还是要先选择任意一个点，一直到最后，如果没有到达终点的点，那么要返回一步，走第二种走法，一直到所有的走法走完。上面就是一个简单的回溯过程，核心思想有两条：（1） 在无法知道走那条路的时候，只能任选区一条路

7、试试看。（2） 当从某点出发，所有可能的路径都不能达到目标时，说明到达此点是错误的，必须回到上一个点，然后重新选择另一个点来进行。【程序清单】略.例2【问题描述】马的遍历问题。在的棋盘中，马只能走日字。马从位置(X,Y)处出发，把棋盘的每一格都走一次，且只走一次。找出所有路径。【算法分析】骑士在棋盘中某一点可以移动到下一步的点有8个（当然有些边上和角上的位置没有那么多选择，不过如果将棋盘延伸看来它们还是可以选8个方向，只不过有些位置超出了棋盘。）。骑士每次移动会先判断下一点是否可以移动根据一个事先安排好的顺序（可以是顺时针或者逆时针或者其他更能优化算法的顺序）看下一个点是否可以走到，如果可以走

8、到就将骑士移动到那一点，然后走下一步；有可能这个点已经超出了棋盘边界或者已经走过一次了，那就对下一个点进行判断；如果所有的8个选择点都不可行，则骑士回退一步，从当前位置之前一个点继续。【程序设计】棋盘大小：INT CHESSBOARD88骑士所处位置：CAVX,CAVY骑士走过的路径记录：CAVPATH652为了使用1-64步更直观，我将该数组定义为65，同样的CAVPATHI0代表水平方向的坐标值，CAVPATHI1代表垂直方向。骑士在每一点可以尝试移动的方向：INT MOVENEXT = 2,1,1,2,-1,2,-2,1,-2,-1,-1,-2,1,-2,2,-1; 每一个点可以尝试向8

9、个方向移动，MOVENEXTI0代表移动方向在水平方向的移动，MOVENEXTI1代表在垂直方向的移动。骑士在每一个点上已经尝试移动过的方向个数：CAVDIRECT65跟着骑士移动的步伐记录每个移动点上尝试了多少方向，当骑士回退时，会知道它在这个点上已经尝试过多少点是不可移动到的。骑士已经走过的点的个数CAVNUM骑士的出发点：CAVX,CAVY的初始值1、骑士的移动：判断骑士是否可以移动到下一点，记录尝试过的点；如果可以移动则移动骑士当前的坐标；2、修改棋盘的状态，做骑士的路径记录，骑士移动的步数+1；3、棋盘抹去刚刚骑士走过的痕迹，抹去骑士这一步的路径记录，抹去骑士在这个点尝试点的记录，将

10、骑士当前的点还原到上一步；【程序清单】 深度优先搜索法 TYPEXTP=ARRAY1.8 OF INTEGER;ATP=ARRAY1.20,1.20 OF INTEGER;VARK,I,J,X,Y,N,H:INTEGER;DX,DY:XTP;A:ATP;PROCEDURE HORSE(VAR A:ATP;VAR H,N,X,Y,K:INTEGER);VAR M:INTEGER;BEGIN H:=1; REPEAT IF (X+DXH<=N) AND (Y+DYH<=N) AND (X+DXH>=1) AND (Y+DYH>=1) AND (A(X+DXH),(Y+DYH

11、)=0) THEN BEGIN K:=K+1;AX,Y:=K; IF K=N*N THEN FOR I:=1 TO N DO BEGIN FOR J:=1 TO N DO WRITE(AI,J:4); WRITELN; END; X:=X+DXH;Y:=Y+DYH; M:=H; HORSE(A,H,N,X,Y,K); K:=K-1; X:=X-DXM;Y:=Y-DYM; H:=M+1; AX,Y:=0; END ELSE H:=H+1; UNTIL H=8;END;BEGINFOR I:=1 TO 20 DO FOR J:=1 TO 20 DO AI,J:=0;DX1:=2;DY1:=1; D

12、X2:=1;DY2:=2;DX3:=-2;DY3:=1; DX4:=-1;DY4:=2;DX5:=2;DY5:=-1; DX6:=1;DY6:=-2;DX7:=-2;DY7:=-1; DX8:=-1;DY8:=-2;WRITE('INPUT THE POSITION:');READ(X,Y);WRITELN;WRITE('INPUT THE LARGE:');READ(N);H:=1;K:=0; HORSE(A,H,N,X,Y,K);END.例3【问题描述】求迷宫中一条从入口到出口的路径的算法【程序设计】设定当前位置的初值为入口位置:DO  

13、  若当前位置可通,    则 将当前位置插入堆栈顶;        若该位置是出口位置,则结束;        否则切换当前位置的东邻块为新的当前位置;          否则, 若堆栈不空且栈顶位置尚有其他方向未经探索;  则设定新的当前位置为沿顺时针方向转到的栈顶位置的下一相邻块; 若栈不空但

14、栈顶位置的四周均不可通,         则删去栈顶位置;     若栈不空,则重新测试新的栈顶位置,      直至找到一个可通的相邻或出栈至栈空;               【程序清单】本程序假设迷宫是一个4 X 4的矩阵，入口在A1，1，出口在A4，4矩阵数据放在文件中PROGRAM MIK

15、ONG;VAR  A,B,C:ARRAY1.4,1.4 OF INTEGER;  数组A用来存放迷宫路径，约定元素值为0表示通，1表示不通                                     

16、; 数组B用来存放方向增量                                       数组C用来记录结果，当第I步移到某一元素时，该元素就等于I  I,J,K,M,N:INTEGER;  FV

17、:TEXT;  Q:BOOLEAN;  用来标记迷宫是否有出路  PROCEDURE PRINT;  VAR     M,N:INTEGER;  BEGIN    Q:=TRUE;  如果打印步骤，表示肯定有出路    WRITELN;    WRITELN;    WRITELN('穿越迷宫的步骤是：');    FOR M:=1

18、 TO 4 DO      BEGIN              FOR N:=1 TO 4 DO          WRITE(CM,N:4);        WRITELN;      END 

19、END;  PROCEDURE TRY(X,Y,I:INTEGER);  VAR    U,V,K:INTEGER;  BEGIN    FOR K:=1 TO 4 DO   可以有4个方向选择      BEGIN        U:=X+BK,1;     当前坐标加上方向增量    

20、    V:=Y+BK,2;        IF (U>=1) AND (U<=4) AND (V>=1) AND (V<=4) THEN  判断是否越界          IF (AU,V=0) AND (CU,V=0) THEN    判断是否为0，为0就表示通，为1就表示不通     &#

21、160;      BEGIN              IF (X=2) AND (Y=3) THEN WRITELN('AAAAAAAAAAAA');              CU,V:=I;  数组 C打上记号，表示此元素是第I步到达  

22、;            IF (U<>4) OR (V<>4) THEN  判断是否到出口                  TRY(U,V,I+1)  没有就继续走         

23、       ELSE   PRINT;              CU,V:=0   下一路所有方向都不通，清除本次所做的标记            END      END  END; 

24、BEGIN  ASSIGN(FV,'SHUJU3.TXT');  RESET(FV);  FOR I:=1 TO 4 DO    BEGIN      FOR J:=1 TO 4 DO        READ(FV,AI,J);        READLN(FV)      END;

25、  B1,1:=-1;  B1,2:=0;  B2,1:=0;   B2,2:=1;  B3,1:=1;   B3,2:=0;  B4,1:=0;   B4,2:=-1;  CLOSE(FV);  FOR I:=1 TO 4 DO    首先标记数组C所有元素全部为0    FOR J:=1 TO 4 DO CI,J:=0;  C1,1:=1;  FOR I:=1 TO 4 DO

26、0; 显示迷宫具体线路，0表示通，1表示不通    BEGIN      FOR J:=1 TO 4 DO        WRITE(AI,J:4);        WRITELN      END;  Q:=FALSE;  假设迷宫没有出路  TRY(1,1,2); IF Q=FALSE

27、 THEN WRITELN( '此迷宫没有出路')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 

28、60;1  0   0   0   0   输出:TOTAL=3 表示可以称出1G,2G,3G三种不同的重量【算法分析】本题采用全组合的算法，用D1   D2   D3   D4   D5   D6分别代表每种砝码的个数。例如：D1=3  D2=4   D3=

29、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，00依次取到D1，D2D6。2、 当给出某个取法后，如何计算出可称重量。3、 当知名人士重计算出以后，如何断定重复，以及如何计算总数。下面给出上面三个问题的回答：1、 为了能从1，0，00依次取到D1，D2D6，可引入一个数组B:ARRAY1.6OF INTEGER,初值为0，然后给出加1的算法，开始时设J:=1