第5章-回溯与分支限界

1、1第第5章章 回溯与分支限界回溯与分支限界5.1 回溯算法的基本思想和适用条件回溯算法的基本思想和适用条件5.2 回溯算法的设计步骤回溯算法的设计步骤5.3 回溯算法的效率估计和改进途径回溯算法的效率估计和改进途径5.4 分支限界分支限界 5.4.1 背包问题背包问题 5.4.2 最大团问题最大团问题 5.4.3 货郎问题货郎问题 5.4.4 圆排列问题圆排列问题 5.4.5 连续邮资问题连续邮资问题25.1回溯算法的基本思想和适用条件回溯算法的基本思想和适用条件5.1.1 几个典型例子几个典型例子 四后问题四后问题0-1背包问题背包问题货郎问题（货郎问题（TSP）5.1.2 回溯算法的适用条

2、件回溯算法的适用条件35.1.1几个典型例子几个典型例子例例5.1 n后问题后问题 4后问题：解是一个后问题：解是一个4维向量，维向量，（放置列号）（放置列号） 搜索空间：搜索空间：4叉树叉树 8后问题：解是一个后问题：解是一个8维向量，维向量，搜索空间：搜索空间：8叉树，叉树， 一个解：一个解： 4 实例：实例：V=12,11,9,8, W=8,6,4,3, B=13 结点：向量结点：向量（子集的部分特征向量）（子集的部分特征向量） 搜索空间：搜索空间：子集树子集树，2n片树叶片树叶 可行解：可行解： x1=0, x2=1, x3=1, x4=1. 价值价值:28，重量，重量:13 可行解：

3、可行解： x1=1, x2=0, x3=1, x4=0. 价值价值:21，重量，重量:12例例5.2 0-1背包问题背包问题5 对应于巡回路线：对应于巡回路线：12 4 3 1长度：长度：5+2+7+9=23 例例5.3 货郎问题货郎问题12345249713为巡回路线为巡回路线搜索空间：排列树搜索空间：排列树, (n-1)!片树叶片树叶实例：实例：6回溯算法的基本思想回溯算法的基本思想(1) 适用问题：求解搜索问题和优化问题适用问题：求解搜索问题和优化问题(2) 搜索空间：树，结点对应部分解向量，树叶对应可行解搜索空间：树，结点对应部分解向量，树叶对应可行解(3) 搜索过程：采用系统的方法隐

4、含遍历搜索树搜索过程：采用系统的方法隐含遍历搜索树(4) 搜索策略：深度优先，宽度优先，函数优先，宽深结合等搜索策略：深度优先，宽度优先，函数优先，宽深结合等(5) 结点分支判定条件：结点分支判定条件：满足约束条件满足约束条件-分支扩张解向量分支扩张解向量不满足约束条件，回溯到该结点的父结点不满足约束条件，回溯到该结点的父结点(6) 结点状态：动态生成结点状态：动态生成白结点白结点(尚未访问尚未访问)；灰结点灰结点(正在访问该结点为根的子树正在访问该结点为根的子树); 黑结点黑结点(该结点为根的子树遍历完成该结点为根的子树遍历完成)(7) 存储：当前路径存储：当前路径7设设 P(x1, x2,

5、 , xi) 为真表示向量为真表示向量 满足某个性满足某个性质质 (n后问题中后问题中i 个皇后放置在彼此不能攻击的位置）个皇后放置在彼此不能攻击的位置）多米诺性质：多米诺性质：例例5.4 求不等式的整数解求不等式的整数解 5x1+4x2 x3 10, 1 xi 3, i=1,2,3 P(x1, , xk) : 意味将意味将x1, x2, , xk代入原不等式的相应部分代入原不等式的相应部分使得左边小于等于使得左边小于等于10不满足多米诺性质不满足多米诺性质变换：变换： 令令 x3=3 x3, 5x1+4x2+x3 13 ，1 x1, x2 3, 0 x3 2 nkxxxPxxxPkk 0),

