《计算机算法设计与分析》PPT第五章 回溯法

1、1第第5章章 回溯法回溯法2n学习要点学习要点理解回溯法的深度优先搜索策略理解回溯法的深度优先搜索策略掌握用回溯法解题的算法框架掌握用回溯法解题的算法框架（1）递归回溯）递归回溯（2）迭代回溯）迭代回溯（3）子集树算法框架）子集树算法框架（4）排列树算法框架）排列树算法框架3n通过应用范例学习回溯法的设计策略通过应用范例学习回溯法的设计策略（1）装载问题）装载问题（2）批处理作业调度）批处理作业调度（3）符号三角形问题）符号三角形问题（4）n后问题后问题（5）0-1背包问题背包问题（6）最大团问题）最大团问题（7）图的）图的m着色问题着色问题（8）旅行售货员问题）旅行售货员问题（9）圆排列问题

2、）圆排列问题（10）电路板排列问题）电路板排列问题（11）连续邮资问题）连续邮资问题4搜索算法介绍搜索算法介绍（1）穷举搜索）穷举搜索（2）盲目搜索）盲目搜索深度优先深度优先(DFS)或回溯搜索或回溯搜索( Backtracking);广度优先搜索广度优先搜索( BFS );分支限界法分支限界法(Branch & Bound)；博弈树搜索博弈树搜索( -Search)（3）启发式搜索）启发式搜索A* 算法和最佳优先算法和最佳优先( Best-First Search )迭代加深的迭代加深的A*算法算法B*, AO*, SSS*等算法等算法Local Search, GA等算法等算法5n

3、搜索空间的三种表示搜索空间的三种表示表序表示表序表示n搜索对象用线性表数据结构表示；搜索对象用线性表数据结构表示；显示图表示显示图表示n搜索对象在搜索前就用图（树）的数据结构表示；搜索对象在搜索前就用图（树）的数据结构表示；隐式图表示隐式图表示n除了初始结点，其他结点在搜索过程中动态生成。除了初始结点，其他结点在搜索过程中动态生成。缘于搜索空间大，难以全部存储。缘于搜索空间大，难以全部存储。6回溯法回溯法n有许多问题，当需要找出它的解集或者要求回答有许多问题，当需要找出它的解集或者要求回答什么解是满足某些约束条件的最优解时，往往要什么解是满足某些约束条件的最优解时，往往要使用回溯法。使用回溯法

4、。n回溯法的基本做法是回溯法的基本做法是搜索搜索，或是一种组织得井井，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。这有条的，能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。种方法适用于解一些组合数相当大的问题。n回溯法回溯法有有“通用解题法通用解题法”之称。之称。7回溯法回溯法n回溯法在问题的解空间树中，按回溯法在问题的解空间树中，按深度优先策略深度优先策略，从根结点，从根结点出发搜索解空间树。算法搜索至解空间树的任意结点时，出发搜索解空间树。算法搜索至解空间树的任意结点时，先判断该结点是否包含问题的解先判断该结点是否包含问题的解。若肯定不包含，则跳过。若

5、肯定不包含，则跳过对以该结点为根的子树的搜索，逐层向其祖先结点回溯；对以该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先搜索策略搜索。否则，进入该子树，继续按深度优先搜索策略搜索。n回溯法求问题的所有解时，要回溯到根，且根结点的所有回溯法求问题的所有解时，要回溯到根，且根结点的所有子树都被搜索遍才结束。在它求问题的一个解时，只要搜子树都被搜索遍才结束。在它求问题的一个解时，只要搜索到问题的一个解就结束。索到问题的一个解就结束。n回溯法回溯法：以深度优先方式系统搜索问题解以深度优先方式系统搜索问题解的算法，它适用的算法，它适用于求解组合数较大的问题。于求解组合数较大

6、的问题。8n回溯法既有系统性又有跳跃性回溯法既有系统性又有跳跃性它在包含问题的所有解的解空间树中，按照深它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间度优先的策略，从根结点出发搜索解空间树。树。系统性系统性算法搜索至解空间树的任一结点时，判断该结算法搜索至解空间树的任一结点时，判断该结点为根的子树是否包含问题的解，如果肯定不点为根的子树是否包含问题的解，如果肯定不包含，则跳过以该结点为根的子树的搜索，逐包含，则跳过以该结点为根的子树的搜索，逐层向其祖先结点回溯。否则，进入该子树，继层向其祖先结点回溯。否则，进入该子树，继续深度优先的策略进行搜索。续深度优先的策略进

