回溯法_PPT教学课件

1、第五章. 回溯法回溯法 (back traiking)1 1、穷举法应用：、穷举法应用：有限离散问题总可以用穷举法求得问题的全部有限离散问题总可以用穷举法求得问题的全部 0-1 0-1背包问题背包问题( (0-10-1knapsack problem knapsack problem ) )设有设有n n个物体和一个背包个物体和一个背包, ,物体物体i i的重量为的重量为w wi i价值为价值为p pi i背包的载荷为背包的载荷为m,m,若将物体若将物体i i(1(1 i i n,)n,)装入背包装入背包, ,则有价值为则有价值为p pi i . .目标是找到一个方案目标是找到一个方案, ,使

2、得能放入背包的物体总价值最高使得能放入背包的物体总价值最高例例 题题若取若取w= (16,15, 15), p= (40,25, 25), c=30w= (16,15, 15), p= (40,25, 25), c=30穷举法求解相当于分别计算每个可能解，再求优解穷举法求解相当于分别计算每个可能解，再求优解例如例如 取取n=3 , n=3 , 问题所有可能的解为问题所有可能的解为(解空间解空间): (0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1) 时间复杂性时间复杂性:

3、o(2n)2 2、穷举法改进、穷举法改进对于某些组合难题的较大实例，我们可以用穷举法求解，对于某些组合难题的较大实例，我们可以用穷举法求解，但穷举法的规模较大，所以我们对它进行改进，提出了回溯法和但穷举法的规模较大，所以我们对它进行改进，提出了回溯法和分支界限法两种算法设计技术。分支界限法两种算法设计技术。它们每次只构造候选解的一个分量，然后评估这个部分它们每次只构造候选解的一个分量，然后评估这个部分构造解：如果加上剩下的分量也不可能求得一个解，就绝不会生构造解：如果加上剩下的分量也不可能求得一个解，就绝不会生成剩下的分量。成剩下的分量。他们是一构造一棵解空间树为基础的，树的节点反映了他们是一

4、构造一棵解空间树为基础的，树的节点反映了对一个部分解做出的特定选择，如果可以保证，节点子孙所对应对一个部分解做出的特定选择，如果可以保证，节点子孙所对应的选择不可能得出问题的一个结，两种技术都回立即停止处理这的选择不可能得出问题的一个结，两种技术都回立即停止处理这个节点。个节点。两种技术的区别在于他们能处理的问题类型不同，分支两种技术的区别在于他们能处理的问题类型不同，分支界限法只能应用于最优问题，而回溯法可以搜索任何问题的所有界限法只能应用于最优问题，而回溯法可以搜索任何问题的所有解和任一解。解和任一解。5.1 回溯法基本思想穷举法技术建议我们先生成所有的候选解，然后找出那个穷举法技术建议我

5、们先生成所有的候选解，然后找出那个具有需要特性的元素具有需要特性的元素1 1、回溯法主要思想是每次只构造解的一个分量，然后按照、回溯法主要思想是每次只构造解的一个分量，然后按照鲜明的方法来评估这个部分构造解。如果一个部分构造解可以进一鲜明的方法来评估这个部分构造解。如果一个部分构造解可以进一步构造而不会违反问题的约束，我们就接受对下一个分量所作的第步构造而不会违反问题的约束，我们就接受对下一个分量所作的第一个合法选择。如果无法对下一个分量进行合法的选择，就不对剩一个合法选择。如果无法对下一个分量进行合法的选择，就不对剩下的任何分量再做任何选择了。在这种情况下，该算法进行回溯，下的任何分量再做任

6、何选择了。在这种情况下，该算法进行回溯，把部分构造解的最后一个分量替换为它的下一个选择。把部分构造解的最后一个分量替换为它的下一个选择。2 2、解空间树：通过对所做的选择结构构造一棵解空间树，、解空间树：通过对所做的选择结构构造一棵解空间树，树根代表了在查找解之前的初始状态。树的第一层节点代表对解的树根代表了在查找解之前的初始状态。树的第一层节点代表对解的第一个分量所做的选择，第二层节点代表了对解的第二个分量所做第一个分量所做的选择，第二层节点代表了对解的第二个分量所做的选择，以此类推。的选择，以此类推。如果一个部分构造解（子树）仍然有可能导致一个完整解，如果一个部分构造解（子树）仍然有可能导

