回溯算法(一).ppt

1、回溯算法（一）,一、回溯的概念,相信大家都走过迷宫或者玩过走迷宫的游戏吧，在走迷宫的过程中，我们从入口出发，到达路口后，选择一条岔路进入，到达下一个路口，然后再选择，。在这个过程中，我们往往会走入死路，这时我们只能退回到最近的路口，重新选择一条岔路，而如果某个路口所有的岔路都是死路的话，还必须再往前面的路口退回去。这样不停的进进退退，直到最后走出迷宫为止。,一、回溯的概念,像走迷宫这样，遇到死路就回头的搜索思路就叫做“回溯”。 从问题的某种可能情况出发，搜索所有能到达的可能情况，然后以其中一种可能的情况为新的出发点，继续向下探索，当所有可能情况都探索过且都无法到达目标的时候，再回退到上一个出发

2、点，继续探索另一个可能情况，这种不断回头寻找目标的方法称为“回溯法”。,一、回溯的概念,回溯算法是一种有条不紊的搜索问题答案的方法，是一种能避免不必要搜索的穷举式的搜索算法，其基本思想就是穷举搜索。常用于查找问题的解集或符合某些限制条件的最佳解集。,一、回溯的概念,回溯算法常被用来解决自然数排列问题、皇后问题、迷宫问题、数的拆分、0/1背包问题、骑士问题、货船装箱问题和图形覆盖问题等。,二、应用举例n皇后问题,在一个nn的棋盘上放置n个国际象棋中的皇后，要求所有的皇后之间都不形成攻击。请你给出所有可能的排布方案数。 输入：4 输出：2,n皇后问题,对于n皇后问题而言，我们很难找出很合适的方法来

3、快速的得到解，因此，我们只能采取最基本的枚举法来求解。 但我们知道，在nn的棋盘上放置n个棋子的所有放置方案有 种，而这个数字是非常庞大的，直接枚举肯定会超时。,n皇后问题,考虑到皇后攻击的特性，所有的皇后不能同行、同列，那么不妨我们先人为规定第k个皇后在第k行，这样的话我们只要给出每个皇后所处的列号就可以描述皇后的位置了。如图放置方式就可以被表示为：3、1、4、2即第1个皇后在第3列，第2个皇后在第1列，,n皇后问题,既然回溯算法是由一个节点开始逐步扩展的，因此我们采用把皇后一个一个的放到棋盘上的方式来分析问题。,n皇后问题,首先要把第一个皇后放到棋盘上由于第一个皇后有n列可以放，因此可扩展

4、出n种情况。先选其中一列放下这个皇后； 然后开始放第二个皇后。同样第二个皇后也有n列可以放，因此也能扩展出n种情况，但第二个皇后可能会和第一个皇后发生攻击，而一旦发生攻击，就没有必要往下扩展第三个皇后，而如果没有发生攻击，则继续放第三个皇后； 依此类推，直到n个皇后全都放下后，即得到一组可行解。 扩展全部完成后即可得到结果。,n皇后问题,n皇后问题,n皇后问题的解空间就应该是1n全排列的一部分。 解空间的长度是n。 解空间的组织形式是一棵n叉树，一个可行的解就是从根节点到叶子节点的一条路径。 控制策略则是当前皇后与前面所有的皇后都不同列和不同对角线。,n皇后问题（边界判定）,function