6、.,(),.,(211215.1.2 回溯算法的适用条件回溯算法的适用条件85.2 回溯算法的设计步骤回溯算法的设计步骤(1) 定义搜索问题的解向量和每个分量的取值范围定义搜索问题的解向量和每个分量的取值范围解向量为解向量为 确定确定 xi 的可能取值的集合为的可能取值的集合为 Xi , i = 1, 2, , n. (2) 当当 x1, x2, , xk-1 确定以后计算确定以后计算 xk 取值集合取值集合Sk, Sk Xk (3) 确定结点儿子的排列规则确定结点儿子的排列规则(4) 判断是否满足多米诺性质判断是否满足多米诺性质(5) 搜索策略搜索策略-深度优先、宽度优先等深度优先、宽度优先

7、等(6) 确定每个结点分支约束条件确定每个结点分支约束条件(7) 确定存储搜索路径的数据结构确定存储搜索路径的数据结构9算法算法5.1 ReBack(k) 1. if kn then 是解是解 2. else while Sk do 3. xkSk中最小值中最小值 4. SkSkxk 5. 计算计算Sk+1 6. ReBack(k+1) 算法算法5.2 ReBacktrack(n)输入：输入：n输出：所有的解输出：所有的解 1. for k1 to n 计算计算 Xk 2. ReBack(1) 回溯算法的递归实现回溯算法的递归实现10算法算法5.3 Backtrack(n) 输入：输入：n 输

8、出：所有的解输出：所有的解 1. 对于对于i =1, 2, , n 确定确定Xi 2. k1 3. 计算计算Sk 4. while Sk do 5. xkSk中最小值中最小值; SkSkxk 6. if kn then 7. kk+1; 计算计算Sk 8. else 是解是解 9. if k1 then kk-1； goto 4 回溯算法的迭代实现回溯算法的迭代实现11回溯算法解决问题的步骤回溯算法解决问题的步骤回溯算法也叫试探法，它是一种系统地搜索问题的回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。解的方法。用回溯算法解决问题的一般步骤用回溯算法解决问题的一般步骤：1 针对所给问题，

9、定义问题的解空间，它至少包含针对所给问题，定义问题的解空间，它至少包含问题的一个（最优）解。问题的一个（最优）解。2 确定易于搜索的解空间结构确定易于搜索的解空间结构,使得能用回溯法方便使得能用回溯法方便地搜索整个解空间地搜索整个解空间 。3 以深度优先的方式搜索解空间，并且在搜索过程以深度优先的方式搜索解空间，并且在搜索过程中用中用剪枝函数剪枝函数避免无效搜索。避免无效搜索。 回溯法回溯法的搜索过程涉及的结点（称为的搜索过程涉及的结点（称为搜索空间搜索空间）只是整个解空间树的一部分，在搜索过程中，通常只是整个解空间树的一部分，在搜索过程中，通常采用两种策略避免无效搜索：采用两种策略避免无效搜

10、索：（1）用）用约束条件约束条件剪去得不到剪去得不到可行解可行解的子树；的子树；（2）用）用目标函数目标函数剪去得不到剪去得不到最优解最优解的子树。的子树。这两类函数统称为这两类函数统称为剪枝函数剪枝函数（Pruning Function）。）。v 需要注意的是，问题的解空间树是虚拟的，并不需要注意的是，问题的解空间树是虚拟的，并不需要在算法运行时构造一棵真正的树结构，只需要需要在算法运行时构造一棵真正的树结构，只需要存储从根结点到当前结点的路径。存储从根结点到当前结点的路径。回溯法的求解过程回溯法的求解过程 由于问题的解向量由于问题的解向量X=(x1, x2, , xn)中的每个分量中的每个

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

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

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

14、素，就回溯到X=(x1, x2, , xi)，选择选择Si的下一个元素作为解向量的下一个元素作为解向量X的第的第i个分量，假个分量，假设设xi= aik，如果如果aik不是集合不是集合Si的最后一个元素，则令的最后一个元素，则令xi= aik1；否则，就继续回溯到否则，就继续回溯到X=(x1, x2, , xi1)；例例5 装载问题装载问题例例5.5 n个集装箱装上个集装箱装上2艘载重分别为艘载重分别为c1和和c2的轮船，的轮船，wi为集装为集装箱箱i的重量，且的重量，且问是否存在一种合理的装载方案将问是否存在一种合理的装载方案将n个集装箱装上轮船？如个集装箱装上轮船？如果有，给出一种方案果有

15、，给出一种方案. 求解思路：令第一船装载量为求解思路：令第一船装载量为W1，用回溯算法求使，用回溯算法求使W1-c1达达到最小的装载方案到最小的装载方案， 如果如果 回答回答Yes, 否则回答否则回答No. 问题满足多米诺性质，搜索策略：深度优先问题满足多米诺性质，搜索策略：深度优先 niiccw121211cWwnii 算法算法算法算法5.4 Loading (W,c1), 输入：集装箱重量输入：集装箱重量W=, c1是第一条船的载重是第一条船的载重输出：使第一条船装载最大的方案输出：使第一条船装载最大的方案，其中，其中xi=0,11. Sort(W); /对对w1,w2,wn按照从大到小排

16、序按照从大到小排序2. B ; best ; i 1; 3. while i n do 4. if 装入装入 i 后重量不超过后重量不超过c15. then B B wi; xi 1; i i+1; 6.else xi0; i i+1; 7.ifB1 and xi=0 do2. i i 1;3. if xi=1 4. then xi0; BB+wi; ii+1; 实例实例 W=, c1=152, c2=130复杂性：复杂性：W(n)=O(2n)00101290002040308000例例6 图的着色问题图的着色问题例例5.6 着色问题：给定无向连通图着色问题：给定无向连通图G和和m种颜色，用这

17、些颜色种颜色，用这些颜色给图的顶点着色，每个顶点一种颜色给图的顶点着色，每个顶点一种颜色. 要求是：要求是：G 的每条边的的每条边的两个顶点着不同颜色两个顶点着不同颜色. 给出所有可能的着色方案；如果不存在给出所有可能的着色方案；如果不存在着这样的方案，则回答着这样的方案，则回答“No”. 则搜索空间为深度则搜索空间为深度n 的的m叉完全树叉完全树. 将颜色编号为将颜色编号为1,2,m， 结点结点：x1, x2, , xk 1, 2, ., m, 1 k n，表示顶表示顶点点1着颜色着颜色 x1，顶点，顶点2着颜色着颜色 x2，顶点，顶点 k 着颜色着颜色 xk. 约束条件：该顶点邻接表中的顶

18、点与该顶点没有同色；约束条件：该顶点邻接表中的顶点与该顶点没有同色；搜索策略：深度优先搜索策略：深度优先时间：时间：O(nmn)19实例实例12332131231213220提高效率的途径提高效率的途径根据对称性，只需搜索根据对称性，只需搜索1/3的解空间即可的解空间即可. 当当1和和2确定确定,即即以后，只有以后，只有1个解，因此在个解，因此在为根的子树中也只有为根的子树中也只有1个解个解.由于由于3个子树的对称性，总共有个子树的对称性，总共有6个解个解.进一步分析，在取定进一步分析，在取定以后，不可以扩张成以后，不可以扩张成, 因为因为可以检查是否有和可以检查是否有和1,2,3都相邻的顶点

19、都相邻的顶点.如果存在如果存在,例如例如7, 则没则没有解有解. 所以可以从打叉的结点回溯，而不必搜索它的子树所以可以从打叉的结点回溯，而不必搜索它的子树.21 5.3 回溯算法的效率估计回溯算法的效率估计 与改进途径与改进途径Monte Carlo(蒙特卡罗蒙特卡罗)方法估计搜索树中的结点，方法估计搜索树中的结点，背景：蒙特卡罗方法于背景：蒙特卡罗方法于20世纪世纪40年代美国在年代美国在第二次世界大第二次世界大战中研制原子弹战中研制原子弹的的“曼哈顿计划曼哈顿计划”计划的成员乌拉姆和计划的成员乌拉姆和冯冯诺伊曼首先提出。数学家冯诺伊曼首先提出。数学家冯诺伊曼用驰名世界的赌诺伊曼用驰名世界的

20、赌城城摩纳哥的摩纳哥的Monte Carlo 1从根开始，随机选择一条路经，直到不能分支为止从根开始，随机选择一条路经，直到不能分支为止, 即从即从x1,x2, 依次对依次对xi 赋值，每个赋值，每个xi 的值是从当时的的值是从当时的 Si中随机选取，直到向量不能扩张为止中随机选取，直到向量不能扩张为止. 2假定搜索树的其他假定搜索树的其他 | Si | 1 个分支与以上随机选出的个分支与以上随机选出的 路径一样，计数搜索树的点数路径一样，计数搜索树的点数. 3重复步骤重复步骤 1 和和 2，将结点数进行概率平均，将结点数进行概率平均.22算法算法5.6 Monte Carlo 输入：输入：n

21、,t 为正整数，为正整数，n为皇后数，为皇后数，t为抽样次数为抽样次数输出：输出：sum, 即即t 次抽样路径长度的平均值次抽样路径长度的平均值 1sum 0 /sum为为 t 次结点平均数次结点平均数 2for i 1 to t do /取样次数取样次数 t 3. m Estimate(n) /m为本次结点总数为本次结点总数 4. sum sum + m 5. sum sum / t 算法实现算法实现23m为输出为输出本次取样结点总数，本次取样结点总数，k 为层数，为层数，r1为本层为本层分支数分支数, r2为上层分支数，为上层分支数，n为树的层数为树的层数算法算法5.7 Estimate(

22、n) 1. m1; r21; k1 /m为结点总数为结点总数 2. While k n do 3. if Sk= then return m 4. r1 |Sk|*r2 /r1为扩张后结点总数为扩张后结点总数 5. m m + r1 / r2为扩张前结点总数为扩张前结点总数 6. xk 随机选择随机选择 Sk 的元素的元素 7. r2 r1 8. k k+1 子过程子过程24估计四后搜索树的结点数估计四后搜索树的结点数case1：1+4+4 2+4 2=21case2: 4 4+1=17case3：1+4 1+4 2=13 实例实例Case3: Case1: Case2: 25估计结果估计结果

23、假设假设 4 次抽样测试：次抽样测试： case1:1次，次，case2:1次，次，case3:2次，次， 平均结点数平均结点数(211+171+132)/4=16 搜索空间访问的结点数为搜索空间访问的结点数为17搜索空间搜索空间26影响算法效率的因素影响算法效率的因素最坏情况下的时间最坏情况下的时间W(n)=(p(n)f(n) 其中其中 p(n) 为每个结点时间，为每个结点时间，f(n)为结点个数为结点个数 影响回朔算法效率的因素影响回朔算法效率的因素 （1）搜索树的结构）搜索树的结构 分支情况：分支均匀否、分支情况：分支均匀否、 树的深度：树的深度： 对称程度：对称适合裁减对称程度：对称适

24、合裁减 （2）解的分布）解的分布 在不同子树中分布多少是否均匀在不同子树中分布多少是否均匀 分布深度分布深度 （3）约束条件的判断：计算简单）约束条件的判断：计算简单27（1）根据树分支设计优先策略：）根据树分支设计优先策略： 结点少的分支优先，解多的分支优先结点少的分支优先，解多的分支优先（2）利用搜索树的对称性剪裁子树）利用搜索树的对称性剪裁子树（3）分解为子问题）分解为子问题: 求解时间求解时间 f(n)=c2n，组合时间，组合时间T=O(f(n) 如果分解为如果分解为 k 个子问题，每个子问题大小为个子问题，每个子问题大小为 n/k 求解时间为求解时间为 Tkckn 2改进途径改进途径

25、分支限界法（分支分支限界法（分支+限界）限界）常以广度优先或以最小耗费（最常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。大效益）优先的方式搜索问题的解空间树。分支：分支：按广度优先的策略进行搜索按广度优先的策略进行搜索限界：限界：为加快搜索速度而采用启发式信息剪枝的策略为加快搜索速度而采用启发式信息剪枝的策略组合优化问题的相关概念组合优化问题的相关概念目标函数目标函数（极大化或极小化）（极大化或极小化）约束条件约束条件搜索空间中满足约束条件的解称为搜索空间中满足约束条件的解称为可行解可行解使得目标函数达到极大使得目标函数达到极大(或极小或极小)的解称为的解称为最优解最优解2

26、85.4 分支限界分支限界29分支限界技术（极大化）分支限界技术（极大化）设立设立代价函数代价函数函数值以该结点为根的搜索树中的所有可行解的目标函函数值以该结点为根的搜索树中的所有可行解的目标函数值的上界数值的上界父结点的代价不小于子结点的代价父结点的代价不小于子结点的代价设立设立界界代表当时已经得到的可行解的目标函数的最大值代表当时已经得到的可行解的目标函数的最大值界的设定初值可以设为界的设定初值可以设为0可行解的目标函数值大于当时的界，进行更新可行解的目标函数值大于当时的界，进行更新搜索中停止分支的依据搜索中停止分支的依据不满足约束条件或者其代价函数小于当时的界不满足约束条件或者其代价函数

27、小于当时的界 30实例：布线问题实例：布线问题印刷电路板将布线区域划分成印刷电路板将布线区域划分成n X m个方格如图所个方格如图所示。精确的电路布线问题要求确定连接方格示。精确的电路布线问题要求确定连接方格a的中的中点到方格点到方格b的中点的最短布线方案。在布线时，电的中点的最短布线方案。在布线时，电路只能沿直线或直角布线。为了避免线路相交，已路只能沿直线或直角布线。为了避免线路相交，已布了线的方格做了封锁标记，其它线路不允穿过被布了线的方格做了封锁标记，其它线路不允穿过被封锁的方格。封锁的方格。31背包问题的实例：背包问题的实例： 4 , 3 , 2 , 1,N107432953max43

28、214321 ixxxxxxxxxi对变元重新排序使得对变元重新排序使得11 iiiiwvwv4 , 3 , 2 , 1,N102347359max43214321 ixxxxxxxxxi实例：背包问题实例：背包问题排序后实例排序后实例 32结点结点 的代价函数的代价函数 否否则则有有若若对对某某个个 kiiijkiiikikkiikiiixvwxwbkjwvxwbxv111111)( 分支策略分支策略-深度优先深度优先 代价函数与分支策略确定代价函数与分支策略确定3383/3210 x2=273/339 04 , 3 , 2 , 1,N,102347359max43214321 ixxxxx

29、xxxxi07/910 74/539 x1=115x2=211 116x2=313272/139 01012104/510 x1=043/365 103/310 0wv实实例例345.4.2 最大团问题最大团问题例例5.9 最大团问题：给定无向图最大团问题：给定无向图G=, 求求G中的最大团中的最大团. 相关知识：相关知识： 无向无向图图G = , G的的子图子图：G= , 其中其中V V, E E, G的的补图补图： =, E是是E关于完全图边集的补集关于完全图边集的补集 G中的中的团团：G 的完全子图的完全子图 G 的的点独立集点独立集：G 的顶点子集的顶点子集A，且，且 u,v A, u

30、,v E. 最大团最大团：顶点数最多的团：顶点数最多的团 最大点独立集最大点独立集：顶点数最多的点独立集：顶点数最多的点独立集命题：命题：U是是G 的最大团当且仅当的最大团当且仅当U是是 的最大点独立集的最大点独立集 35结点结点的含义：的含义： 已检索已检索 k 个顶点，其中个顶点，其中 xi=1 对应的顶点在当前的团内对应的顶点在当前的团内搜索树为子集树搜索树为子集树约束条件：该顶点与当前团内每个顶点都有边相连约束条件：该顶点与当前团内每个顶点都有边相连界：当前图中已检索到的极大团的顶点数界：当前图中已检索到的极大团的顶点数代价函数：目前的团扩张为极大团的顶点数上界代价函数：目前的团扩张为

31、极大团的顶点数上界 F = Cn+n k 其中其中 Cn 为目前团的顶点数（初始为为目前团的顶点数（初始为0），）， k 为结点层数为结点层数时间：时间：O(n2n)算法设计算法设计3623514顶点编号顺序为顶点编号顺序为 1, 2, 3, 4, 5,对应对应 x1, x2, x3, x4, x5, xi=1 当且仅当当且仅当 i 在团内在团内 分支规定左子树为分支规定左子树为1，右子树为，右子树为0. B 为界，为界，F 为代价函数值为代价函数值.最大团的实例最大团的实例37a：得第一个极大团：得第一个极大团 1, 2, 4 , 顶点数为顶点数为3, 界为界为3；b：代价函数值：代价函数值

32、 F = 3, 回溯；回溯；c：得第二个极大团：得第二个极大团1, 3, 4, 5, 顶点数为顶点数为4, 修改界为修改界为4；d：不必搜索其它分支：不必搜索其它分支, 因为因为F = 4, 不超过界；不超过界；e：F = 4, 不必搜索不必搜索.最大团为最大团为 1, 3, 4, 5, 顶点数为顶点数为 4. 23514实例求解实例求解a,B=3 b,F=3c,B=4d,F=4e,F=4TSP问题问题 TSPTSP问题是指旅行家要旅行问题是指旅行家要旅行n n个城市，要求各个城个城市，要求各个城市经历且仅经历一次然后回到出发城市，并要求所走市经历且仅经历一次然后回到出发城市，并要求所走的路程

33、最短。的路程最短。271563134253984C= 3 1 5 8 3 6 7 9 1 6 4 2 5 7 4 3 8 9 2 3 (a) 一个无向图一个无向图 (b) 无向图的代价矩阵无向图的代价矩阵图图9.4 无向图及其代价矩阵无向图及其代价矩阵 采用贪心法求得近似解为采用贪心法求得近似解为135421，其路径，其路径长度为长度为1+2+3+7+3=16，这可以作为，这可以作为TSP问题的上界。问题的上界。 把矩阵中每一行最小的元素相加，可以得到一个简单的把矩阵中每一行最小的元素相加，可以得到一个简单的下界，其路径长度为下界，其路径长度为1+3+1+3+2=10，但是还有一个信息量，但是

34、还有一个信息量更大的下界：考虑一个更大的下界：考虑一个TSP问题的完整解，在每条路径上，问题的完整解，在每条路径上，每个城市都有两条邻接边，一条是进入这个城市的，另一每个城市都有两条邻接边，一条是进入这个城市的，另一条是离开这个城市的，那么，如果把矩阵中每一行最小的条是离开这个城市的，那么，如果把矩阵中每一行最小的两个元素相加再除以两个元素相加再除以2，如果图中所有的代价都是整数，再，如果图中所有的代价都是整数，再对这个结果向上取整，就得到了一个合理的下界。对这个结果向上取整，就得到了一个合理的下界。 lb=(1+3)+(3+6)+(1+2)+(3+4)+(2+3)/2=14 于是，得到了目标

35、函数的界于是，得到了目标函数的界14, 16。需要强调的是，这个解并不是一个合法的选择（可能没有需要强调的是，这个解并不是一个合法的选择（可能没有构成哈密顿回路），它仅仅给出了一个参考下界。构成哈密顿回路），它仅仅给出了一个参考下界。 部分解的目标函数值的计算方法部分解的目标函数值的计算方法 例如图例如图9.4所示无向图，如果部分解包含边所示无向图，如果部分解包含边(1, 4)，则该部分，则该部分解的下界是解的下界是lb=(1+5)+(3+6)+(1+2)+(3+5)+(2+3)/2=16。 UrUrji1k1i1iiij2/ )rrrrc2(lb行最小的两个元素素行不在路径上的最小元2715

36、63134253984C= 3 1 5 8 3 6 7 9 1 6 4 2 5 7 4 3 8 9 2 3 (a) 一个无向图一个无向图 (b) 无向图的代价矩阵无向图的代价矩阵图图9.4 无向图及其代价矩阵无向图及其代价矩阵412lb=142356781startlb=1413lb=1414lb=1615lb=1923lb=1624lb=1625lb=1932lb=1634lb=1535lb=149101152lb=1954lb=14141542lb=161742lb=1845lb=15121352lb=2016分支限界法求解分支限界法求解TSP问题示例问题示例425.4.3 货郎问题货郎问

37、题例例5.10 货郎问题：给定货郎问题：给定n个城市集合个城市集合C=c1,c2,cn, 从一个城从一个城市到另一个城市的距离市到另一个城市的距离 dij 为正整数，求一条最短且每个城为正整数，求一条最短且每个城市恰好经过一次的巡回路线市恰好经过一次的巡回路线. 货郎问题的类型：有向图、无向图货郎问题的类型：有向图、无向图. 设巡回路线从设巡回路线从1开始，开始，解向量为解向量为, 其中其中 i1, i2, , in-1为为 2, 3, , n 的排列的排列. 搜索空间为排列树，结点搜索空间为排列树，结点 表示得到表示得到 k 步路线步路线1234524971343Biiik1jjjjklld

38、L为部分巡回路线扩张成全程巡回路线的长度下界为部分巡回路线扩张成全程巡回路线的长度下界时间时间 O(n!)：计算：计算O(n 1)!)次，代价函数计算次，代价函数计算O(n)约束条件约束条件：令：令B = i0=1, i1, i2, , ik , 则则 ik+1 2, , n B界界：当前得到的最短巡回路线长度：当前得到的最短巡回路线长度代价函数代价函数L：设顶点：设顶点 ci 出发的最短边长度为出发的最短边长度为 li，dj 为选为选定巡回路线中第定巡回路线中第 j 段的长度，则段的长度，则算法设计算法设计445.4.4 圆排列问题圆排列问题例例5.11 圆排列问题：给定圆排列问题：给定n个

39、圆的半径序列个圆的半径序列, 将各圆与将各圆与矩形底边相切排列矩形底边相切排列, 求具有最小长度求具有最小长度 ln 的圆的排列顺序的圆的排列顺序.解为解为为为1, 2, , n的的排列，解空间为排列树排列，解空间为排列树. 部分解向量部分解向量 ：表示：表示前前 k 个圆已排好个圆已排好. 令令B= i1, i2, , ik ,下一个圆选择下一个圆选择ik+1. 约束条件：约束条件：ik+1 1, 2, , n B界：当前得到的最小园排列长度界：当前得到的最小园排列长度45 k：算法完成第：算法完成第 k 步，已经选择了第步，已经选择了第1 k 个圆个圆 rk：第：第 k 个圆的半径个圆的半径 dk：第：第 k 1 个圆到第个圆到第 k 个圆的圆心水平距离，个圆的圆心水平距离，k1 xk：第：第 k 个圆的圆心坐标，规定个圆的圆心坐标，规定 x1=0, lk： 第第 1 k 个圆的排列长度个圆的排列长度 Lk：放好：放好 1k 个圆以后，对应结点的代价函数值个圆以后，对应结点的代价函数值 Lk ln代价函数符号说明代价函数符号说明46112111212.22.rrrrrrrrxrrdddxLnnnkkkkknnkk