7、致一个完整解，我们说这个部分解在树中的相应节点是有希望的。否则说是没希望我们说这个部分解在树中的相应节点是有希望的。否则说是没希望的。的。叶子要么代表没希望的，要么代表算法找到完整解叶子要么代表没希望的，要么代表算法找到完整解若取若取w= (16,15, 15), w= (16,15, 15), p= (40,25, 25), p= (40,25, 25), c=30 c=30例如例如 取取n=3 , n=3 , 问题所有可能的解为问题所有可能的解为(解空间解空间): (0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1

8、), (1, 1, 0), (1, 1, 1)0-10-1背包问题解空间树背包问题解空间树可表示为一棵可表示为一棵3层的完全正则二叉树层的完全正则二叉树时间复杂性时间复杂性: o(2n)求解过程相当于在树中搜索求解过程相当于在树中搜索满足条件的叶结点满足条件的叶结点. .3、搜索策略、搜索策略回溯法在问题的解空间树中，按深度优先策略，从根节回溯法在问题的解空间树中，按深度优先策略，从根节点出发搜索解空间树。算法搜索至解空间树的任一节点时，先点出发搜索解空间树。算法搜索至解空间树的任一节点时，先判断该节点是否包含问题的解。判断该节点是否包含问题的解。如果肯定不包含，则跳过对以该节点为根的子树的搜

9、索，如果肯定不包含，则跳过对以该节点为根的子树的搜索，逐层向其祖先节点回溯逐层向其祖先节点回溯否则，进入该子树，继续按深度优先策略搜索。否则，进入该子树，继续按深度优先策略搜索。回溯法求问题的所有解时，要回溯到根，且根节点的所回溯法求问题的所有解时，要回溯到根，且根节点的所有子树都已被搜索遍才结束。有子树都已被搜索遍才结束。回溯法求解问题的一个解时，只要搜索到问题的一个解回溯法求解问题的一个解时，只要搜索到问题的一个解就可以结束。就可以结束。这种以深度优先方式系统搜索问题解的算法称为回溯法。这种以深度优先方式系统搜索问题解的算法称为回溯法。回溯法举例：回溯法举例：若取若取w= (16,15,

10、15), p= (40,25, 25), c=30w= (16,15, 15), p= (40,25, 25), c=30回溯法举例：回溯法举例： 旅行商问题旅行商问题 在这个问题中，给出一个在这个问题中，给出一个n n 顶点网络（有向顶点网络（有向或无向），要求找出一个包含所有或无向），要求找出一个包含所有n n 个顶点的具有最小耗个顶点的具有最小耗费的环路。任何一个包含网络中所有费的环路。任何一个包含网络中所有n n 个顶点的环路被称个顶点的环路被称作一个旅行（作一个旅行（t o u rt o u r）。在旅行商问题中，要设法找到一）。在旅行商问题中，要设法找到一条最小耗费的旅行。条最小耗

11、费的旅行。 分析分析 图给出了一个四顶点网络。在这个网络中，一些旅图给出了一个四顶点网络。在这个网络中，一些旅行如下：行如下： 1 , 2 , 4 , 3 , 11 , 2 , 4 , 3 , 1；1 , 3 , 2 , 4 , 11 , 3 , 2 , 4 , 1和和1 , 4 , 3 , 2 , 11 , 4 , 3 , 2 , 1。旅行旅行1 , 2 , 4 , 3 , 11 , 2 , 4 , 3 , 1的耗费为的耗费为6 66 6；而；而1 , 3 , 2 , 4 , 11 , 3 , 2 , 4 , 1的耗费的耗费为为2 52 5；1 , 4 , 3 , 2 , 11 , 4 ,

12、3 , 2 , 1为为5 95 9。故。故1 , 3 , 2 , 4 , 11 , 3 , 2 , 4 , 1是该网络中是该网络中最小耗费的旅行。最小耗费的旅行。旅行是包含所有顶点的一个循环，故可以把任意一个点作旅行是包含所有顶点的一个循环，故可以把任意一个点作为起点（因此也是终点）。针对该问题，任意选取点为起点（因此也是终点）。针对该问题，任意选取点1 1作为起点和作为起点和终点，则每一个旅行可用顶点序列终点，则每一个旅行可用顶点序列1, 1, v v2 ,2 , , , vnvn , 1, 1来描述，来描述，v v2, 2, , , vnvn 是是(2, 3, (2, 3, , , n n

13、) ) 的一个排列。可能的旅行可用一个树来的一个排列。可能的旅行可用一个树来描述，其中每一个从根到叶的路径定义了一个旅行。下图给出了描述，其中每一个从根到叶的路径定义了一个旅行。下图给出了一棵表示四顶点网络的树。从根到叶的路径中各边的标号定义了一棵表示四顶点网络的树。从根到叶的路径中各边的标号定义了一个旅行（还要附加一个旅行（还要附加1 1作为终点）。例如，到节点作为终点）。例如，到节点l l的路径表示了的路径表示了旅行旅行1 , 2 , 3 , 4 , 11 , 2 , 3 , 4 , 1，而到节点，而到节点o o的路径表示了旅行的路径表示了旅行1 , 3 , 1 , 3 , 4 , 2 ,