5、check(pos: integer): boolean; var i: integer; begin check := true; for i := 1 to pos - 1 do if (xpos = xi) or (abs(xpos - xi) = abs(pos - i) then begin check := false; break; end; end;,n皇后问题（递归）,procedure search(k: integer); var i: integer; begin if k n then / 是否前n个皇后都已经放下 inc(count) else / 还有皇后没放 f

6、or i := 1 to n do / 从第1列开始逐列尝试 begin xk := i; / 把第k个皇后放在第i列 if check(k) then / 第k个皇后是否可以放在第i列 search(k + 1); / 可以放，继续处理第k+1个皇后 end; end;,n皇后问题（非递归）,top := 1; / 从第一个皇后开始尝试 while (top 0) do / 当还有活动节点时循环 if (top n) then / 是否n个皇后都放置在棋盘了 begin inc(count); / 找到一组解，总数加一 dec(top); / 回到上一皇后继续 end else / n个皇后

7、还没有都放置好 begin inc(xtop); / 当前皇后到下一列 if (xtop n) then / 是否超出棋盘 dec(top) / 超出棋盘，回到上一个皇后继续 else / 没有超出棋盘 if check(top) then / 检查当前位置是否可以放皇后 begin inc(top); / 可以放置，继续尝试下一个皇后 xtop := 0; / 下一个皇后从第一列开始尝试 end; end;,四、应用举例跳马问题,在nm棋盘上有一中国象棋中的马： 马走日字； 马只能往右走。 请你找出一条可行路径，使得马可以从棋盘的左下角（1，1）走到右上角（n，m）。,跳马问题,输入：9 5

8、 输出：(1,1)-(3,2)-(5,1)-(6,3)-(7,1)-(8,3)-(9,5),跳马问题,马走日字，当马一开始在黄点时，它下一步可以到达的点有以下的八个，但由于题目规定了只能往右走的限制，所以它只能走到四个绿色点之一。,跳马问题,当马一开始位于左下角的时候，根据规则，它只有两条线路可以选择（另外两条超出棋盘的范围），我们无法预知该走哪条，故任意选择一条，到达A1。,A1,A2,跳马问题,当到达A1点后，又有三条线路可以选择，于是再任意选择一条，到达B1。 从B1再出发，又有两条线路可以选择，先选一条，到达C1。,A,A1,A2,B1,B2,B3,C1,C2,跳马问题,从C1出发，可

9、以有三条路径，选择D1。但到了D1以后，我们无路可走且D1也不是最终目标点，因此，选择D1是错误的，我们退回C1重新选择D2。同样D2也是错误的。再回到C1选择D3。D3只可以到E1，但E1也是错误的。返回D3后，没有其他选择，说明D3也是错误的，再回到C1。此时C1不再有其他选择，故C1也是错误的，退回B1，选择C2进行尝试。,A,A1,A2,B1,B2,B3,C1,C2,D1,D2,D3,E1,跳马问题,从C2出发，有四条路径可以选择，选择D4，从D4出发又有两条路径，选择E1错误，返回D4选择E2，从E2出发有两条路径，先选择F1错误，返回E2选择B，而B恰好是我们要到达的目标点，至此，

10、一条路径查找成功。,A,A1,A2,B1,B2,B3,C2,E2,B,D4,E1,F1,跳马问题,从上面的分析我们可以得知： 在无法确定走哪条线路的时候，任选一条线路进行尝试； 当从某点出发，所有可能到达的点都不能到达终点时，说明此点是一个死节点，必须回溯到上一个点，并重新选择一条新的线路进行尝试。,骑士遍历,为了描述路径，我们最直接的方法就是记录路径上所有点的坐标。但比较繁琐。 如果我对马可以走到的四个点都编上号（方向），那么我们很容易得到每一个方向上两个坐标和原位置的关系。 同时，四个方向都有了编号，那么在选择路径的时候也就可以不采用任选的方式了，只需按照编号依次尝试就可以了。,骑士遍历,

11、增量数组：dx = (1, 2, 2, 1)dy = (-2, -1, 1, 2),若马所处的位置为(x,y)，则其下一步可以到达的四个位置分别是(x+1, y-2)，(x+2, y-1)，(x+2, y+1)，(x+1, y+2)。,在使用增量数组后，只要知道方向t，下一步的位置就是(x+dxt, y+dyt)。,骑士遍历,为了判断棋子是否落在棋盘上，我们还必须知道当前棋子（扩展节点）的位置信息。而用一系列的方向来表示就比较麻烦，因此，我们另外使用两个变量来保存当前棋子的坐标。但这时千万要注意的是一定要在回溯的时候，修改当前棋子的坐标。,骑士遍历,骑士遍历问题的解空间是从左下角到右上角的所有

12、路径。 解空间的长度是所有路径中最长的路径的长度。 解空间的组织形式是一棵四叉树，一个可行的解就是从根节点到叶子节点的一条路径。 控制策略则是马必须在棋盘内。,骑士遍历（递归）,procedure search(k: integer); / 递归查找 begin for i := 1 to 4 do / 依次尝试四个方向 if (x + dxi 0) and (y + dyi = m) then / 在棋盘上 begin routek := i; / 记录下当前方向 x := x + dxi; y := y + dyi; / 修改扩展节点坐标 if (x = n) and (y = m) th

13、en / 是否是目标点 begin output(k); halt; / 是目标点，输出结果并终止程序 end else search(k+1); / 不是目标点，继续尝试下一步 / 扩展出的点是死点，回溯 x := x - dxi; y := y - dyi; / 恢复扩展节点坐标 end; end;,骑士遍历（非递归）,top := 1; / 从第一步开始尝试 while (x n) or (y m) and (top 0) do begin inc(routetop); / 取下一个方向为当前方向 if (routetop 4) then begin / 是否四个方向全部尝试过 dec(

14、top); / 都尝试过，回溯，并恢复扩展节点坐标 x := x - dxroutetop; y := y - dyroutetop; end else begin / 还有方向可以尝试 x := x + dxroutetop; y := y + dyroutetop; / 修改扩展节点坐标 if (x n) or (y m) or (y 1) then begin / 活动点是否在棋盘上 x := x - dxroutetop; y := y - dyroutetop; / 不在棋盘上，恢复 end else begin / 在棋盘上 inc(top); / 继续尝试一步 routetop

15、:= 0; / 下一步从第一个方向开始尝试 end; end; end;,骑士遍历（思考）,在本例中，我们只要求输出一条可行路径，如果我们需要输出所有的可行路径，怎样改动此程序呢？ 如果我们把问题改成“在nm的棋盘上有一骑士，开始时，骑士在点(x,y)，现在请你找出一条可行的路径，使得骑士可以不重复的走遍棋盘上的每一个点。”的话，又要如何编写此程序呢？,四、应用举例自然数拆分,任何一个自然数x都可以被写成若干自然数之和的形式，如：514；523；511111；。现请你编写一个程序，给出自然数x的所有拆分等式（23和32视为相同形式）。 输入：4 输出：4=1+3 4=1+1+2 4=1+1+1

16、+1 4=2+2,自然数拆分,自然数拆分其实就是数的组合问题，根据题目的描述，我们可知，对于符合题意的任意一个组合必须满足： 组合中的所有数字之和为n； 每个组合中数字的个数不固定（2n） 因此，最直接的想法就是枚举所有可能的组合，然后判断是否符合题意。由于数字允许重复，因此需要枚举的数量为 显然这个数量级是非常庞大的。,自然数拆分,下面我们需要一些策略来减少枚举的数量 由于题目中规定符合加法交换律的等式是同一种拆分，因此，为了避免出现重复，我们规定整个等式中的数字是从左往右递增的。 同时根据加法结合律，我们可以认为122这个等式是有14这个等式进一步拆分而得的（因为4可以拆分成22的形式）。

17、因此，我们不妨就考虑数字被拆分成两个数字之和的情况，然后对于拆分而得的两个数字继续考虑是否能被继续拆分。,自然数拆分,由于我们规定了左边的数字不能超过右边的数字，因此在拆分时，第一个数字较小，不再继续拆分，而第二个数字较大，需要考虑继续拆分。 当第二个数字不能再被拆分时，回溯到上一次拆分继续。,自然数拆分,对于某一次拆分，第一个数字的取值范围为上一个拆分得到的数字到这次拆分数字的一半。 我们可以得到如下的图示,自然数拆分,7,6,5,4,5,4,3,2,4,3,3,2,1,1,1,1,1,1,1,2,3,2,3,2,2,3,2,2,2,自然数拆分,我们可以得到： 问题的解空间是从根结点到任意节

18、点的路径； 解空间的长度为n； 解空间的组织形式是一棵树； 控制策略是前一个数字不超过后一个数字。,自然数拆分（递归）,procedure try(m, start, k: integer); / m为当前要拆分的数，start为拆分的起始值，k为递归层次 var i, j: integer; begin for i := start to (m div 2) do begin ak := m i;/ 保持当前节点 bk := i;/ 保持当前拆分所取的值 write(n, =);/ 输出等式 for j := 1 to k do write(bk, +); writeln(ak); try(

19、ak, i, k+1);/ 递归拆分当前节点 end; end;,自然数拆分（非递归）,read(n); k := 0; ak := n; bk := 1; start := 1; / 初始化 while k = 0 do begin if start (ak div 2) then begin / 判断当前数字是否可以再拆分 start := bk + 1; / 设置下一次拆分的初始值 dec(k); / 回溯 end else begin inc(k); / 继续向下拆分 ak := ak-1 - start; / 保存拆分的第二个数字 bk := start; / 保存拆分的第一个数字

20、write (n, =); / 输出等式 for i := 1 to k do write(bi, +); writeln(ak); end end;,四、应用举例四色问题,有形如下列图形的地图，图中每一块区域代表一个省份，现请你用红（1）、兰（2）、黄（3）、绿（4）四种颜色给这些省份填上颜色，要求每一省份用一种颜色，且任意两个相邻省份的颜色不能相同，请给出一种符合条件的填色方案。地图用无向图的形式给出，每个省份代表图上的一个顶点，边代表两个省份是相邻的。,四色问题,输入70 1 0 0 0 0 11 0 1 1 1 1 10 1 0 1 0 0 00 1 1 0 1 0 00 1 0 1

21、0 1 00 1 0 0 1 0 11 1 0 0 0 1 0 输出1 2 1 3 1 3 4,四色问题,要得到一种可行的填色方案，比较直接的做法就是一个省一个省的填色，在填色的过程中去检查是否和周围省份的颜色存在冲突。 从第一个省份开始，对每个省份依次尝试四种颜色，判断当然选择的颜色是否和相邻的省份相同。 若都不相同，则将此省份填上当前的颜色。 若存在相同，则取下一种颜色继续尝试。 若四种颜色都不能填上，则退回上一个省份并选择下一种颜色继续尝试。 当最后一个省份也被填色后就找到一组可行解。,四色问题,四色问题的解空间是所有的填色方案。 解空间的长度是n。 解空间的组织形式是一棵四叉树，一个可行的解就是从根节点到叶子节点的一条路径。 控制策略则是当前颜色与相邻省份颜色不能相同。,四色问题（递归）,procedure search(m: integer); / 递归搜索第m个省份 begin if m n then begin / 是否所有省份都已经填色 write(s1); / 已全部填色，输出结果，终止程序 for j := 2 to n do write( , sj); writ