7、行搜索。跳跃性跳跃性95.1回溯法的算法框架回溯法的算法框架n复杂问题常常有很多的可能解，这些可能解构成复杂问题常常有很多的可能解，这些可能解构成了问题的解空间。了问题的解空间。n解空间解空间应该应该包括所有的可能解，包括所有的可能解，也就是进行穷举也就是进行穷举的搜索空间的搜索空间。n确定正确的解空间很重要。如果没有确定正确的确定正确的解空间很重要。如果没有确定正确的解空间就开始搜索，可能会增加很多重复解，或解空间就开始搜索，可能会增加很多重复解，或者根本就搜索不到正确的解。者根本就搜索不到正确的解。10例：桌子上有例：桌子上有6根火柴棒，要求以这根火柴棒，要求以这6根火柴棒为边根火柴棒为边

8、搭建搭建4个等边三角形。个等边三角形。11n对于任何一个问题，可能解的对于任何一个问题，可能解的表示方式表示方式和它相应和它相应的的解释解释隐含了解空间及其大小。隐含了解空间及其大小。12例：有例：有n个物品的个物品的0-1背包问题，其可能解的表示方式有两种。背包问题，其可能解的表示方式有两种。（1）可能解由一个不等长向量组成）可能解由一个不等长向量组成 当物品当物品i(1in)装入背包时，解向量中包含分量装入背包时，解向量中包含分量i，否，否 则，解向量中不包含分量则，解向量中不包含分量i。当当n=3时，其解空间：时，其解空间： ( ), (1), (2), (3), (1, 2), (1,

9、 3), (2, 3), (1, 2, 3) （2）可能解由一个等长向量）可能解由一个等长向量x1, x2, , xn组成组成 xi=1(1in)表示物品表示物品i装入背包，装入背包，xi=0表示物品表示物品i没有装没有装入背包。入背包。当当n=3时，其解空间：时，其解空间：(0, 0, 0), (0, 0, 1), (0, 1, 0), (1, 0, 0), (0, 1, 1), (1, 0, 1), (1, 1, 0), (1, 1, 1) 13n为了用回溯法求解一个具有为了用回溯法求解一个具有n个输入的问题，一个输入的问题，一般情况下，将其可能解表示为满足某个约束条件般情况下，将其可能解

10、表示为满足某个约束条件的等长向量的等长向量X=(x1, x2, , xn)，其中分量，其中分量xi (1in)的取值范围是某个有限集合的取值范围是某个有限集合Si=ai1, ai2, , airi。n所有可能的解向量构成了问题的所有可能的解向量构成了问题的解空间解空间。14n问题的解空间一般用问题的解空间一般用解空间树解空间树（Solution Space Trees,也称也称状态空间树状态空间树）的方式组织。）的方式组织。n树的根结点位于第树的根结点位于第1层，表示搜索的初始状态，层，表示搜索的初始状态，第第2层的结点表示对解向量的第一个分量做出选层的结点表示对解向量的第一个分量做出选择后到

11、达的择后到达的状态状态，第，第1层到第层到第2层的边上标出对第层的边上标出对第一个分量一个分量选择的结果选择的结果。依此类推，。依此类推，从树的根结点从树的根结点到叶子结点的路径到叶子结点的路径就构成了解空间的一个就构成了解空间的一个可能解可能解。1516n两类常见的解空间树两类常见的解空间树子集树子集树：当所给的问题是从：当所给的问题是从n个元素的集合个元素的集合S中找出满中找出满足足某种性质的子集某种性质的子集时，相应的解空间树称为子集树。时，相应的解空间树称为子集树。子集树通常有子集树通常有2n个叶子结点，其总结点个数为个叶子结点，其总结点个数为2n+1-1，遍历子集树时间为遍历子集树时

12、间为(2n) 。例：例：0-1背包问题叶结点数为背包问题叶结点数为2n，总结点数，总结点数2n+1-1；排列树排列树：当所给问题是确定：当所给问题是确定n个元素满足个元素满足某种性质的排某种性质的排列列时，相应的解空间树称为排列树。排列树通常有时，相应的解空间树称为排列树。排列树通常有n!个叶子结点，遍历排列树需要个叶子结点，遍历排列树需要(n!)的计算时间。的计算时间。例：例：TSP问题叶结点数为问题叶结点数为n!，遍历时间为，遍历时间为(n!)。17n对于对于n=3的的0/1背包问题，其解空间树如下图所示。背包问题，其解空间树如下图所示。n树中的树中的8个叶子结点分别代表该问题的个叶子结点