14、 14 , 2 , 1。网络中的每一个旅行都由树中的一条从根到叶的确定。网络中的每一个旅行都由树中的一条从根到叶的确定路径来表示。因此，树中叶的数目为路径来表示。因此，树中叶的数目为( (n n- 1 )- 1 )！。！。回溯算法将用深度优先方式从根节点开始，通过搜索解空间回溯算法将用深度优先方式从根节点开始，通过搜索解空间树发现一个最小耗费的旅行。对题中网络，利用前页的解空间树，树发现一个最小耗费的旅行。对题中网络，利用前页的解空间树，一个可能的搜索为一个可能的搜索为a b c f la b c f l。在。在l l点，旅行点，旅行1 , 2 , 3 , 4 , 11 , 2 , 3 , 4

15、 , 1作为当前作为当前最好的旅行被记录下来。它的耗费是最好的旅行被记录下来。它的耗费是5 95 9。从。从l l点回溯到活节点点回溯到活节点f f。由。由于于f f没有未被检查的孩子，所以它成为死节点，回溯到没有未被检查的孩子，所以它成为死节点，回溯到c c点。点。c c变为变为e-e-节点，向前移动到节点，向前移动到g g，然后是，然后是mm。这样构造出了旅行。这样构造出了旅行1 , 2 , 4 , 3 , 1 , 2 , 4 , 3 , 1 1，它的耗费是，它的耗费是6 66 6。既然它不比当前的最佳旅行好，抛弃它并回溯。既然它不比当前的最佳旅行好，抛弃它并回溯到到g g，然后是，然后是

16、c , bc , b。从。从b b点，搜索向前移动到点，搜索向前移动到d d，然后是，然后是h , nh , n。这。这个旅行个旅行1 , 3 , 2 , 4 , 11 , 3 , 2 , 4 , 1的耗费是的耗费是2 52 5，比当前的最佳旅行好，把它作为，比当前的最佳旅行好，把它作为当前的最好旅行。当前的最好旅行。从从nn点，搜索回溯到点，搜索回溯到hh，然后是，然后是d d。在。在d d点，再次向前移动，到点，再次向前移动，到达达o o点。如此继续下去，可搜点。如此继续下去，可搜索完整个树，得出索完整个树，得出1 , 3 , 2 , 4 , 1 , 3 , 2 , 4 , 1 1是最少耗

17、费的旅行。是最少耗费的旅行。设问题的解可表示为设问题的解可表示为n n元组元组( (x x1 1, , x x2 2, , x xn n), ), x xi i s si i , , s si i为有限为有限集集, ,n n元组的子组元组的子组( (x x1 1, , x x2 2, , x xi i) ) i in 回溯法回溯法1.1.子集树子集树: :当解向量为不定长当解向量为不定长n n元组时元组时, , 树中从根至每一结点的路径树中从根至每一结点的路径集合构成解空间集合构成解空间. .树的每个结点称为一个树的每个结点称为一个解状态解状态, ,有儿子的结点称为有儿子的结点称为可扩展结点可

18、扩展结点, ,叶结点称为叶结点称为终止结点终止结点, ,若结点若结点v v对应解状态对应解状态( (x x1 1, , x x2 2, , x xi i) ), ,则其儿子对应则其儿子对应扩展的解扩展的解状态状态( (x x1 1, , x x2 2, , x xi, i, x xi+1i+1 ). ).满足所有满足所有约束条件约束条件的解状态结点称为的解状态结点称为回答结点回答结点.0-1.0-1背包问题的解空间就是子集树背包问题的解空间就是子集树2.2.排序树排序树: :当解向量为定长当解向量为定长n n元组时元组时, , 树中从根至叶结点的路径的集合树中从根至叶结点的路径的集合构成解空间

19、构成解空间. .树的每个叶结点称为一个解状态树的每个叶结点称为一个解状态. .旅行商问题的解空间就旅行商问题的解空间就是排序树是排序树解空间树构造解空间树构造: :搜索按深度优先策略从根开始搜索按深度优先策略从根开始, , 当搜索到任一结点时当搜索到任一结点时, ,判断该点是否判断该点是否满足约束条件满足约束条件d(d(剪枝函数剪枝函数),),满足则继续向下深度优先搜索满足则继续向下深度优先搜索, ,否则跳过否则跳过该结点以下的子树该结点以下的子树( (剪枝剪枝),),向上逐级回溯向上逐级回溯. .搜索过程搜索过程: :求解过程可表示为在一棵求解过程可表示为在一棵解空间树解空间树 作作 深度优

