《回溯算法讲解》由会员分享，可在线阅读，更多相关《回溯算法讲解（17页珍藏版）》请在金锄头文库上搜索。
1、沙栏中学信息学奥林匹克竞赛培训教材回溯算法回溯算法与递归算法实现方法完全相同，所用的自定义过程或函数几乎完全相同，只是在我们对它的理解以及这些函数/过程运行时有所不同。它的基本思想是：在搜索过程中，当探索到某一步时，发现原先的选择达不到目标，就退回到上一步重新选择。它主要用来解决一些要经过许多步骤才能完成的，而每个步骤都有若干种可能的分支，为了完成这一过程，需要遵守某些规则，但这些规则又无法用数学公式来描述的一类问题。回溯的实现有递归和非递归两种方法。例1、八皇后问题，要在国际象棋棋盘中放八个皇后，使任意两个皇后都不能互相吃，即任意两个皇后都不能处于同一行、同一列或同一斜线上，共有多少种放法，
2、全部打印出来。分析：皇后能吃同一行、同一列、同一对角线的任意棋子。所以，我们可以这样考虑：在每一行中放一个皇后，从第一行开始，在往每新的一行加皇后时，我们必须确保这个皇后必须不能与已经取得的所有皇后都不在同一列或同一条对角线。我们定义一个数组来存放八个皇后的在1到8行中的列位置，所以形式参数就可以只要一个行号，当行号达到9时，我们就找到了一个答案。这样，我们就能把所有答案找出来。uses crt; var a:array1.8 of byte; a数组用来存放8个皇后在棋盘中的列位置(为什么不用二维数组？)第一个元素记录第一个皇后在第一行中的位置,第二个元素记录第2个皇后在第二行中的位置.以此
3、类推t:integer; t用来存放答案数目procedure qu(n:byte);varl,k:integer; l表示行,k表示列b:boolean;begin if n=9 then如果8个皇后的位置都排好, (出口) begin t:=t+1;统计方法数 writeln(t); for k:=1 to 8 do 输出8个皇后在棋盘中的状态 begin for l:=1 to 8 do if (akl) then write(.:3) else write(Q:3); writeln; end; writeln; readln;暂停 endelse begin for k:=1 to
4、8 do 检索当前皇后应在哪一列?逐行检索,每一个皇后在每一行中应占的列 begin b:=true; for l:=1 to n-1 do 逐行检索已确定的皇后的位置,如果当前试探列k与前面已确定的n-1个皇后冲突,作上标志 b=false(则检索下一列) if (al=k) or (abs(al-k)=abs(l-n) then b:=false; (al=k) 判断是否同列.(abs(al-k)=abs(l-n)判断是否在斜线上 abs(al-k)=abs(l-n),如果:列-列=行-行,则在斜线上 if b then 若b=true,则该列k,不与前面的皇后冲突begin an:=k;
5、 记录本行n,皇后应占的位置 qu(n+1);探索下一位皇后 end; end; end;end; begin clrscr;清屏 t:=0; qu(1); 开始找第一位皇后 writeln; writeln( total ,T,);输出排列的总方式 readln;end. 从上述程序中可以看出，回溯过程和递归过程的程序看起来完全是同一类型的，程序也几乎相同，都是定义了出口，然后中间就是调用过程，展开下一层节点。但实际运行过程中，回溯和递归是有差别的，递归是每次顺一条路往下走都能找到答案，然后才往回回溯；而回溯则不然，在中间某层时，就有可能走不通，下一层一个节点都无法展开，这时就只能在中途就回
6、溯了。编写： 把8皇后问题中简化为4皇后问题的程序。我们把8皇后问题中简化为4皇后问题。如果我们的前两个皇后放的位置为：1、3，这时，第三个皇后是无法放下去的（为什么？），这时就只能回溯，返回第二层（这个返回是循环结束，正常结束此次过程，于是返回调用它的上一层过程），第二个皇后就放到第4个位置，位置变为：1、4，这时，再展开第3个皇后，可放在第三2个位置，位置变为：1、4、2，再展开第4个皇后，这时，第四个皇后又无法放下，于是返回第三层，第三层已别无选择，再返回第二层，仍无其它选择，于是返回第一层，第一个皇后放在第2个位置，再展开第二层，放第4个位置，再展开第三层，放第1个位置，再展开第四层，
7、放第3个位置，这时，才找到第一个答案。从这我们完全可以看出，递归在找到一个答案前，是不会中途回溯的；而回溯在找到第一个答案前有可能就已经回溯了好几次了。递归算法是往下展开时就一直往下走；而回溯则是中途可以任意返回，回溯是能进则进，不能进则退。两种算法的程序是相似的，但运行过程是不同的。再看看另一种方法（N皇后）：1）不同行：由于是一行只排一个皇后，所以肯定不同行。 2）不同列：设置一个数组：MARK0，当J列已安排皇后时，MARK0J:=FALSE。不允许再安排皇后。 3）不在同一对角线：*任意一条红色左斜线上的方格坐标都有一个规律：相等，只要标记MARK1I+J:=FALSE，该条红色左斜线
8、都将不可安排。红色的斜线从最左边11，2+1或1+2到NN条。*任意一条绿色的右斜线上的方格坐标也有一个规律：相等，也只要定义MARK2I-J=FALSE，则所有该右斜线都将不可安排。绿色的斜线从最右边 1-N到N-1条。最后的条件是：当皇后准备安排在第 J列时，必须符合下列条件，才能安排： If MARK0J AND MARK1I+J and MARK2I-J Then Begin xI:=J； 安排皇后 MARK0J:=FALSE； MARK1I+J:=FALSE； MARK2I-J:=FALSE； 设置约束条件，让其他皇后无法再放置End；当所有的J都不满足条件，第I+1个皇后无法安置时
9、，此时应回溯第I个皇后，回溯如下： MARK0J:=TRUE： MARK1I+J:=TRUE： MARK2I-J:=TRUE 将第 I个皇后的约束条件释放，待重新安置后再确定约束条件。 varx:array1.8 of integer; 当前8个皇后所摆的方案a,b,c:array-7.16 of boolean; 分别是列，对角线，反对角线为什么是-7？i:integer;procedure print; 打印本次方案var k:integer;beginfor k:=1 to 8 do write(xk:4);writeln;end;procedure try(i:integer); 使用
10、回溯法递归求解，试遍所有的情况，是一种递归枚举var j:integer;beginfor j:=1 to 8 doif aj and bi+j and ci-j 若(i,j) 可放then begin xi:=j; 则第i行就放在第j列 aj:=false; 做上相应位置不能放的标志 bi+j:=false; ci-j:=false; if i8 then try(i+1) 8个没放完，则继续放 else print; 放完去打印方案 aj:=true; 回溯回来后，撤去不能放的标志 bi+j:=true; ci-j:=true endend;beginfor i:=-7 to 16 do初
11、始化为每个位置均可放beginai:=true;bi:=true;ci:=trueend;try(1);从第一行开始end.例2、求N个数的全排列。（1至N）分析：当n=3时我们可以使用多重循环来做：for I:=1 to 3 do for j:=1 to 3 do if Ij then for k:=1 to 3 do if (kI) and (kj) write(i, j , k); 但当n的值不确定的时候，循环层数无法确定，无法使用多重循环。我们可以这样考虑，求N个数的全排列，可以看成把N个不同的球放入N个不同的盒子中，每个盒子中只能有一个球。具体算法：在过程中使用循环来放置每一个可能的
12、值到第一个盒子中，然后将其它的数用同样的方式放到后面的第2个盒子中，再把除掉这两个数的其它数用同样的方式放到后面的第3个盒子中，以此类推，可以使用循环来做，但不知道需要多少层循环，我们可以做成递归的形式，即在过程中调用自身，调用之前应该做的工作应该是将前面用过的数排除掉。我们可以定义两个相同下标的数组，其中一个数组x用来放数，另一个数组a用来表示该数有没有被前面放置过，未放置则其值为true，放置过之后其值置为false。数据结构定义：1、设数组a为N个空盒可以放N个数，一开始数组a全部置为true，表示都可以放，放完之后置为false，表示不可以放了。2、设数组x是放置每一次排列的数组，在过程中try应该是从第1个数组元素开始的，而下一次的递归调用其下标应该逐次加1，即调用try(i+1);3、Total为累记总数过程如下：procedure try(i:integer); 调用的时候确定xi的值var j:integer;begin for j:=1 to n do if aj=true then begin xi:=j; aj:=false; 某一个数被用过之后，在后面的递归调用中不能再用