13、分别代表该问题的8个可能解。个可能解。18n对于对于n=4的的TSP(旅行售货员旅行售货员)问题，其解空间树如问题，其解空间树如下图所示。树中的下图所示。树中的24个叶子结点分别代表该问题个叶子结点分别代表该问题的的24个可能解。如，结点个可能解。如，结点5代表一个可能解，路代表一个可能解，路径为径为12341，长度为各边代价之和。，长度为各边代价之和。19生成问题状态的基本方法生成问题状态的基本方法n扩展结点扩展结点:一个正在产生儿子的结点称为扩展结点一个正在产生儿子的结点称为扩展结点n活结点活结点:一个自身已生成但其儿子还没有全部生成的节点一个自身已生成但其儿子还没有全部生成的节点称做活结

14、点称做活结点n死结点死结点:一个所有儿子已经产生的结点称做死结点一个所有儿子已经产生的结点称做死结点n深度优先的问题状态生成法：如果对一个扩展结点深度优先的问题状态生成法：如果对一个扩展结点R，一，一旦产生了它的一个儿子旦产生了它的一个儿子C，就把，就把C当做新的扩展结点。在当做新的扩展结点。在完成对子树完成对子树C（以（以C为根的子树）的穷尽搜索之后，将为根的子树）的穷尽搜索之后，将R重重新变成扩展结点，继续生成新变成扩展结点，继续生成R的下一个儿子（如果存在）。的下一个儿子（如果存在）。n宽度优先的问题状态生成法：在一个扩展结点变成死结点宽度优先的问题状态生成法：在一个扩展结点变成死结点之

15、前，它一直是扩展结点。之前，它一直是扩展结点。n回溯法：为了避免生成那些不可能产生最佳解的问题状态，回溯法：为了避免生成那些不可能产生最佳解的问题状态，要不断地利用限界函数要不断地利用限界函数(bounding function)来处死那些来处死那些实际上不可能产生所需解的活结点，以减少问题的计算量。实际上不可能产生所需解的活结点，以减少问题的计算量。具有限界函数的深度优先生成法称为回溯法。具有限界函数的深度优先生成法称为回溯法。205.1.2回溯法的基本思想回溯法的基本思想n基本思想基本思想从开始结点从开始结点(根结点根结点)出发，按照深度优先策略遍历解空出发，按照深度优先策略遍历解空间树，

16、搜索满足约束条件的解。间树，搜索满足约束条件的解。这个开始结点成为这个开始结点成为活结点活结点，同时也成为当前的，同时也成为当前的扩展结点扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为新的活结点，并成为当前扩展结点。这个新结点就成为新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向扩展，则当如果在当前的扩展结点处不能再向纵深方向扩展，则当前扩展结点就成为前扩展结点就成为死结点死结点。此时，应往回移动（回溯）至最近的一个活结点处，并此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当

17、前的扩展结点；直到找到一个解或使这个活结点成为当前的扩展结点；直到找到一个解或全部解。全部解。21n在搜索至树中任一结点时，先判断该结点对应的在搜索至树中任一结点时，先判断该结点对应的部分解是否满足部分解是否满足约束条件约束条件，或者是否超出，或者是否超出目标函目标函数数的界，也就是判断该结点是否的界，也就是判断该结点是否包含包含问题的（最问题的（最优）解，如果肯定不包含，则跳过对以该结点为优）解，如果肯定不包含，则跳过对以该结点为根的子树的搜索，即所谓根的子树的搜索，即所谓剪枝（剪枝（Pruning）；否；否则，进入以该结点为根的子树，继续按照深度优则，进入以该结点为根的子树，继续按照深度优

18、先策略搜索。先策略搜索。22n回溯法的基本步骤回溯法的基本步骤（1）针对所给问题，定义问题的解空间；）针对所给问题，定义问题的解空间；（2）确定易于搜索的解空间结构；）确定易于搜索的解空间结构；（3）以深度优先方式搜索解空间，并在搜索过程中）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。用剪枝函数避免无效搜索。23n回溯法的搜索过程涉及的结点（称为搜索空间）回溯法的搜索过程涉及的结点（称为搜索空间）只是整个解空间树的一部分，在搜索过程中，通只是整个解空间树的一部分，在搜索过程中，通常采用两种策略避免无效搜索：常采用两种策略避免无效搜索：（1）用）用约束条件约束条件剪去得不到可