20、先搜索深度优先搜索. .procedure backtrack(n)；k:=l； repeat if tk (x1,x2,.xk-1 )中的值未取遍中的值未取遍 then xk:tk (x1，x2，., x k-1 )中未取过的一个值；中未取过的一个值； if bk (x1, x2, ., x k) then /状态结点状态结点(x1,.xk(x1,.xk) )被激活被激活 if kn then output(x1, x2, ., xk) /输出一个回答结点输出一个回答结点 e1se k:k + l； /深度优先深度优先 e1se k:k-l； /回溯回溯 until k0；end；backt

21、rack算法模式算法模式5 5、回溯、回溯法解题步骤法解题步骤: :1).1).针对所给问题针对所给问题, ,定义问题的解空间定义问题的解空间2).2).确定解空间结构确定解空间结构. .3).3).以深度优先方式搜索以深度优先方式搜索解空间解空间. .算法设计与分析算法设计与分析 回溯法回溯法6 6、递归回溯、递归回溯算法设计与分析算法设计与分析 回溯法回溯法调用一次调用一次backtrack(1)即可完成整个回溯搜索过程即可完成整个回溯搜索过程void backtrack(int t) if (t n) /t表示深度，表示深度，tn表示算法以搜索到叶节点。表示算法以搜索到叶节点。 outp

