C语言回溯法.doc

授课教师：南京玄武区教师进修学校高建君 回 溯 算 法学习重点：1、 理解回溯法的基本思想；2、 掌握回溯法解题的基本算法。学习过程:一、回溯法的基本思想回溯法又称试探法。回溯法的基本做法是深度优先搜索，是一种组织得井井有条的、能避免不必要重复搜索的穷举式搜索算法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。具体说,就是：在搜索(依次用各种方法一一去试探)的过程中，当在P点有N种选择，则从第一种开始尝试，若第K种可行，即这一步搜索成功，打上标记，再向前(即 P+1点)搜索；如在P点搜索失败(所有的方法都试探过，没有一种可行)，为了摆脱当前的失败，就返回搜索进程中的上一点(即P-1点)，再用第K+1种方法(假设上次在P-1点用第K种方法搜索成功，必须明确以前用过的方法不能再用，否则会陷入死循环)再去搜索，重新寻求解答。这样搜索回溯，再搜索再回溯，如能搜索到终点，问题有解，如最后回溯到出发点，问题就无解。 这种在搜索的过程中，先对深度大的点进行扩展的算法，叫深度优先搜索法。 设搜索深度指针为P，搜索方法指针为I，可把深度优先搜索算法写成如下形式： P=0：I=0 DO I=I+1(搜索到一种方法) IF 搜索方法有效 THEN 试探产生临时新结点 IF 符合条件 THEN P=P+1(深入一步)，新结点记录，I=0，再全方位搜索 IF到达终点 THEN 结束搜索，输出结果 END IF ELSE(搜索的方法无效) I=上次搜索的方法(下一轮将用I的下一方法去搜索)，P=P-1(后退一步返回上结点) END IF L00P UNTIL P=0 IF P=0 THEN 深度指针P为0，表示已退到起始状态，是本题无解的标志 无解 ELSE 输出结果 END IF END二、应用举例1、【问题描述】有一迷宫(如图)，可用一个10行9列的01矩阵表示，其中0表示无障碍(白色)，1表示有障碍(黑色)。设入口位置的坐标为(2，1)，出口为(9，9)，规定每次移动中只能从一个无障碍的单元移到其周围四个方向上任一无障碍的单元。试编程给出通过迷宫的一条路径或报告一个“无法通过”的信息。 出口入口【问题分析】要寻找一条通过迷宫的路径，通常用深度优先搜索。当在迷宫入口，先确定某个前进走向，依此一一试探，如某一走向有路可走，就前进一步，继续向前试探；如果无路可走，则退回一步，重新选择未走过的方向再去试探可前进的路。进进退退，再进进再退退，按此规则不断搜索，直至搜索到出口，闯迷宫成功。如最后退回入口，则此迷宫是个死胡同。在搜索迷宫时，为了不迷失方向和不走重复的路，在搜索时必须在前进与回退的路上设置一些标记，这样，就可以判断哪条路是已经走过的，哪条路是死胡同，哪条路还没有走过。根据这些标记，就能正确的找到通向出口的路，在回溯时也能正确地找到应返回的位置，避免重新进入死胡同。 【数据结构分析】建立一个相应的迷宫数组A(10，9)，再根据迷宫的01矩阵(不同的迷宫有不同的矩阵数据)，给数组的每一个元素赋予相应的值，如用X、Y表示迷宫中的位置坐标，则：A(X，Y)=0表示此处可走(白色)A(X，Y)=l表示此处是路不通(黑色)A(X，Y)=2表示此处已走过如果可走的位置已走过，就使原来的A(X，Y)=0改为A(X，Y)=2，这一点很重要，保证不陷入死循环(避免重复走某一步)。前面的两个图中后图就是前图的数学模型。设I为搜索走向指针，I的取值范围14(1向右、2向下、3向左、4向上)，这四个走向用一个数组V(4，2)来表示。第一个下标是I表示某个走向；第二个下标，1表示行增量(向下为正，向上为负)，2表示列增量(向右为正，向左为负)。四个走向的下标及其增量如下图所示。向上:V(4，1)=-1，V(4，2)=0即行减1，列没变向左:V(3，1)=0，V(3，2)=-1 即行没变，列减1向右:V(1，1)=0，V(1，2)=1 即行没变，列加1 向下:V(2，1)=1，V(2，2)=0 即行加1，列没变 变量P为深度指针，前进一步P=P+1，后退一步P=P-1，走了多少步，P值就多大。建立X和Y数组，存放已行走路线中各步的X和Y值，因不知走多少步才能走出迷宫，所以这两个数组可以定义大一些；如：DIM X(100)，Y(100)，表示走的第P步，则X(P)=X，Y(P)=Y。当某步无法前进，要退回前一步，前一步的位置X、Y值就可以从这两个数组中取出。最后输出两个数组的值，就是走出迷宫的路线。建立S数组，用它来存放已走路线中各步搜索走向的I值。当在P步搜索前进用I走向，则S(P)=I。当某步无法前进，要退回前一步，继续再向前搜索时，I的值不能再从1开始去试探，而应该从S(P)中取出 I值，从I+1开始去试探；这一点很重要,否则也会陷入死循环。举例说明：假如在第7步前进时，试探向前(向右即I=1)不行；换向下(I=2)可行，记下S(7)=2，就继续前进到第8步。如在第8步搜索前进四个走向都不行(死胡同)，只有再回到第7步，在第7步应该用I=2+1=3的方向去搜索，因为前两种方向已试探失败，不能再用。迷宫的入口值为XO、Y0，迷宫的出口值为XE、YE【程序清单】CLSDATA 1,1,1,1,1,1,1,1,1DATA 0,0,0,0,0,0,0,0,1DATA 1,0,1,0,0,1,1,0,1DATA 1,0,0,1,0,1,0,0,1DATA 1,1,0,1,0,0,1,0,1DATA 1,0,0,0,1,0,1,0,1DATA 1,0,1,1,0,0,1,0,1DATA 1,0,0,0,1,1,0,1,1DATA 1,0,1,0,0,0,0,0,0DATA 1,1,1,1,1,1,1,1,1X=10 :Y=9 迷宫大小DIM A(10,9)，S(100),X(100),Y(100) A是迷宫，S存放每步方向，X、Y存放每步的坐标XE=9 : YE=9FOR I=1 TO X 读入迷宫矩阵 FOR J=1 TO Y READ A(I,J)NEXT J,IFOR I=1 TO 4 四个方向的增量，1向右、2向下、3向左、4向上 READ V(I,1)，V（I,2）NEXT IDATA 0,1,1,0,0,-1，-1,0X0=2 : Y0=1: P=0: X(P)=X0 : Y(P)=Y0: I=0 入口坐标（2，1），起点算第0步DO I=I+1 IF I=4 THEN X=X(P)+V(I,1) :Y=Y(P)+V(I,2) IF A(X,Y)=0 THEN 通 P=P+1: S(P)=I: X(P)=X: Y(P)=Y 记录此步的方向、坐标 A(X,Y)=2 打上标记，表示此点已走过 I=0 下一步又将从1号方向开始尝试 END IF ELSE 不通，回溯 I=S(P) : P=P-1 取回上次走的方向，下一次尝试的方向将是I+1 END IFLOOP UNTIL P=0 OR X=XE AND Y=YEIF P=0 THEN 退回起点，表示迷宫是死胡同 PRINT no ELSE FOR I=0 TO P 输出成功从起点开始走出迷宫的各步坐标，I=0表示起点 PRINT (；X(I); , ；Y(I);)， NEXT IEND IFEND【运行结果】(2,1) (2,2) (3,2) (4,2) (4,3)(5,3) (6,3) (6,2) (7,2) (8,2)(8,3) (8,4) (9,4) (9,5) (9,6) (9,7) (9,8) (9,9)通过写程序，我们再次体会一下回溯的思想：这个方向有路可走，我没走过往这个方向前进是死胡同，往回走，回到上一个路口重复第一步，直到找到出口或无路可走。2、【问题描述】自然数的拆分。任何一个大于1的自然数总可以拆分成若干个自然数之和。4=11114=1124=134=2+24=4【问题分析】设拆分出的数s1s2sk，即拆分出的因子呈递增。定义数组B为一个栈，用来存放因子。每次从1开始搜索因子，求和，若S N就将因子存入数组（即压栈）；若S=N，则输出解（即出栈）；若S N，则修改最后一个数组元素的值（即栈顶元素的值），就是回溯。【程序清单】CLS : INPUT N :DIM B(100)K=1: S=0: J=0 K控制B数组的下标，J存放拆分的因子，S是拆分的因子和DO J=J+1 因子从1开始 S=S+J IF SN，则回溯 S=S-J : K=K-1 S=S-B(K) : J=B(K)END IFLOOP UNTIL K=0 当回溯到K=0时，表示所有方案均已完成END【运行示例】？55=1+1+1+1+15=1+1+1+25=1+1+35=1+2+25=1+45=2+35=5练一练:修改上面的程序，实现如下的输出结果：5=1+2+25=1+45=2+35=3+25=53、 跳马问题。【问题描述】中国象棋半张棋盘如下，马自左下角往右上角跳。现规定只许往右跳，不许往左跳。比如下图所示为一种跳行路线。 编程输出所有的跳行路线，打印格式如下：1:(0,0) (1,2) (3,1) (5,2) (6,4) (7,2) (8,4)2:(0,0) (1,2) (3,1) (5,2) (6,0) (7,2) (8,4)【问题分析】设马在某一位置（X，Y），下一步可以是如图的四个位置1、2、3、4。 (8,4)1234(0,0)【程序清单】CLSX0=0 : Y0=0 : XE=8 :YE=4 起点为(0,0),终点为(8,4)K=0 K记录方案数FOR I=1 TO 4 READ V(I,1),V(I,2) 数组V存放四个方向的坐标增量NEXT IDATA 1,2,2,1,2,-1,1,-2P=0 : X(0)=0 :Y(0)=0 : I=0 数组X和Y记录走过点的横坐标和纵坐标,I表示方向DO I=I+1 IF I=4 THENX=X(P)+V(I,1) : Y=Y(P)+V(I,2) IF X=8 AND Y=0 AND Y=0 THEN 判断点的坐标是否超界 P=P+1 :S(P)=I :X(P)=X :Y(P)=Y :I=0 将走过的方向记录在S数组中 IF X=8 AND Y=4 THEN K=K+1 ：PRINT K；“：”；FOR I=0 TO P 输出当前方案中各点的坐标 PRINT (；X(I); , ；Y(I);) ; NEXT I PRINTEND IF END IF ELSE I=S(P) : P=P-1 回溯,取出上一步所走的方向 END IFLOOP UNTIL P=0 当回溯到K=0时，表示所有方案均已完成END【运行结果】1: (0,0) (1,2) (3,1) (5,2) (6,4) (7,2) (8,4)2: (0,0) (1,2) (3,1) (5,2) (6,0) (7,2) (8,4)30: (0,0) (1,2) (2,0) (4,1) (6,0) (7,2) (8,4)教法指导：回溯算法对于小学生来说较难理解，在教学中一方面可以借助动画模拟软件帮助学生理解，另一方面可将编好的程序当成读程序，精读每一条语句，展示每一步过程，让