19、行解的子树；剪去得不到可行解的子树；（2）用）用目标函数目标函数剪去得不到最优解的子树。剪去得不到最优解的子树。这两类函数统称为这两类函数统称为剪枝函数（剪枝函数（Pruning Function）。n需要注意的是，问题的解空间树是虚拟的，并不需要注意的是，问题的解空间树是虚拟的，并不需要在算法运行时构造一棵真正的树结构，只需需要在算法运行时构造一棵真正的树结构，只需要存储从根结点到当前结点的路径。要存储从根结点到当前结点的路径。24例：例：0-1背包问题背包问题n=3, w=( 16, 15, 15), v=( 45, 25, 25), c=30（1） 定义解空间：定义解空间：X=(0,0,

20、0), (0,0,1), (0,1,0), (1,1,0), (1, 1, 1) （2）构造解空间树）构造解空间树25（3）从）从A出发按出发按DFS搜索搜索n=3, w=( 16, 15, 15), v=( 45, 25, 25), c=3026例：例：TSP问题问题（1）定义解空间：）定义解空间：X=12341, 12431, 13241,13421, 14231, 14321（2）构造解空间树）构造解空间树（3）从）从A出发按出发按DFS搜索整棵树搜索整棵树27回溯法的求解过程回溯法的求解过程n由于问题的解向量由于问题的解向量X=(x1, x2, , xn)中的每个分量中的每个分量xi(

21、1in)都属于一个有限集合都属于一个有限集合Si=ai1, ai2, , airi，因此，回溯法，因此，回溯法可以按某种顺序（例如字典序）依次考察笛卡儿积可以按某种顺序（例如字典序）依次考察笛卡儿积S1S2Sn中的元素。中的元素。n初始时，令解向量初始时，令解向量X为空，然后，从根结点出发，选择为空，然后，从根结点出发，选择S1的第一个元素作为解向量的第一个元素作为解向量X的第一个分量，即的第一个分量，即x1=a11，如，如果果X=(x1)是问题的部分解，则继续扩展解向量是问题的部分解，则继续扩展解向量X，选择，选择S2的第一个元素作为解向量的第一个元素作为解向量X的第的第2个分量，否则，选择

22、个分量，否则，选择S1的下一个元素作为解向量的下一个元素作为解向量X的第一个分量，即的第一个分量，即x1=a12。依。依此类推。此类推。28n一般情况下，如果一般情况下，如果X=(x1, x2, , xi)是问题的部分解，则选择是问题的部分解，则选择Si+1的第一个元素作为解向量的第一个元素作为解向量X的第的第i+1个分量时，有下面三种情个分量时，有下面三种情况：况：（1）X=(x1, x2, , xi,xi+1)是问题的是问题的最终解最终解，则输出这个解。如果，则输出这个解。如果问题只希望得到一个解，则结束搜索，否则继续搜索其他解；问题只希望得到一个解，则结束搜索，否则继续搜索其他解；（2）

23、X=(x1, x2, , xi,xi+1)是问题的是问题的部分解部分解，继续构造解向量的下，继续构造解向量的下一个分量；一个分量；（3）X=(x1, x2, , xi,xi+1)既不是问题的部分解也不是问题的最终既不是问题的部分解也不是问题的最终解，存在下面两种情况：解，存在下面两种情况：xi+1=ai1,k不是集合不是集合Si1的最后一个元素，则令的最后一个元素，则令xi+1=ai1,k1，即选择即选择Si+1的下一个元素作为解向量的下一个元素作为解向量X的第的第i+1个分量；个分量；xi+1=ai1,k是集合是集合Si1的最后一个元素，回溯到的最后一个元素，回溯到X=(x1, x2, ,

24、xi)，选择，选择Si的下一个元素作为解向量的下一个元素作为解向量X的第的第i个分量，假设个分量，假设xi=aik，如果，如果aik不是集合不是集合Si的最后一个元素，则令的最后一个元素，则令xi=ai,k1；否则，就继续回溯到否则，就继续回溯到X=(x1, x2, , xi1)；29n用回溯法解题的一个显著特征是用回溯法解题的一个显著特征是在搜索过程中动在搜索过程中动态产生问题的解空间态产生问题的解空间。n在任何时刻，算法只保存从根结点到当前扩展结在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为最长