22、ut(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后问题5.2 装载问题问题描述问题描述:n个集装箱装到2艘载重量分别为c1,c2的货轮,其中集装箱i的重量为wi且 问题要求找到一个合理的装载方案可将这n个货箱装上这2艘轮船。211ccwnii例如 当n=3, c1=c2=50, w=10, 40, 40, 可将货箱1和2装到第一艘船上;货箱3装到第二艘船上; 若w=20, 40, 40, 则无法将全部货箱装船.当当 时问

23、题等价于子集和问题时问题等价于子集和问题; ; 当当c1=c2c1=c2且且 时时问题等价于划分问题问题等价于划分问题. .211ccwnii112cwnii若装载问题有解, 采用如下策略可得一个最优装载方案:(1)将第一艘轮船尽可能装满; (2)将剩余的货箱装到第二艘轮船上。将第一艘船尽可能装满等价于如下0-l背包问题:niiixw1m ma ax x12cxwniiixi0,1, 1in可采用动态规划求解, 其时间复杂性为:o(c1,2n)算法设计与分析算法设计与分析 回溯法回溯法 装载问题装载问题算法思路算法思路:用排序树表示解空间,则解为n元向量x1, . ,xn , xi0, 1 j

24、iiixw1 + wj+1 c1约束条件:由于是最优化问题, 可利用最优解性质进一步剪去不含最优解的子树:设 bestw: 当前最优载重量, cw = : 当前扩展结点的载重量 ; r = : 剩余集装箱的重量;当 cw+r (限界函数)bestw 时, 将cw对应右子树剪去。jiiixw1njijw1cw+r bestwjiiixw1 + wj+1 c1例如例如 n=4, c1=12, w=8, 6, 2, 3.cw=0cw=8cw=14cw=8cw=10cw=13bestw=10cw=8bestw=11cw=0cw=6cw=8bestw=11 搜索从根搜索从根a开始且开始且cw= 0。若移

25、动到左孩子。若移动到左孩子b则则cw= 8，cwc1 = 12。以。以b为根的子树包含一个可行的节点，故移动到节点为根的子树包含一个可行的节点，故移动到节点b。从节点。从节点b不能移动到节不能移动到节点点d，因为，因为c w+w2 c1。移动到节点。移动到节点e，这个移动未改变，这个移动未改变c w。下一步为节。下一步为节点点j，c w= 1 0。j的左孩子的的左孩子的c w值为值为1 3，超出了，超出了c1，故搜索不能移动到，故搜索不能移动到j的的左孩子。左孩子。 可移动到可移动到j的右孩子，它是一个叶节点。至此，已找到了一个子集，它的右孩子，它是一个叶节点。至此，已找到了一个子集，它的的c

26、 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 更好的解更好的解决方

27、案。到该节点的路径决定了决方案。到该节点的路径决定了x 的值的值 1 , 0 , 0 , 1 。template type 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 b e s t wc w b e s t w，则表示当前解优于最优解。目前最优解答，则表示当前解优于最优解。目前最优解答的值被更新。的值被更新

28、。 当当inin 时，当前扩展节点时，当前扩展节点z z是子集树中的内部节点。它有两个孩是子集树中的内部节点。它有两个孩子节点。左孩子表示子节点。左孩子表示xixi= = 的情况，只有的情况，只有cw + wiccw + wic 时，才能移时，才能移到这里。到这里。 当移动到左孩子时，当移动到左孩子时，cwcw 被置为被置为cw+wicw+wi ，且到达一个，且到达一个i+1i+1层的节层的节点。以该节点为根的子树被递归搜索。调用点。以该节点为根的子树被递归搜索。调用backtrack (i+1)backtrack (i+1)； 当搜索完成时，回到节点当搜索完成时，回到节点z z（第（第i i

29、层）。为了得到层）。为了得到z z的的cwcw值，需用值，需用当前的当前的cwcw 值减去值减去wiwi 。z z的右子树还未搜索。既然这个子树表示的右子树还未搜索。既然这个子树表示xixi=0=0的情况，所以无需进行可行性检查就可移动到该子树，因为一的情况，所以无需进行可行性检查就可移动到该子树，因为一个可行节点的右孩子总是可行的。即执行个可行节点的右孩子总是可行的。即执行backtrack (i+1)backtrack (i+1)；backtrack(int i)算法实现：templatevoid loading:backtrack(int i) / /搜索第i层结点 if (in) /到

30、达叶结点 bestw=cw； return； /搜索子树 if (cw+wi=c) /xi=1左孩子 cw += wi； backtrack (i+1)； cw - = wi; backtrack(i+1)； /xi=0右孩子 3、加入上界函数、加入上界函数 引入上界函数，用于引入上界函数，用于剪去不含最优解的子树，剪去不含最优解的子树，从而改进算法在平均情况从而改进算法在平均情况下的运行效率。下的运行效率。 设设r是剩余集装箱的是剩余集装箱的重量。定义上界函数为重量。定义上界函数为cw+r。在以。在以z为根的子树为根的子树中任意叶结点所相应的载中任意叶结点所相应的载重量不操作重量不操作cw+

31、r。因此，。因此，当当cw+rbestw时，可将时，可将z的右子树剪去。的右子树剪去。4、构造最优解、构造最优解templatevoid loading:backtrack(int i) / /搜索第搜索第i层结点层结点 if (in) /到达叶结点到达叶结点 bestw=cw； return； /搜索子树搜索子树 r - = wi; if (cw+wi bestw) /控制剪去右子树控制剪去右子树 backtrack(i+1)； r+=wi if (i n) / 在叶节点上在叶节点上for (int j = 1; j 回溯法回溯法 n后问题53 批处理作业调度批处理作业调度问题描述问题描述:

32、给定n个作业的集合j=(j1, j2, . , jn)。每一作业ji都有两项任务要分别在2台机器上完成. 每一作业须先由机器l处理, 再由机器2处理. 设tji是作业ji在机器j上的处理时间, i=1,.,n, j=1, 2.fji是作业ji在器j上完成处理的时间. 所有作业在机器2上完成时间和: f=f2i 称为作业调度的完成时间和完成时间和.对于给定的j, 要求制定一个最佳作业调度方案, 使完成时间和最小.算法思路算法思路:设解为n元向量x1,. ,xn , xi1,.n, 用排序树表示解空间 约束条件: 当i j , xi xj (元素不能重复选取)限界函数: bestx:为当前最小时间

33、和 x : 当前扩展结点的时间和; r : 剩余作业的时间和;当 x+r 回溯法回溯法 作业调度int flow(int * m, int n, int bestx ) int ub = 32767; flowshop x; x.x = new int n+ 1; /当前调度 x.f2 = new intn+ l; x.m = m; /各作业所需处理时间 x.n= n; /作业数 x.bestx = bestx; /当前最优调度 x. bestf = ub; /当前最优调度时间 x.fl = 0; /机器2完成处理时间 x.f = 0; /机器1完成处理时间 for(int i = 0;i=

34、n; i+) x.f2i = 0,x.xi=i; x. backtrack( 1 ); delete x. x; delete x. f2; return x. bestf ;算法复杂性算法复杂性: o(n!)作业调度回溯回溯算法backtrack中，中， 当当in时，算法搜索至时，算法搜索至叶结点，得到一个新的作叶结点，得到一个新的作业调度方案，此时算法适业调度方案，此时算法适合更新当前最优值和相应合更新当前最优值和相应的当前最佳作业调度。的当前最佳作业调度。 当当in) for(int j = 1;j = n; j+) bestxj = xj; bestf = f; else for (i

35、nt j = i; j fl)?f2i-1:fl) +mxj2; f+= f2i; if (f 回溯法回溯法 作业调度 机器1 机器2 作业1 2 1 作业2 3 1 作业3 2 3 tji 这三个作业的6种可能调度方案是: 1, 2, 3; 1, 3, 2; 2, 1, 3; 2, 3, 1; 3, l, 2; 3, 2, l;（穷举法）相应的完成时间和分别是: 10, 8, 10，9，7，8。最佳调度: 3, 1, 2; 完成时间为7，时间从0开始计时。机器1机器2j1j1j3j3j2j2调度1,3,2例例 题题机器1机器2j3j3j2j2调度3,1,2j1j1算法设计与分析算法设计与分析

36、 回溯法回溯法 作业调度 机器1 机器2 作业1 2 1 作业2 3 1 作业3 2 3 tji 这三个作业的6种可能调度方案是: 1, 2, 3; 1, 3, 2; 2, 1, 3; 2, 3, 1; 3, l, 2; 3, 2, l;相应的完成时间和分别是: 10, 8, 10，9，7，8。最佳调度: 3, 1, 2; 完成时间为7。x1=j1j2j3x2=j2j3j1x3=j3abcdefj2bestx=7j3efj3j1j2efj2j2j1例例 题题算法思路算法思路:将棋盘从左至右将棋盘从左至右,从上到下编号为从上到下编号为1,.,n,皇后编号为皇后编号为1,.,n. 设解为设解为(x

37、1, ., xn) , xi为皇后为皇后i放在棋盘的第放在棋盘的第i行的第行的第xi列。列。解空间解空间:e= (x1,., xn) | xi si, i=1,.,4, si=1, ., 4,1 i n；解空间；解空间为排列树为排列树.其其约束集合约束集合d为为 1) xi xj 2) xi-i xj-j 3) xi+i xj+j皇后皇后i,ji,j不在同一斜线上（隐约束）不在同一斜线上（隐约束）算法设计与分析算法设计与分析 回溯法回溯法 n n后问题后问题5.4 n5.4 n后问题后问题皇后皇后i,ji,j不在同一列上（显约束）不在同一列上（显约束）问题描述问题描述:nxn:nxn棋盘上放置

