第六章 回 溯 法.

Presentation on theme: "第六章 回 溯 法."— Presentation transcript:

1 第六章 回 溯 法

2 回溯法的基本思想 回溯法算法 回溯法例子 n皇后问题 图的m着色问题

3 0/1背包问题 给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?

4 例子: n=3 w＝[16,15,15] p=[45,25,25], c=30 1）思考所有可能的解 2）将解组织成一个结构，以便搜索。（树状结构） 此结构为解空间

5 n=3时的0-1背包问题用完全二叉树表示的解空间

6 求解过程： 也就是树的遍历的过程。 深度优先搜索DFS。 排除不符合条件的子树。 从根到叶节点为一个解。 回溯法：为了避免生成那些不可能产生最佳解的问题状态，要不断地利用限界函数(bounding function)来处死那些实际上不可能产生所需解的活结点，以减少问题的计算量。具有限界函数的深度优先生成法称为回溯法

7 用处：有许多问题，当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时，往往要使用回溯法。
回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。

8 回溯法的基本思想 (1)针对所给问题，定义问题的解空间； (2)确定易于搜索的解空间结构；
(3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。 常用剪枝函数： 用约束函数在扩展结点处剪去不满足约束的子树； 用限界函数剪去得不到最优解的子树。

9 用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为O(h(n))。而显式地存储整个解空间则需要O(2h(n))或O(h(n)!)内存空间。

10 基本概念： 扩展结点:一个正在产生儿子的结点称为扩展结点 活结点:一个自身已生成但其儿子还没有全部生成的节点称做活结点
死结点:一个所有儿子已经产生的结点称做死结点 深度优先的问题状态生成法：如果对一个扩展结点R，一旦产生了它的一个儿子C，就把C当做新的扩展结点。在完成对子树C（以C为根的子树）的穷尽搜索之后，将R重新变成扩展结点，继续生成R的下一个儿子（如果存在）

11 宽度优先的问题状态生成法：在一个扩展结点变成死结点之前，它一直是扩展结点
回溯法：为了避免生成那些不可能产生最佳解的问题状态，要不断地利用限界函数(bounding function)来处死那些实际上不可能产生所需解的活结点，以减少问题的计算量。具有限界函数的深度优先生成法称为回溯法

12 递归回溯 回溯法对解空间作深度优先搜索，因此，在一般情况下用递归方法实现回溯法。 void backtrack (int t) {
if (t>n) output(x); else for (int i=f(n,t);i<=g(n,t);i++) { x[t]=h(i); if (constraint(t)&&bound(t)) backtrack(t+1); }

13 迭代回溯 采用树的非递归深度优先遍历算法，可将回溯法表示为一个非递归迭代过程。 void iterativeBacktrack () {
int t=1; while (t>0) { if (f(n,t)<=g(n,t)) for (int i=f(n,t);i<=g(n,t);i++) { x[t]=h(i); if (constraint(t)&&bound(t)) { if (solution(t)) output(x); else t++;} } else t--;

14 子集树 遍历子集树需O(2n)计算时间 void backtrack (int t) { if (t>n) output(x);
else for (int i=0;i<=1;i++) { x[t]=i; if (legal(t)) backtrack(t+1); } 遍历子集树需O(2n)计算时间

15 排列树 遍历排列树需要O(n!)计算时间 void backtrack (int t) { if (t>n) output(x);
else for (int i=t;i<=n;i++) { swap(x[t], x[i]); if (legal(t)) backtrack(t+1); } 遍历排列树需要O(n!)计算时间

16 n后问题 在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n×n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。 1 2 3 4 5 6 7 8 Q

17 2)不处于同一正、反对角线：|i-j||xi-xj|
解向量：(x1, x2, … , xn) 显约束：xi=1,2, … ,n 隐约束： 1)不同列：xixj 2)不处于同一正、反对角线：|i-j||xi-xj| bool Queen::Place(int k) { for (int j=1;j<k;j++) if ((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k])) return false; return true; } void Queen::Backtrack(int t) if (t>n) output(x); else for (int i=1;i<=n;i++) { x[t]=i; if (Place(t)) Backtrack(t+1);

18

19 图的m着色问题 给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。是否有一种着色法使G中每条边的2个顶点着不同颜色。这个问题是图的m可着色判定问题。若一个图最少需要m种颜色才能使图中每条边连接的2个顶点着不同颜色，则称这个数m为该图的色数。求一个图的色数m的问题称为图的m可着色优化问题。

20 解向量：(x1, x2, … , xn)表示顶点i所着颜色x[i]

21 void Color::Backtrack(int t)
{ if (t>n) output(x) else for (int i=1;i<=m;i++) { x[t]=i; if (Ok(t)) Backtrack(t+1); } bool Color::Ok(int k) {// 检查颜色可用性 for (int j=1;j<=n;j++) if ((a[k][j]==1)&&(x[j]==x[k])) return false; return true;

22 复杂度分析 图m可着色问题的解空间树中内结点个数是 对于每一个内结点，在最坏情况下，用ok检查当前扩展结点的每一个儿子所相应的颜色可用性需耗时O(mn)。因此，回溯法总的时间耗费是

23 用回溯法设计解装载问题的O(2n)计算时间算法。在某些情况下该算法优于动态规划算法。
有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i的重量为wi，且 装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。如果有，找出一种装载方案。 容易证明，如果一个给定装载问题有解，则采用下面的策略可得到最优装载方案。 (1)首先将第一艘轮船尽可能装满； (2)将剩余的集装箱装上第二艘轮船。 将第一艘轮船尽可能装满等价于选取全体集装箱的一个子集，使该子集中集装箱重量之和最接近。由此可知，装载问题等价于以下特殊的0-1背包问题。 用回溯法设计解装载问题的O(2n)计算时间算法。在某些情况下该算法优于动态规划算法。

24 当前载重量cw+剩余集装箱的重量r当前最优载重量bestw
解空间：子集树 可行性约束函数(选择当前元素)： 上界函数(不选择当前元素)： 当前载重量cw+剩余集装箱的重量r当前最优载重量bestw private static void backtrack (int i) {// 搜索第i层结点 if (i > n) // 到达叶结点 更新最优解bestx,bestw;return; r -= w[i]; if (cw + w[i] <= c) {// 搜索左子树 x[i] = 1; cw += w[i]; backtrack(i + 1); cw -= w[i]; } if (cw + r > bestw) { x[i] = 0; // 搜索右子树 backtrack(i + 1); } r += w[i]; }

25

26 回溯法效率分析 通过前面具体实例的讨论容易看出，回溯算法的效率在很大程度上依赖于以下因素： (1)产生x[k]的时间；
(3)计算约束函数constraint的时间； (4)计算上界函数bound的时间； (5)满足约束函数和上界函数约束的所有x[k]的个数。 好的约束函数能显著地减少所生成的结点数。但这样的约束函数往往计算量较大。因此，在选择约束函数时通常存在生成结点数与约束函数计算量之间的折衷。

27 跳马问题 在n×m棋盘上有一中国象棋中的马： 马走日字； 马只能往右走。
输入：9 5 输出：(1,1)->(3,2)->(5,1)->(6,3)->(7,1)->(8,3)->(9,5)

28 当马一开始位于左下角的时候，根据规则，它只有两条线路可以选择（另外两条超出棋盘的范围），我们无法预知该走哪条，故任意选择一条，到达A1。
分析： 按题意，马每一步可以有4种走法！ 搜索过程： 当马一开始位于左下角的时候，根据规则，它只有两条线路可以选择（另外两条超出棋盘的范围），我们无法预知该走哪条，故任意选择一条，到达A1。 A A1 A2 当到达A1点后，又有三条线路可以 选择，于是再任意选择一条，到达B1。 从B1再出发，又有两条线路可以选择，先选一条，到达C1。 A A1 A2 B1 B2 B3 C1 C2

29 从C1出发，可以有三条路径，选择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恰好是我们要到达的目标点，至此，一条路径查找成功。 A A1 A2 B1 B2 B3 C2 E2 B D4 E1 F1

30 从上面的分析我们可以得知： 在无法确定走哪条线路的时候，任选一条线路进行尝试；为方便路径表示，对马可以走到的四个点（方向）都编上号； 当从某点出发，所有可能到达的点都不能到达终点时，说明此点是一个死节点，必须回溯到上一个点，并重新选择一条新的线路进行尝试。 y ① ② ③ ④ 解空间: 为了描述路径，我们最直接的方法就是记录路径上所有点的坐标。 x 优化：每一个方向上两个坐标和原位置对应关系 增量数组： 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)。 path:array[1..m] of integer; 其中，path[i]：表示第i个节点所走的方向 方向t，下一步的位置就是(x+dx[t], y+dy[t])。

31 约束条件： 状态树： ① ② ③ ④ ⑤ ⑥ ⑤ ④ ⑥ ⑤ ④ ⑥ ⑤ ⑤
不越界： (x + dx[i] <= n) and (y + dy[i] > 0) and (y + dy[i] <= n) 状态树： 算法描述： 产生一种新走法 越界，继续用新走法，直到找到一种走法不越界----不超过4种走法 if 不越界 then k<nk+1 k=n一组解 if 越界 then 回溯 ① ② ③ ④ ⑤ ⑥ Path[1]:=3 Path[2]:=2 Path[3]:=3 Path[4]:=2 3 4 Path[5]:=1 ① ② ③ ④ ⑦ ⑤ ④ ⑥ ⑤ ④ ② ⑥ ⑦ ① ③ ⑤ ⑤

32 跳马问题（递归） { read(n,m); x=1; y=1; search(1); }
search(k: integer); // 递归查找 { for (i = 1;i<=4;i++) // 依次尝试四个方向 if ((x + dx[i] <= n) && (y + dy[i] > 0)&& (y + dy[i] <= n)) // 在棋盘上 path[k] = i; // 记录下当前方向 x = x + dx[i]; y = y + dy[i]; // 修改扩展节点坐标 if ((x = n) && (y = m)) // 是否是目标点 output(k); halt; // 是目标点，输出结果并终止程序 else search(k+1); // 不是目标点，继续尝试下一步 // 扩展出的点是死点，回溯 x := x - dx[i]; y := y - dy[i]; // 恢复扩展节点坐标，状态恢复 } { read(n,m); x=1; y=1; search(1); }

33 跳马问题（非递归） Horse() { path[1] ← 0，k ← 1，x ←1，y ←1
while ((x!=m) && (y!=n) ){ path[k] ←path[k] +1 while ((x + dx[i] <= n) && (y + dy[i] > 0) && (y + dy[i] <= n) &&(path[k]<=4)) path[k] ← path[k] +1 if (path[k]<=4){ {在4种走法中找到不越界的走法} x ←x+dx[i]，y ←y+dy[i] if ((x==m) && (y==n)) print else{ k ← k+1 path[k] ← 0 } else path[k] ← 0，k ← k-1

34 跳马问题（思考） 在本例中，我们只要求输出一条可行路径，如果我们需要输出所有的可行路径，怎样改动此程序呢？<递归><非递归> 如果我们把问题改成“在n×m的棋盘上有一骑士，开始时，骑士在点(x,y)，现在请你找出一条可行的路径，使得骑士可以不重复的走遍棋盘上的每一个点。”的话，又要如何编写此程序呢？

35 迷宫问题 设有一个N*N方格的迷宫，入口和出口分别在左上角和右上角，迷宫格子中分别放有0和1，0表示可走，1表示不能走，迷宫走的规则如图。当迷宫给出之后，找出一条从入口到出口的通路。 输入：N N*N的迷宫 输出：具体路径 输入样例： 8 1 输入样例： (1,1)-(2,1)-(3,1)-(2,2)-(1,3)-(2,4)-(3,3)-(4,3)-(5,2)-(6,3)-(7,3)-(8,2)-(8,1)

36 x y 解空间 约束条件 状态树 分析： 迷宫信息用二维数组表示 A:array[1..maxn,1..maxn] of 0..1;
 1  增量和方向表示 dx=(1,1,-1,-1,1,-1,0,0) dy=(-1,0,1,0,1,-1,1,-1) y 解空间 path:array[1..maxn*maxn] of integer; 其中，path[i]：表示第i个节点所走的方向 ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ 约束条件 不越界且该点可走 (x>=1) and (x<=N) and (y>=1) and (y<=N) and A[x,y]=0 状态树

37

38 填数问题 从整数1到10中任取9个不同的数，填入下面的9个格子中，使所有相邻（左、右、上、下）两个格子中的数的和是素数。 4 3 8
【问题描述】 从整数1到10中任取9个不同的数，填入下面的9个格子中，使所有相邻（左、右、上、下）两个格子中的数的和是素数。 【输出】 一行3个数，共3行。 【样例】 【说明】 输出所有本质不同的解。（通过某个解的旋转、上下翻转、左右翻转得到的是本质相同的）

39 组合的输出 【问题描述】 排列与组合是常用的数学方法，其中组合就是从n个元素中抽出r个元素(不分顺序且r<＝n)，我们可以简单地将n个元素理解为自然数1，2，…，n，从中任取r个数。 现要求你不用递归的方法输出所有组合。 例如n＝5，r＝3，所有组合为： l l l l 【输入】 一行两个自然数n、r(1<n<21，1<＝r<＝n)。 【输出】 所有的组合，每一个组合占一行且其中的元素按由小到大的顺序排列，每个元素占三个字符的位置，所有的组合也按字典顺序。 【样例】 输入 5 3 输出 1 2 3 1 2 4 1 2 5 1 3 4 1 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5

40 算24点 【问题描述】 几十年前全世界就流行一种数字游戏，至今仍有人乐此不疲．在中国我们把这种游戏称为“算24点”。您作为游戏者将得到4个1~9之间的自然数作为操作数，而您的任务是对这4个操作数进行适当的算术运算，要求运算结果等于24。 您可以使用的运算只有：+，-，*，/，您还可以使用（）来改变运算顺序。注意：所有的中间结果须是整数，所以一些除法运算是不允许的（例如，(2*2)/4是合法的，2*(2/4)是不合法的）。下面我们给出一个游戏的具体例子： 若给出的4个操作数是：1、2、3、7，则一种可能的解答是1+2+3*7=24。 【输入】 只有一行，四个1到9之间的自然数。 【输出】 如果有解的话，只要输出一个解，输出的是三行数据，分别表示运算的步骤。其中第一行是输入的两个数和一个运算符和运算后的结果，第二行是第一行的结果和一个输入的数据、运算符、运算后的结果；第三行是第二行的结果和输入的一个数、运算符和“=24”。如果两个操作数有大小的话则先输出大的。 如果没有解则输出“No answer!” 【输入样例】 【输出样例】 =3 7*3=21 21+3=24