25、路径的长度为h(n)，则回溯法所需的计算空，则回溯法所需的计算空间通常为间通常为O(h(n)。而显式地存储整个解空间则需。而显式地存储整个解空间则需要要O(2h(n)或或O(h(n)!)内存空间。内存空间。30void backtrack (int t) /搜索到树的第t层/由第t层向第t + 1层扩展，确定xt的值 if (tn) output(x); /叶子结点是可行解 else for (int i=f(n,t);i0) if (f(n,t)=g(n,t) for (int i=f(n,t);in) output(x); else for (int i=0;in) output(x);

26、else for (int i=t;in) / 到达叶结点到达叶结点 for (int j = 1; j= n; j+) bestxj = xj; bestw=cw; /更新最优解更新最优解bestx,bestw return; r-=wi; if (cw+ wibestw) / 搜索右子树搜索右子树 xi=0; backtrack(i+1); r+=wi;39n迭代回溯迭代回溯数组数组x记录了解空间树中从根到当前扩展结点记录了解空间树中从根到当前扩展结点的路径，这些信息已包含了回溯法在回溯时所的路径，这些信息已包含了回溯法在回溯时所需信息。因此利用数组需信息。因此利用数组x所含信息，可将上述

27、所含信息，可将上述回溯法表示成非递归形式。由此可进一步省去回溯法表示成非递归形式。由此可进一步省去O(n)递归栈空间。递归栈空间。算法算法MaxLoading() P149该算法所需的计算时间仍为该算法所需的计算时间仍为O(2n)405.3 n问题描述：略问题描述：略n解表示和解空间：解表示和解空间：n解空间树解空间树41n无限界函数的算法无限界函数的算法42n有限界函数的算法有限界函数的算法基本思想基本思想nr是当前扩展结点是当前扩展结点z的右子树（或左子树）的的右子树（或左子树）的价值上界价值上界ncp是当前价值是当前价值nbestp是当前最优价值是当前最优价值n如如cp+r=bestp，

28、可裁剪掉右子树（或左子，可裁剪掉右子树（或左子树）。树）。43n求经扩展结点求经扩展结点z的可行解价值上界的方法的可行解价值上界的方法计算至扩展结点的当前背包价值计算至扩展结点的当前背包价值 已知已知xi，i=1k-1，当前背包价值，当前背包价值cp=经经z左子树的可行解价值上界左子树的可行解价值上界=cp+左子树上界左子树上界经经z右子树的可行解价值上界右子树的可行解价值上界=cp+右子树上界右子树上界11kiiixv44n有限界函数的算法有限界函数的算法可行性约束函数可行性约束函数：上界函数上界函数：计算右子树中解的上界的更好方法：计算右子树中解的上界的更好方法是将剩余物品依其单位重量价值

29、排序，然后依是将剩余物品依其单位重量价值排序，然后依次装入物品，直至装不下时，再装入该物品的次装入物品，直至装不下时，再装入该物品的一部分而装满背包。由此得到的价值是右子树一部分而装满背包。由此得到的价值是右子树中解的上界。中解的上界。cxwniii145templateTypep Knap:Bound(int i)/ 计算上界计算上界 Typew cleft=c-cw; / 剩余容量剩余容量 Typep b=cp; / 以物品单位重量价值递减序装入物品以物品单位重量价值递减序装入物品 while (i=n & wi=cleft) cleft-=wi; b+=pi; i+; / 装满背

30、包装满背包 if (i half)|(t*(t-1)/2-counthalf) return; /剪枝法，剪除不必要的子树 if (tn) sum+; /到叶子结点，”+”号数和”-”号数相同的符号三角形个数增加1 else for (int i=0;i2;i+) /当前扩展结点Z只有两种可能的取值0或1，即只可能有2个孩子 p1t=i; /二维数据p记录了符号三角形矩阵 count+=i; /当前符号三角形矩阵中，”+”号的个数 for (int j=2;j=t;j+) /从第二行起计算”+”号个数，计算可行性约束 pjt-j+1=pj-1t-j+1pj-1t-j+2; count+=pjt

31、-j+1; Backtrack(t+1); for (int j=2;j=t;j+) /必须回退！因外层for循环是对当前扩展结点两个子树分别搜索！ count-=pjt-j+1; count-=i; 50n复杂度分析复杂度分析计算可行性约束需要计算可行性约束需要O(n)时间，在最坏情况下时间，在最坏情况下有有 O(2n)个结点需要计算可行性约束，故解符个结点需要计算可行性约束，故解符号三角形问题的回溯算法所需的计算时间为号三角形问题的回溯算法所需的计算时间为 O(n2n)。515.5n后问题后问题n问题描述问题描述在在nn格的棋盘上放置格的棋盘上放置彼此不受攻击的彼此不受攻击的n个皇个皇后。

32、按照国际象棋的规后。按照国际象棋的规则，皇后可以攻击与之则，皇后可以攻击与之处在同一行或同一列或处在同一行或同一列或同一斜线上的棋子。同一斜线上的棋子。n后问题等价于在后问题等价于在nn格格的棋盘上放置的棋盘上放置n个皇后，个皇后，任何任何2个皇后不放在同个皇后不放在同一行或同一列或同一斜一行或同一列或同一斜线上。线上。12345678QQQQQQQQ1 2 3 4 5 6 7 852n棋盘的每一行上可以而且必须摆放一个皇后，则棋盘的每一行上可以而且必须摆放一个皇后，则n皇后问皇后问题的可能解用一个题的可能解用一个n元向量元向量X=(x1, x2, , xn)表示，表示，1in且且1xin，即

33、第，即第i个皇后放在第个皇后放在第i行第行第xi列上。列上。n两个皇后不同列，解向量两个皇后不同列，解向量X必须满足必须满足约束条件约束条件1：xixjn若两个皇后摆放的位置分别是若两个皇后摆放的位置分别是(i, xi)和和(j, xj)，在棋盘上斜，在棋盘上斜率为率为-1的斜线上，满足条件的斜线上，满足条件ij=xixj，在棋盘上斜率为，在棋盘上斜率为1的斜线上，满足条件的斜线上，满足条件ij=xixj，综合两种情况，由于两，综合两种情况，由于两个皇后不能位于同一斜线上，所以，解向量个皇后不能位于同一斜线上，所以，解向量X必须满足必须满足约约束条件束条件2：|ixi|jxj|53四皇后问题四

34、皇后问题n问题描述问题描述在在4 x 4棋盘上放上棋盘上放上4个皇后，使皇后彼此不受攻击。不个皇后，使皇后彼此不受攻击。不受攻击的条件是彼此不在同行（列）、斜线上。求出全受攻击的条件是彼此不在同行（列）、斜线上。求出全部的放法。部的放法。n解表示解表示解向量解向量： 4元向量元向量X=(x1,x2,x3,x4)， xi 表示皇后表示皇后i放在放在i行行上的列号，如上的列号，如(3,1,2,4)解空间解空间：(x1,x2,x3,x4)xiS，i=14S=1,2,3,4可行性约束函数可行性约束函数n显约束：显约束： xiS，i=14n隐约束隐约束(i j)：xi xj (不在同一列不在同一列) |

35、ixi|jxj|(不在同一斜线不在同一斜线)54n四皇后问题的解空间树是一棵四皇后问题的解空间树是一棵完全完全4叉树叉树，树的，树的根结点表示搜索的初始状态，从根结点到第根结点表示搜索的初始状态，从根结点到第2层层结点对应皇后结点对应皇后1在棋盘中第在棋盘中第1行的可能摆放位置，行的可能摆放位置，从第从第2层结点到第层结点到第3层结点对应皇后层结点对应皇后2在棋盘中第在棋盘中第2行的可能摆放位置，依此类推。行的可能摆放位置，依此类推。5556n回溯法求解回溯法求解4皇后问题的搜索过程皇后问题的搜索过程57n输出解输出解58bool Queen:Place(int k)/检查xk位置是否合法 f

36、or (int j=1;jn) sum+; else for (int i=1;i=n;i+) xt=i; if (Place(t) Backtrack(t+1); 595.6 图的图的m着色问题着色问题n问题描述问题描述给定无向连通图给定无向连通图G和和m种不同的颜色。用这些种不同的颜色。用这些颜色为图颜色为图G的各顶点着色，每个顶点着一种颜的各顶点着色，每个顶点着一种颜色。是否有一种着色法使色。是否有一种着色法使G中每条边的中每条边的2个顶点个顶点着不同颜色。着不同颜色。这个问题是这个问题是图的图的m可着色判定问题可着色判定问题。若一个图最少需要若一个图最少需要m种颜色才能使图中每条边种颜

37、色才能使图中每条边连接的连接的2个顶点着不同颜色，则称这个数个顶点着不同颜色，则称这个数m为为该图的该图的色数色数。求一个图的色数求一个图的色数m的问题称为图的的问题称为图的m可着色优可着色优化问题。化问题。60n由于用由于用m种颜色为无向图种颜色为无向图G=(V, E)着色，其中，着色，其中，V的顶点个数为的顶点个数为n，可以用一个，可以用一个n元组元组C=(c1, c2, , cn)来描述图的一种可能着色，其中，来描述图的一种可能着色，其中，ci1, 2, , m(1im)表示赋予顶点表示赋予顶点i的颜色。的颜色。例：例：5元组元组(1, 2, 2, 3, 1)表示对具有表示对具有5个顶点

38、的无向个顶点的无向图的一种着色，顶点图的一种着色，顶点1着颜色着颜色1，顶点，顶点2着颜色着颜色2，顶点顶点3着颜色着颜色2，如此等等。，如此等等。如果在如果在n元组元组C中，所有相邻顶点都不会着相同颜中，所有相邻顶点都不会着相同颜色，就称此色，就称此n元组为可行解，否则为无效解。元组为可行解，否则为无效解。61n回溯法求解图着色问题，回溯法求解图着色问题，首先首先把所有顶点的颜色把所有顶点的颜色初始化为初始化为0，然后然后依次为每个顶点着色。在图着依次为每个顶点着色。在图着色问题的解空间树中，如果从根结点到当前结点色问题的解空间树中，如果从根结点到当前结点对应一个部分解，也就是所有的颜色指派

39、都没有对应一个部分解，也就是所有的颜色指派都没有冲突，则在当前结点处选择第一棵子树继续搜索，冲突，则在当前结点处选择第一棵子树继续搜索，也就是为下一个顶点着颜色也就是为下一个顶点着颜色1，否则，对当前子，否则，对当前子树的兄弟子树继续搜索，也就是为当前顶点着下树的兄弟子树继续搜索，也就是为当前顶点着下一个颜色，如果所有一个颜色，如果所有m种颜色都已尝试过并且都种颜色都已尝试过并且都发生冲突，则回溯到当前结点的父结点处，上一发生冲突，则回溯到当前结点的父结点处，上一个顶点的颜色被改变，依此类推。个顶点的颜色被改变，依此类推。62例：判断下图是否是例：判断下图是否是3可着色。可着色。63 n四色猜

40、想四色猜想在一个平面或球面上的任何地图能够只用在一个平面或球面上的任何地图能够只用4种种颜色来着色，使相邻的国家在地图上着不同的颜色来着色，使相邻的国家在地图上着不同的颜色。假设每个国家在地图上是单连通区域，颜色。假设每个国家在地图上是单连通区域，两个国家相邻则其边界长度不为两个国家相邻则其边界长度不为0。右图是一个有右图是一个有5个区域的地图及其相应的平面个区域的地图及其相应的平面图。图。64bool Color:Ok(int k)/检查颜色可用性 for (int j=1;jn) sum+; for (int i=1; i=n; i+) cout xi ; cout endl; else

41、for (int i=1;in) output(x); else for (int i=t;i=n;i+) swap(xt, xi); backtrack(t+1); swap(xt, xi); main(int n)for (int i=t;i=n;i+) xi=i;backtrack(1);n对对n=3的执行情况验证的执行情况验证685.8 旅行售货员问题旅行售货员问题n问题描述问题描述某售货员要到若干城市去推销商品，已知各城某售货员要到若干城市去推销商品，已知各城市之间的路程市之间的路程(或旅费或旅费)。他要选定一条从驻地。他要选定一条从驻地出发，经过每个城市一遍，最后回到驻地的路出发，经过每个城市一遍，最后回到驻地的路线，使总的路程线，使总的路程(或总旅费或总旅费)最小。最小。n基本思想基本思想利用排列生成问题的回溯算法利用排列生成问题的回溯算法Backtrack(2)，对对x=1, 2, , n的的x2.n进行全排列，则进行全排列，则(x1, x2)，(x2, x3)，, (xn, x1)构成构成一个回路。在全排列算法的基础上，进行路径一个回路。在