38、棋盘上放置n n个皇后使得每个皇后互不受攻击个皇后使得每个皇后互不受攻击. . 即任二即任二皇后不能位于同行同列和同一斜线上皇后不能位于同行同列和同一斜线上. . 四后问题的解四后问题的解等价于：等价于： |i-j| |xi-xj|回溯回溯法解题步骤法解题步骤: :针对所给问针对所给问题题, ,定义问题的解空间；确定定义问题的解空间；确定解空间结构；解空间结构；以深度优先方以深度优先方式搜索式搜索解空间并按约束条件解空间并按约束条件进行剪枝进行剪枝. .算法设计与分析算法设计与分析 回溯法回溯法 n后问题（未剪枝之前）（未剪枝之前）回溯求解四后问题过程中被激活过的结点算法设计与分析算法设计与分

39、析 回溯法回溯法 n后问题（a）（b）（c）（d）（e）（f）（g）（h）1 int nqueen(int n) queenx； /初始化初始化x x x. n=n；/皇后个数皇后个数 x. sum=0； int*p=new int n+1； for(int i=0；i 回溯法回溯法 n后问题算法设计与分析算法设计与分析 回溯法回溯法 n后问题bool queen: place(int k) for (int j = 1; j n) sum+; else for (int i=1;i n时，算法搜索至叶时，算法搜索至叶结点，得到一个新的结点，得到一个新的n皇后皇后互不攻击防止方案，当前已互不攻

40、击防止方案，当前已找到方案数找到方案数sum增增1； in时，当前扩展结点时，当前扩展结点z的每一个儿子节点，由的每一个儿子节点，由place检查其可行性，并以检查其可行性，并以深度优先的方式递归地对可深度优先的方式递归地对可行子树搜索，或减去不可行行子树搜索，或减去不可行子树。子树。12453完全子图完全子图：设无向图设无向图g=(v, e), u v, 若对任意若对任意u, v u, 有有(u,v) e, 则称则称u是是g的一个的一个完全子图完全子图。团团：g的完全子图的完全子图u是是g的一个的一个团团(完备子图完备子图)当且仅当当且仅当u不包含在不包含在g的更大的更大的完全子图中。的完全

41、子图中。最大团最大团：g的的最大团最大团是是g中所含顶点数最多的团。中所含顶点数最多的团。空子图空子图：如果：如果u v,且对任意且对任意u,v u,(u,v ) e, 则称则称u是是g的一个的一个空子图空子图。独立集独立集：g的空子图的空子图u是是g的一个的一个独立集独立集当且仅当当且仅当u不包含在不包含在g的更大的空的更大的空子图中。子图中。g的的最大独立集最大独立集是是g中所含顶点数最多的独立集。中所含顶点数最多的独立集。*若若u是是g的一个的一个完全子图完全子图,则则u是是g的补图的补图 的一个独立集的一个独立集.5.7 最大团问题最大团问题 g问题描述问题描述:在在g g 中找一个最

42、大团中找一个最大团. .例如例如最大团最大团:1, 2, 5, 1, 4, 5, :2, 3, 5g的补图的补图子集子集1，2是不是团？是不是团？子集子集1，2，5是不是团？是不是团？子集子集1，2，4，5是不是团？是不是团？12453子集子集2，4是不是最大独立集？是不是最大独立集？最大独立集最大独立集:2，4子集子集1,2是不是图是不是图 最大独立集？最大独立集？子集子集1,2,5是不是图是不是图 最大独立集？最大独立集？gg设无向图设无向图g=(v, e), |v|=n,用邻接矩阵用邻接矩阵a表示图表示图g, 问题的解可表示为问题的解可表示为n n元向量元向量x1, . xn , x x

43、i i 0,10,1. . 问题的解空间用子集树表示问题的解空间用子集树表示.算法设计与分析算法设计与分析 回溯法回溯法 最大团问题 算法思路算法思路.1011011，2，51，4，52，3，5101101剪枝原则：剪枝原则：约束条件约束条件:x1,x2,.xi xi+1是团是团.目标函数限界目标函数限界:设设 bestn: 已求出的最大团的尺寸已求出的最大团的尺寸; cn : 当前团的尺寸当前团的尺寸 ; r :剩余结点数目剩余结点数目;r=n-i当当 cn+r bestn 时时, 将将cn对应右子树剪去。对应右子树剪去。.1，2，51，4，52，3，50算法设计与分析算法设计与分析 回溯法

44、回溯法 最大团问题 最大团问题的回溯算法最大团问题的回溯算法int maxclique(int * a, int vi,int n) clique y;y.x = new int n+l;y.a= a; /图图g g的邻接矩阵的邻接矩阵y.n= n; /图图g g顶点数顶点数y.cn = 0; /当前团顶点数当前团顶点数y.bestn=0; /当前最大团顶点数当前最大团顶点数y.bestx = v; /当前最优解当前最优解y. backtrack( 1 );delete y. x;return y. bestn； void clique:backtrack(int i) if (in) /找到

45、更大团找到更大团, ,更新更新 for (int j=1; j=n；j+) bestxj = xj; bestn = cn; return; / /检查顶点检查顶点i i是否与当前团相连是否与当前团相连 int ok = 1; /满足加入团的条件满足加入团的条件 for(int j =1; j bestn) /剪右枝条件，否则向右枝递归剪右枝条件，否则向右枝递归 xi=0；backtrack(i + 1); 设当前扩设当前扩展节点展节点z z位于位于解空间树的第解空间树的第i i层，层， 在进入左在进入左子树之前，必子树之前，必须确认从顶点须确认从顶点i i到已入选的到已入选的顶点集中每一顶点

46、集中每一个顶点都有边个顶点都有边相连。相连。 在进入右在进入右子树之前，必子树之前，必须确认还有足须确认还有足够多的可选择够多的可选择的顶点使算法的顶点使算法有可能在右子有可能在右子树中找到更大树中找到更大的团。的团。复杂度分析：复杂度分析：回溯算法回溯算法backtrackbacktrack所需所需的计算时间显的计算时间显然为然为o(n2o(n2n n) )。算法设计与分析算法设计与分析 回溯法回溯法 着色问题图的图的m m色判定问题色判定问题: 给定无向连通图给定无向连通图g和和m种颜色。用这些颜色为图种颜色。用这些颜色为图g的各顶点的各顶点着色着色. 问是否存在着色方法问是否存在着色方法

47、, 使得使得g中任中任2邻接点有不同颜色。邻接点有不同颜色。图的图的m m色优化问题色优化问题: :给定无向连通图给定无向连通图g,为图为图g的各顶点着色的各顶点着色, 使图中任使图中任2邻接点着邻接点着不同颜色不同颜色,问最少需要几种颜色问最少需要几种颜色。所需的最少颜色的数目所需的最少颜色的数目m m称为该图的称为该图的色数色数。5.8 图的图的m m着色问题着色问题 问题描述可平面图：可平面图：如果一个图得所有顶点和边都能用某种方式画在平面上，且没有如果一个图得所有顶点和边都能用某种方式画在平面上，且没有任何两面相交，则称这个图为可平面图。任何两面相交，则称这个图为可平面图。4 4色定理

48、：色定理：若图若图g是可平面图是可平面图,则它的色数不超过则它的色数不超过4色色4 4色定理的应用色定理的应用: :在一个平面或球面上的任何地图能够只用在一个平面或球面上的任何地图能够只用4种颜色来着色使种颜色来着色使得相邻的国家在地图上着有不同颜色得相邻的国家在地图上着有不同颜色4321512345a).a).将将g g的结点按照度数递减的次序排列的结点按照度数递减的次序排列. . b).b).用第一种颜色对第一个结点用第一种颜色对第一个结点着色着色, ,并并按照结点排列的次序按照结点排列的次序 对与前面对与前面着色着色点不邻接的每一点着以相同颜色点不邻接的每一点着以相同颜色. .c).c)

