第5章_回溯法_jimmy

1、1第5章 回溯法计算机与信息工程学院第五章 回溯法 (Back tracking)1、穷举法应用：有限离散问题总可以用穷举法求得问题的全部 0-1背包问题(0-1Knapsack Problem )设有n个物体和一个背包,物体i的重量为wi价值为pi背包的载荷为M,若将物体i(1 i n,)装入背包,则有价值为pi .目标是找到一个方案,使得能放入背包的物体总价值最高例 题若取W= (16,15, 15), P= (45,25, 25), C=30穷举法求解相当于分别计算每个可能解，再求最优解例如 取N=3 , 问题所有可能的解为：(0, 0, 0), (0, 0, 1), (0, 1, 0)

2、, (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1) 时间复杂性: O(2n)2、穷举法改进 对于某些组合难题的较大实例，我们可以用穷举法求解，但穷举法的规模较大，所以我们对它进行改进，提出了回溯法和分支界限法两种算法设计技术。 两种技术的区别在于他们能处理的问题类型不同，分支界限法只能应用于最优问题，而回溯法可以搜索任何问题的所有解和任一解。4有许多问题，当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时，往往要使用回溯法。回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。这种方法适用于解

3、一些组合数相当大的问题。回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。回溯法5问题的解空间 问题的解向量：回溯法希望一个问题的解能够表示成一个n元式(x1,x2,xn)的形式。 显约束：对分量xi的取值限定。 隐约束：为满足问题的解而对不同分量之间施加的约束。 解空间：对于问题的一个实例，解向量满足显式约束条件的所有多元组，构成了该实例的一个解空间。注意：同一个问题可以有多种表示，有些表示方法更简单，所需表示的状态空间更小（存储量少，搜索方法简单）。例如（0-1背包问题）：取N=3 , 问题所有可能的解 (解空间)为: (0, 0, 0), (0, 0, 1), (0,

4、1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1) 解空间树：通过对所做的选择结构构造一棵解空间树，树根代表了在查找解之前的初始状态。树的第一层节点代表对解的第一个分量所做的选择，第二层节点代表了对解的第二个分量所做的选择，以此类推。 如果一个部分构造解（子树）仍然有可能导致一个完整解，我们说这个部分解在树中的相应节点是有希望的。否则说是没希望的。 叶子要么代表没希望的，要么代表算法找到完整解。解空间树若取W= (16,15, 15), P= (45,25, 25), C=30例如 取N=3 , 问题所有可能的解为(解空间)

5、: (0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1)0-1背包问题解空间树可表示为一棵3层的完全二叉树求解过程相当于在树中搜索满足条件的叶结点.8相关概念扩展结点:一个正在产生儿子的结点称为扩展结点活结点:一个自身已生成但其儿子还没有全部生成的节点称做活结点死结点:一个所有儿子已经产生的结点称做死结点深度优先的问题状态生成法：如果对一个扩展结点R，一旦产生了它的一个儿子C，就把C当做新的扩展结点。在完成对子树C（以C为根的子树）的穷尽搜索之后，将R重新变成扩展结点，继续生

6、成R的下一个儿子（如果存在） 回溯法在问题的解空间树中，按深度优先策略，从根节点出发搜索解空间树。算法搜索至解空间树的任一节点时，先判断该节点是否包含问题的解。 如果肯定不包含，则跳过对以该节点为根的子树的搜索，逐层向其祖先节点回溯。 否则，进入该子树，继续按深度优先策略搜索。 回溯法求问题的所有解时，要回溯到根，且根节点的所有子树都已被搜索遍才结束。 回溯法求解问题的一个解时，只要搜索到问题的一个解就可以结束。 这种以深度优先方式系统搜索问题解的算法称为回溯法。搜索策略回溯法举例：若取W= (16,15, 15), P= (45,25, 25), C=30回溯法举例：旅行商问题 在这个问题中

7、，给出一个n 顶点网络（有向或无向），要求找出一个包含所有n 个顶点的具有最小耗费的环路。任何一个包含网络中所有n 个顶点的环路被称作一个旅行（t o u r）。在旅行商问题中，要设法找到一条最小耗费的旅行。分析图给出了一个四顶点网络。在这个网络中，一些旅行如下： 1 , 2 , 4 , 3 , 1；1 , 3 , 2 , 4 , 1和1 , 4 , 3 , 2 , 1。旅行1 , 2 , 4 , 3 , 1的耗费为6 6；而1 , 3 , 2 , 4 , 1的耗费为2 5；1 , 4 , 3 , 2 , 1为5 9。故1 , 3 , 2 , 4 , 1是该网络中最小耗费的旅行。 旅行是包含所

8、有顶点的一个循环，故可以把任意一个点作为起点旅行是包含所有顶点的一个循环，故可以把任意一个点作为起点（因此也是终点）。针对该问题，任意选取点（因此也是终点）。针对该问题，任意选取点1 1作为起点和终点，则每作为起点和终点，则每一个旅行可用顶点序列一个旅行可用顶点序列1, 1, v v2 ,2 , , , vn vn , 1, 1来描述，来描述，v v2, 2, , , vn vn 是是(2, (2, 3, 3, , , n n) ) 的一个排列。可能的旅行可用一个树来描述，其中每一个的一个排列。可能的旅行可用一个树来描述，其中每一个从根到叶的路径定义了一个旅行。从根到叶的路径定义了一个旅行。

9、下图给出了一棵表示四顶点网络的树。从根到叶的路径中各边的下图给出了一棵表示四顶点网络的树。从根到叶的路径中各边的标号定义了一个旅行（还要附加标号定义了一个旅行（还要附加1 1作为终点）。例如，到节点作为终点）。例如，到节点L L的路径的路径表示了旅行表示了旅行1 , 2 , 3 , 4 , 11 , 2 , 3 , 4 , 1，而到节点，而到节点O O的路径表示了旅行的路径表示了旅行1 , 3 , 1 , 3 , 4 , 2 , 14 , 2 , 1。网络中的每一个旅行都由树中的一条从根到叶的确定路径。网络中的每一个旅行都由树中的一条从根到叶的确定路径来表示。因此，树中叶的数目为来表示。因此，

10、树中叶的数目为( (n n-1 )-1 )！。 回溯算法将用深度优先方式从根结点开始，通过搜索解空间树发现一个最小耗费的旅行。一个可能的搜索为A B C F L。在L点，旅行1 , 2 , 3 , 4 , 1作为当前最好的旅行被记录下来。它的耗费是5 9。从L点回溯到活结点F。由于F没有未被检查的孩子，所以它成为死结点，回溯到C点。C变为新扩展结点，向前移动到G，然后是M。这样构造出了旅行1 , 2 , 4 , 3 , 1，它的耗费是6 6。既然它不比当前的最佳旅行好，抛弃它并回溯到G，然后是C , B。从B点，搜索向前移动到D，然后是H , N。这个旅行1 , 3 , 2 , 4 , 1的耗