49、.用第二种颜色对尚未用第二种颜色对尚未着色的着色的点重复步骤点重复步骤b).b).用第三种颜色用第三种颜色 继续这种作法继续这种作法, , 直到所有点直到所有点着色完为止着色完为止. . 任意图的着色任意图的着色welch powellwelch powell法法a1a5a4a6a2a3a7a8 排序排序: :a5, a3, a7, a1, a2, a4, a6, a8 着第一色着第一色: a5, a1,着第二色着第二色:a3,a4, a8着第三色着第三色:a7, a2, a6图论图论 对偶图与着色对偶图与着色算法设计与分析算法设计与分析 回溯法回溯法 图的m着色设图设图g=(v, e), |

50、v|=n, 颜色数颜色数= m, 用邻接矩阵用邻接矩阵a表示表示g, 用整数用整数1, 2m来表示来表示m种不同的颜色。顶点种不同的颜色。顶点i所着的颜色用所着的颜色用xi表示。表示。问题的问题的解向量解向量可以表示为可以表示为n元组元组x= x1,.,xn . xi 1,2,.,m,解空间树解空间树为排序树为排序树,是一棵是一棵n+1层的完全层的完全m叉树叉树.在解空间树中做深度优先搜索在解空间树中做深度优先搜索, 约束条件约束条件: xi xj, 如果如果aji=1. 算法思路n=3, m=3n=3, m=3时的解空间树时的解空间树132011101110a=算法设计与分析算法设计与分析