11、费是2 5，比当前的最佳旅行好，把它作为当前的最好旅行。从N点，搜索回溯到H，然后是D。在D点，再次向前移动，到达O点。如此继续下去，可搜索完整个树，得出1 , 3 , 2 , 4 , 1是最少耗费的旅行。14回溯法的基本思想(1)针对所给问题，定义问题的解空间；(2)确定易于搜索的解空间结构；(3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。常用剪枝函数：用约束函数在扩展结点处剪去不满足约束的子树；用限界函数剪去得不到最优解的子树。例如，解0-1背包问题，回溯法用剪枝函数剪去导致不可行解的子树。在解旅行商问题的回溯法中，如果从根节点到当前扩展结点处的部分周转路线费用已超过

12、当前找到的最好的周游路线费用，则可以断定以该结点为根的子树中不含最优解，因此可将该子树剪去。void backtrack(int t) if (t n) /t表示深度，tn表示算法已搜索到叶节点。 Output(x); /记录或输出得到的可行解x。 else for (int i = f(n,t);i 0) if (f(n,t) = g(n,t) for (int i = f(n,t);i n) output(x); else for (int i=0;in) output(x); else for (int i=t; ic1。移动到节点E，这个移动未改变c w。下一步为节点J，c w= 1

13、0。J的左孩子的c w值为1 3，超出了c1，故搜索不能移动到J的左孩子。 可移动到J的右孩子，它是一个叶节点。至此，已找到了一个子集，它的c w= 1 0。xi 的值由从A到J的右孩子的路径获得，其值为 1 , 0 , 1 , 0 。 回溯算法接着回溯到J，然后是E。从E，再次沿着树向下移动到节点K，此时c w= 8。移动到它的左子树，有c w= 11。既然已到达了一个叶节点，就看是否c w的值大于当前的最优c w 值。结果确实大于最优值，所以这个叶节点表示了一个比 1 , 0 , 1 , 0 更好的解决方案。到该节点的路径决定了x 的值 1 , 0 , 0 , 1 。template Ty

14、pe Maxloading(type w, type c, int n) Loading X； /初始化X X. w=w; /集装箱重量数组 X. c=c; /第一艘船载重量 X. n=n；/集装箱数 X. bestw=0; /当前最优载重 X. cw=0;/当前载重量 X. r=0; /剩余集装箱重量 for (int i=1; i=n; i+) /初始化r X. r +=wi; X.Backtrack(1)； /计算最优载重量 return X.bestw； 装载问题的回溯算法算法复杂性: O(2n)算法MaxLoading调用递归函数Backtrack(1)实现回溯搜索。Backtrac

15、k(i)搜索子集树中第i层子树。类Loading的数据成员记录子集树中结点信息，以减少传给Backtrack的参数。Backtrack(int i)算法实现：templatevoid Loading:Backtrack(int i) / /搜索第i层结点 if (in) /到达叶结点 if (cwbestw) bestw=cw； return； /搜索子树 if (cw+wi bestw，则表示当前解优于最优解。目前最优解的值被更新。 当in 时，当前扩展节点Z是子集树中的内部节点。它有两个孩子节点。左孩子表示xi=1 的情况，只有cw + wic 时，才能对左子树递归搜索。 由于可行结点的右

16、儿子结点总是可行的，故进入右子树时不需检查可行性。 当移动到左孩子时，当移动到左孩子时，cw cw 被置为被置为cw+wicw+wi，且到达一个，且到达一个i+1i+1层的节层的节点。以该节点为根的子树被递归搜索。调用点。以该节点为根的子树被递归搜索。调用Backtrack (i+1)Backtrack (i+1)； 当搜索完成时，回到节点当搜索完成时，回到节点Z Z（第（第i i层）。为了得到层）。为了得到Z Z的的cwcw值，需用值，需用当前的当前的cw cw 值减去值减去wiwi。Z Z的右子树还未搜索。的右子树还未搜索。 既然这个子树表示既然这个子树表示xi=0 xi=0的情况，所以无

17、需进行可行性检查就的情况，所以无需进行可行性检查就可移动到该子树，因为一个可行节点的右孩子总是可行的。即执行可移动到该子树，因为一个可行节点的右孩子总是可行的。即执行Backtrack (i+1)Backtrack (i+1)； if (cw+wi=c) /xi=1左孩子 cw += wi； Backtrack (i+1)； cw - = wi; Backtrack(i+1)； /xi=0右孩子3、加入上界函数 引入上界函数，用于剪去不含最优解的子树，从而改进算法在平均情况下的运行效率。 设r是剩余集装箱的重量。定义上界函数为cw+r。在以Z为根的子树中任意叶结点所相应的载重量不超过cw+r。

18、因此，当cw+rbestw时，可将Z的右子树剪去。templatevoid Loading:Backtrack(int i) / /搜索第i层结点 if (in) /到达叶结点 if (cwbestw) bestw=cw； return； /搜索子树 r - = wi; if (cw+wi bestw) /控制剪去右子树 Backtrack(i+1)； r+=wi； 4、构造最优解templatevoid Loading:Backtrack(int i) / /搜索第i层结点 if (in) /到达叶结点 if (cwbestw) for (int j = 1; j = n; j+) best

19、xj = xj; /最优解 bestw=cw； return； /搜索子树 r - = wi; if (cw+wi bestw) /控制剪去右子树 xi=0； Backtrack(i+1)； r+=wi； 在算法中记录与当前最优值相应的当前最优解。在类Loading中增加两个私有数据成员x和bestx数组。x记录从根至当前结点的路径。bestx记录当前最优解。算法思路:将棋盘从左至右,从上到下编号为1,.,n,皇后编号为1,.,n. 设解为(x1, ., xn) , xi为皇后i放在棋盘的第i行的第xi列。解空间:E= (x1,., xn) | xiSi, i=1,.,4, Si=1, .,

20、4,1 i n；解空间为排列树。其约束集合D为 1) xi xj 2) xi-i xj-j 3) xi+i xj+j皇后i,j不在同一斜线上（隐约束）5.3 n后问题皇后i,j不在同一列上（显约束）问题描述:nXn棋盘上放置n个皇后使得每个皇后互不受攻击，即任二皇后不能位于同行同列和同一斜线上。 四后问题的解等价于： |i-j|xi-xj|回溯法解题步骤:针对所给问题,定义问题的解空间；确定解空间结构；以深度优先方式搜索解空间并按约束条件进行剪枝。（未剪枝之前）回溯求解四后问题过程中被激活过的结点（a）（b）（c）（d）（e）（f）（g）（h）2 int nQueen(int n) Queen

21、 X； /初始化X X. n=n；/皇后个数 X. sum=0； int*p=new int n+1； for(int i=0；i=n；i+) pi= 0； X.x=p； X.Backtrack(1)； delete p； return X. sum；n后问题的回溯算法bool Queen: Place(int k) for (int j = 1; j n) sum+; else for (int i=1;i n时，算法搜索至叶结点，得到一个新的n皇后互不攻击放置方案，当前已找到方案数sum增1； in时，当前扩展结点Z的每一个儿子节点，由Place检查其可行性，并以深度优先的方式递归地对可行

22、子树搜索，或减去不可行子树。图的m色判定问题: 给定无向连通图G和m种颜色。用这些颜色为图G的各顶点着色. 问是否存在着色方法, 使得G中任2邻接点有不同颜色。图的m色优化问题:给定无向连通图G,为图G的各顶点着色, 使图中任2邻接点着不同颜色,问最少需要几种颜色。所需的最少颜色的数目m称为该图的色数。5.4 图的m着色问题 问题描述可平面图：如果一个图的所有顶点和边都能用某种方式画在平面上，且没有任何两面相交，则称这个图为可平面图。4色定理：若图G是可平面图,则它的色数不超过4色。4色定理的应用:在一个平面或球面上的任何地图能够只用4种颜色来着色使得相邻的国家在地图上着有不同颜色。43215

23、12345a)将G的结点按照度数递减的次序排列. b)用第一种颜色对第一个结点着色,并按照结点排列的次序 对与前面着色点不邻接的每一点着以相同颜色.c)用第二种颜色对尚未着色的点重复步骤b).用第三种颜色 继续这种作法, 直到所有点着色完为止. 任意图的着色Welch Powell（韦尔奇-鲍威）着色法a1a5a4a6a2a3a7a8 排序:a5, a3, a7, a1, a2, a4, a6, a8 着第一色: a5, a1,着第二色:a3,a4, a8着第三色:a7, a2, a6设图G=(V, E), |V|=n, 颜色数= m, 用邻接矩阵a表示G, 用整数1, 2m来表示m种不同的颜