51、回溯法回溯法 着色问题 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; i=n; i+) cout xi ； cout endl ； else for ( int i=1; i=m; i+) xt=i; if (ok(t) backtrack( t+1); bool color:ok(int k)/检查颜色可用性，即

52、约束条件检查颜色可用性，即约束条件 for(int j=1；jn时，算法搜索至叶结点，得到时，算法搜索至叶结点，得到新的新的m着色方案，当前找到的可着色方案，当前找到的可m着色的着色的方案数方案数sum增一增一 当当in时，当前扩展结点时，当前扩展结点z是解空间中是解空间中的内部结点。该结点有的内部结点。该结点有xi=1,2,m共共m个儿子结点。对当前扩展结点个儿子结点。对当前扩展结点z的每一的每一个儿子结点，由函数个儿子结点，由函数ok检查其可行性，检查其可行性，并以深度优先递归地对可行的子树进行并以深度优先递归地对可行的子树进行搜索，或减去不可行的子树搜索，或减去不可行的子树5.9 旅行售

53、货员问题旅行售货员问题 旅行商问题的解空间是一个排列树。如果以旅行商问题的解空间是一个排列树。如果以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

54、= n; i+) 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 & (c

55、c + axn-1xn + axn1 bestc |bestc = noedge) / 找到更优的旅行路径找到更优的旅行路径for (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 0且且n o w j t o t a l j 时，时，nj 在插槽在插槽i 和和i + 1之间有连线。之间有连线。插槽插槽i 和和i

56、 + 1间的线密度可利用该测试方法计算出来。在插槽间的线密度可利用该测试方法计算出来。在插槽k和和k + 1 ( 1ki ) 间的线密度的最大值给出了局部排列的密度。间的线密度的最大值给出了局部排列的密度。 为了实现电路板排列问题的回溯算法，使用了类为了实现电路板排列问题的回溯算法，使用了类b o a r d。函数函数a r r a n g e b o a r d s 返回最优的电路板排列密度，最优返回最优的电路板排列密度，最优的排列由数组的排列由数组bestx 返回。返回。 arrangeboards 创建类创建类board 的一个成员的一个成员x 并初始化与之并初始化与之相关的变量。尤其是相关的变量。尤其是total 被初始化以使被初始化以使totalj 等于等于nj 中电路中电路板的数量。板的数量。now1:n 被置为被置为0，与一个空的局部排列相对应。，与一个空的局部排列相对应。调用调用x .bestorder(1,0) 搜索搜索x1:n 的排列树，以从密度为的排列树，以从密度为0的空的空排列中找到一个最优的排列。排列中找到一个最优的排列。通常，通常，x.bestorder(i,cd) 寻找最优的局部排列寻找最优的