24、色。顶点i所着的颜色用xi表示。问题的解向量可以表示为n元组x= x1,.,xn . xi1,2,.,m,解空间树为排序树,是一棵n+1层的完全m叉树.在解空间树中做深度优先搜索, 约束条件: xi xj, 如果aji=1. 算法思路n=3, m=3时的解空间树132a= int mColoring(int n, int m, int *a ) Color X； /初始化X Xn=n； /图的顶点数 Xm=m /可用颜色数 Xa=a； /图的邻接矩阵 XSum=0; /已找到的着色方案数 int*p=new int n+1； for (int i=0；in) sum+； for(int i=1

25、; i=n; i+) cout xi ； cout endl ； else for ( int i=1; i=m; i+) xt=i; if (Ok(t) Backtrack(t+1); xt=0; bool Color:Ok(int k)/检查颜色可用性，即约束条件 for(int j=1；jn时，算法搜索至叶结点，得到新的m着色方案，当前找到的可m着色的方案数sum增一。 当in时，当前扩展结点Z是解空间中的内部结点。该结点有xi=1,2,m共m个儿子结点。对当前扩展结点Z的每一个儿子结点，由函数OK检查其可行性，并以深度优先递归地对可行的子树进行搜索，或减去不可行的子树。图m可着色问题的

26、解空间树中内结点个数是对于每一个内结点，在最坏情况下，用Ok检查当前扩展结点的每一个儿子所相应的颜色可用性需耗时O(mn)。因此，回溯法总的时间耗费是复杂度分析5.5 旅行售货员问题 旅行商问题的解空间是一个排列树。如果以x=1, 2, , n 开始，那么通过产生从x2 到xn 的所有排列，可生成n 顶点旅行商问题的解空间。templateT AdjacencyWDigraph:TSP(int v) /* 用回溯算法解决旅行商问题返回最优旅游路径的耗费，最优路径存入v 1 : n */ /初始化 x = new int n+1;/ x 是排列 for (int i = 1; i = n; i+

27、) xi = i;bestc = NoEdge;bestx = v; / 使用数组v来存储最优路径cc = 0; t S P ( 2 ) ; / 搜索x 2 : n 的各种排列 delete x;return bestc;void AdjacencyWDigraph:tSP(int i) / 旅行商问题的回溯算法if (i = n) / 位于一个叶子的父节点 通过增加两条边来完成旅行if (axn-1xn != NoEdge &axn1 != NoEdge & (cc + axn-1xn + axn1 bestc |bestc = NoEdge) / 找到更优的旅行路径for

28、(int j = 1; j = n; j+)bestxj = xj;bestc = cc + axn-1xn + axn1;else/ 尝试子树 for (int j = i; j = n; j+) / /能移动到子树x j 吗? if (axi-1xj != NoEdge &(cc + axi-1xi bestc |bestc = NoEdge) /能搜索该子树 Swap(xi, xj);cc += axi-1xi;t S P ( i + 1 ) ;cc -= axi-1xi;Swap(xi, xj); 当i=n 时，处在排列树的叶节点的父节点上，并且需要验证从xn-1 到xn 有一条边，从xn 到起点x1 也有一条边。若两条边都存在，则发现了一个新旅行。在本例中，需要验证是否该旅行是目前发现的最优旅行。若是，则将旅行和它的耗费分别存入b e s t x与b e s t c中。 当in 时，检查当前i-1 层节点的孩子节点，并且仅当以下情况出现时，移动到孩子节点之一： 1) 有从xi-1 到xi 的一条边（如果是这样的话， x 1 : i 定义了网络中的一条路径）； 2 )路径x1:i 的耗费小于当前最优解的耗费。 变量c