算法设计与分析王红梅第二版第8章_回溯法

1、 在现实世界中，很多问题没有（至少目前没有）有效的算法，在现实世界中，很多问题没有（至少目前没有）有效的算法，这些问题的解只能通过穷举搜索来得到。只有满足约这些问题的解只能通过穷举搜索来得到。只有满足约束条件的解才是可行解，只有满足目标函数的解才是束条件的解才是可行解，只有满足目标函数的解才是最优解，这就有可能避免无效的搜索，提高搜索效率。最优解，这就有可能避免无效的搜索，提高搜索效率。回溯法和分支限界法均属于有组织的系统化搜索技术，可看作回溯法和分支限界法均属于有组织的系统化搜索技术，可看作是穷举搜索的改进。是穷举搜索的改进。蛮力法：生成问题的所有可能解，再去评估是否满足约束条件；蛮力法：生

2、成问题的所有可能解，再去评估是否满足约束条件；回溯法：每次只构造可能解的一部分，然后评估这个部分解，回溯法：每次只构造可能解的一部分，然后评估这个部分解，如果有可能导致一个完整解，则对其进一步构造，否如果有可能导致一个完整解，则对其进一步构造，否则不必继续构造这个部分解。这样可以避免搜索所有则不必继续构造这个部分解。这样可以避免搜索所有的可能解，适用于求解组合数量较大的问题。的可能解，适用于求解组合数量较大的问题。基于搜索的算法设计技术基于搜索的算法设计技术教学重点教学重点回溯法的设计思想，各种经典问题的回溯思想回溯法的设计思想，各种经典问题的回溯思想教学难点教学难点批处理作业调度问题的回溯算

3、法批处理作业调度问题的回溯算法教学内容及目教学内容及目标标知识点知识点教学要求教学要求了解了解理解理解掌握掌握熟练掌握熟练掌握问题的解空间树问题的解空间树回溯法的设计思想回溯法的设计思想回溯法的时间性能回溯法的时间性能图着色问题图着色问题哈密尔顿回路问题哈密尔顿回路问题八皇后问题八皇后问题批处理作业调度问题批处理作业调度问题学习目标本章要点本章要点8.1 概概 述述 8.2 图问题中的回溯法图问题中的回溯法8.3 组合问题中的回溯法组合问题中的回溯法8.1 概概 述述 8.1.1 问题的解空间问题的解空间8.1.2 回溯法的设计思想回溯法的设计思想8.1.3 回溯法的时间性能回溯法的时间性能概

4、述概述 -问题的解空间问题的解空间 概述概述 -问题的解空间问题的解空间 (a) 二维搜索空间无解 (b) 三维搜索空间的解 图8.1 错误的解空间将不能搜索到正确答案概述概述 -问题的解空间问题的解空间 概述概述 -问题的解空间问题的解空间 n回溯法回溯法“可能解可能解”及及“解空间解空间”的表达的表达n 可能解的表示可能解的表示：用：用等长向量等长向量 X=(x1, x2, , xn)，其中分量，其中分量 xi (1in) 的的取值范围取值范围是某个有限集合是某个有限集合 Si=ai1, ai2, , airi，所，所有可能的解向量构成了问题的有可能的解向量构成了问题的解空间解空间。 概述

5、概述 -问题的解空间问题的解空间 n 解空间表达解空间表达：用：用解空间树解空间树（Solution Space Trees）/也称也称状态空间树状态空间树的方式组织：的方式组织：n第第1层层（根结点）：表示搜索的（根结点）：表示搜索的初始状态初始状态n第第2层结点层结点：表示对解向量的第一个分量做出选择后：表示对解向量的第一个分量做出选择后到达的状态到达的状态n第第1层到第层到第2层间层间边上标出对第一个分量选择的结果边上标出对第一个分量选择的结果n依此类推依此类推，从根结点，从根结点叶结点的路径叶结点的路径构成了解空间的一个可能解构成了解空间的一个可能解。n可行解：可行解：满足约束条件的解

6、，满足约束条件的解，解空间中的一个子集解空间中的一个子集n最优解：最优解：使目标函数取极值使目标函数取极值(极大或极小极大或极小)的可行解，一个或少数几个的可行解，一个或少数几个例：例：货郎担问题，有货郎担问题，有nn种可能解。种可能解。n!种可行解，只有一个或种可行解，只有一个或几个是最优解几个是最优解。例：例：背包问题，有背包问题，有2n种可能解，有些是可行解，只有一个或种可能解，有些是可行解，只有一个或几个是最优解几个是最优解n有些问题，只要可行解，不需要最优解有些问题，只要可行解，不需要最优解：例：八皇后问题例：八皇后问题和和图的着色图的着色问题问题概述概述 -问题的解空间问题的解空间

7、 例：对于例：对于n=3 的的0/1 背包问题，其解空间树如图背包问题，其解空间树如图8.2 所示，树中所示，树中的的8个叶子结点分别代表该个叶子结点分别代表该问题的问题的 8 个可能解个可能解。 对物品对物品1的选择的选择对物品对物品3的选择的选择对物品对物品2的选择的选择1111110000000112345781112141531069概述概述 -问题的解空间问题的解空间 例：对于例：对于n=4 的的TSP 问题，图问题，图8.3是是经压缩后的解空间树经压缩后的解空间树，树中的，树中的24 个叶子结个叶子结点分别代表该问题的点分别代表该问题的24 个可能解，例如个可能解，例如结点结点5

8、代表一个可能解，路径为代表一个可能解，路径为 12341，长度为各边代价之和，长度为各边代价之和。 图图8.3 n=4 的的 TSP 问题问题经压缩后经压缩后解空间树解空间树2434223434131424121233121341313123212142414343224341231241345710121517212326283133 37 3942444749525457596264469111416202225273032 363841434648515356586163381319242935404550556021834241123434概述概述 -问题的解空间问题的解空间 8.1

9、概概 述述 8.1.1 问题的解空间问题的解空间8.1.2 回溯法的设计思想回溯法的设计思想8.1.3 回溯法的时间性能回溯法的时间性能回溯法的设计思想回溯法的设计思想 回溯法从根结点出发，按照回溯法从根结点出发，按照深度优先策略遍历深度优先策略遍历解空间树，搜索满足约束条件的解。在搜索至树中解空间树，搜索满足约束条件的解。在搜索至树中任一结点时，先任一结点时，先判断判断该结点对应的部分解是否满足该结点对应的部分解是否满足约束条件约束条件/是否超出是否超出目标函数目标函数的界，也就是判断该结的界，也就是判断该结点是否点是否包含包含问题的（最优）解，问题的（最优）解，如果肯定不包含，如果肯定不包

10、含，则跳过对以该结点为根的子树的搜索，即所谓则跳过对以该结点为根的子树的搜索，即所谓剪枝剪枝（Pruning）；）；否则否则，进入以该结点为根的子树，继，进入以该结点为根的子树，继续按照深度优先策略搜索。续按照深度优先策略搜索。例：对于例：对于n=3 的的0/1 背包问题，其参数如下：背包问题，其参数如下： 重量重量W=20, 15,10，价值价值V=20, 30, 25，背包容量背包容量C=C=25下图是解空间树结构结果，从根结点出发，其搜索过程如下：下图是解空间树结构结果，从根结点出发，其搜索过程如下： 1不可行解不可行解价值价值=20价值价值=55 价值价值=30 价值价值=25价值价值

11、=0111100000011238111214151310697不可行解不可行解回溯法的设计思想回溯法的设计思想X1=1, V1=20C=25-20=5X2=1, W2=15V2=30,C=5X2=0,V=20C=5X3=0,V=20C=5可行解可行解1X1=0, V=0C=25X2=1, V=30C=10可行解可行解2 可行解可行解3可行解可行解4可行解可行解5在在2叉完全树叉完全树中，结点总数有：中，结点总数有：1+21+22+222=151不可行解不可行解价值价值=20价值价值=55 价值价值=30 价值价值=25价值价值=0111100000011238111214151310697不

12、可行解不可行解回溯法的设计思想回溯法的设计思想 1045不可行解不可行解回溯法的设计思想回溯法的设计思想n需要注意的是：需要注意的是： 问题的解空间树是虚拟的问题的解空间树是虚拟的，并不需要在算法运行时构造一，并不需要在算法运行时构造一棵真正的树结构，棵真正的树结构，只需要存储从根结点到当前结点的路径只需要存储从根结点到当前结点的路径。8.1 概概 述述 8.1.1 问题的解空间问题的解空间8.1.2 回溯法的设计思想回溯法的设计思想8.1.3 回溯法的时间性能回溯法的时间性能回溯法的时间性能回溯法的时间性能 一般情况下，在问题的解向量一般情况下，在问题的解向量 X=( x1, x2, , x

13、n )中，分量中，分量 xi (1in) 的取值范围为某个有限集合的取值范围为某个有限集合Si=ai1, ai2, , airi，因此，问题的，因此，问题的解空间由笛卡儿积解空间由笛卡儿积 A=S1S2Sn 构成，并且第构成，并且第 1 层的根结点有层的根结点有|S1| 棵子树，则第棵子树，则第2层共有层共有 |S1| 个结点，第个结点，第 2 层的每个结层的每个结点有点有 |S2| 棵子树，则第棵子树，则第3层共有层共有 |S1|S2| 个结点；个结点； 依此类推依此类推，第，第n+1层共有层共有|S1|S2|Sn| 个结个结点，他们都是点，他们都是叶子结点叶子结点，代表问题的，代表问题的所

14、有可能解所有可能解。在用回溯法求解问题时，常用到在用回溯法求解问题时，常用到两种典型的解空间树两种典型的解空间树： （1）子集树子集树：当问题是从：当问题是从n 个元素的个元素的集合集合中找出中找出满足某种性质满足某种性质的的子集子集时，相应的时，相应的解空间树称为子集树解空间树称为子集树。在子集树中，。在子集树中，|S1|=|S2|=|Sn|=c，即，即每个结点有相同数目的子树每个结点有相同数目的子树，当，当c=2，则子集树中共有则子集树中共有 2n 个叶子结点，因此，遍历子集树需要个叶子结点，因此，遍历子集树需要(2n)时间。如：时间。如：0/1背包背包（2）排列树排列树：当问题是确定：当

15、问题是确定 n 个元素个元素满足某种性质满足某种性质的的排列排列时，时，相应的相应的解空间树称为排列树解空间树称为排列树。在排列树中，通常情况下，。在排列树中，通常情况下，|S1|=n，|S2|=n-1，|Sn|=1，所以，排列树中共有，所以，排列树中共有n! 个叶子结点，因个叶子结点，因此，遍历排列树需要此，遍历排列树需要(n!)时间。时间。如：如：TSP问题问题回溯法的时间性能回溯法的时间性能 回溯法实际上属于蛮力穷举法，当然不能指回溯法实际上属于蛮力穷举法，当然不能指望它有很好的最坏时间复杂性（指数阶）。其有望它有很好的最坏时间复杂性（指数阶）。其有效性往往体现在当问题规模效性往往体现在

16、当问题规模n很大时，在搜索过很大时，在搜索过程中对问题的解空间树大量剪枝。程中对问题的解空间树大量剪枝。但是但是很难估计出在搜索过程中所产生的结点很难估计出在搜索过程中所产生的结点数数，这也是分析回溯法的时间性能的主要困难。，这也是分析回溯法的时间性能的主要困难。回溯法的时间性能回溯法的时间性能 本章要点本章要点8.1 概概 述述 8.2 图问题中的回溯法图问题中的回溯法8.3 组合问题中的回溯法组合问题中的回溯法8.2 图问题中的回溯法图问题中的回溯法 8.2.1 图着色问题图着色问题 8.2.2 哈密顿回路问题哈密顿回路问题图着色问题图着色问题 图着色问题描述为图着色问题描述为：给定无向连

17、通图：给定无向连通图G=(V, E)和和正整数正整数m，求最小的整数，求最小的整数m，当用，当用m种颜色对种颜色对G中的中的顶点着色，使得顶点着色，使得任意两个相邻顶点着色不同任意两个相邻顶点着色不同。 由于用由于用m 种颜色为无向图种颜色为无向图 G=(V, E) 着色，其中，着色，其中，V 的顶的顶点个数为点个数为n，可以用一个，可以用一个 n 元组元组 C=(c1, c2, , cn) 来描述图的一来描述图的一种可能着色，其中，种可能着色，其中，ci1, 2, , m(1in) 表示赋予顶点表示赋予顶点i 的的颜色。颜色。 例如：例如：5 元组元组 (1, 2, 2, 3, 1) 表示对

18、表示对5 个顶点无向图的着色方案之个顶点无向图的着色方案之一，其中：一，其中： 顶点顶点 1: 着颜色着颜色1；顶点顶点 2 : 着颜色着颜色2；顶点顶点 3 : 着颜色着颜色 2 5 元组元组 (1, 3, 2, 3, 1)表示另一种着色方案表示另一种着色方案 如用如用m种颜色给种颜色给n个顶点的图着色，有个顶点的图着色，有mn种可能的着色组合种可能的着色组合图着色问题图着色问题 图着色问题图着色问题 三着色具有三个顶点的图的状态空间树顶点顶点1的的m种着色种着色图着色问题图着色问题 D=1ACBDE1234567891011121314A=1B=2C=3D=3E=1(a) 一个无向图一个无

19、向图 (b) 回溯法搜索空间回溯法搜索空间图图8.8 回溯法求解图着色问题示例回溯法求解图着色问题示例图着色问题图着色问题 顶点顶点设数组colorn表示顶点的着色情况，回溯法求解m着色问题的算法如下： 算法算法8.1图着色问题图着色问题 1将数组colorn初始化为0； 2k=1; 3while (k=1) 3.1 依次考察每一种颜色，若顶点k的着色与其他顶点的着色不发生冲突，则转步骤3.2；否则，搜索下一个颜色； 3.2 若顶点已全部着色，则输出数组colorn，返回； 3.3 否则， 3.3.1 若顶点k是一个合法着色，则k=k+1，转步骤3处理下一个顶点； 3.3.2 否则，重置顶点k

20、的着色情况，k=k-1，转步骤3回溯；图着色问题图着色问题 算法算法8.2 图着色问题图着色问题 void GraphColor (int n, int c , int m) /所有数组下标从所有数组下标从1开始开始 for (i=1; i=1) colork=colork+1; while (colork=m) if Ok(k) break; else colork=colork+1; /搜索下一个颜色搜索下一个颜色 if (colork=m & k= =n) /求解完毕，输出解求解完毕，输出解 for (i=1; i=n; i+) cout=1) 3.1 xk=xk+1，搜索下一个

21、顶点，搜索下一个顶点; 3.2 若若(n个顶点没有被穷举完个顶点没有被穷举完) 执行下列操作执行下列操作 3.2.1 若若(顶点顶点xk不在哈密顿回路上不在哈密顿回路上&(xk-1,xk)E)， 转步骤转步骤3.3; 3.2.2 否则，否则，xk=xk+1，搜索下一个顶点；，搜索下一个顶点； 3.3 若数组若数组 xn已形成哈密顿路径，则输出数组已形成哈密顿路径，则输出数组xn，算法结束；，算法结束； 3.4 否则，否则， 3.4.1 若数组若数组 xn 构成哈密顿路径的部分解，构成哈密顿路径的部分解， 则则 k=k+1，转步骤，转步骤3； 3.4.2 否则，重置否则，重置 xk，k=

22、k-1，取消顶点，取消顶点 xk 的访问标志，的访问标志， 转步骤转步骤3；哈密顿回路问题哈密顿回路问题 算法算法8.4哈密顿回路问题哈密顿回路问题 void Hamiton(int n, int x , int c ) /所有数组下标从所有数组下标从1开始开始 for (i=1; i=1) xk=xk+1; /搜索下一顶点搜索下一顶点 while (xk=1) 3.1 把皇后把皇后k摆放在下一列的位置，即摆放在下一列的位置，即xk+; 3.2 从从xk开始依次考察每一列，如果皇后开始依次考察每一列，如果皇后k摆放在摆放在xk位置不发生冲位置不发生冲突，则转步骤突，则转步骤3.3;否则否则xk

23、+试探下一列试探下一列; 3.3 若若n个皇后已全部摆放，则输出一个解，算法结束；个皇后已全部摆放，则输出一个解，算法结束； 3.4 若尚有皇后没摆放，则若尚有皇后没摆放，则k+，转步骤，转步骤3摆放下一个皇后；摆放下一个皇后； 3.5 若若xk出界，则回溯，出界，则回溯，xk=-1,k-,转步骤转步骤3重新摆放皇后重新摆放皇后k;4. 退出循环，说明退出循环，说明n皇后问题无解；皇后问题无解；C+描述八皇后问题八皇后问题 八皇后问题八皇后问题)(n8.3 组合问题中的回溯法组合问题中的回溯法 8.3.1 八皇后问题八皇后问题 8.3.2 批处理作业调度问题批处理作业调度问题批处理作业调度问题

24、批处理作业调度问题 n 批处理作业调度问题批处理作业调度问题? ? 设有设有n 个作业个作业 1, 2, , n 要在两台机器上处理：要在两台机器上处理： 作业作业i 先先由机器由机器1处理处理( (所需时间为所需时间为ai ) ) 再由再由机器机器2 处理处理 (所需时间为所需时间为bi ) (1in） 批处理作业调度问题批处理作业调度问题： 要求确定这要求确定这n个作业的最优处理顺序，使得从第个作业的最优处理顺序，使得从第1个作业在机器个作业在机器1上处理开始，到最后一个作业在机器上处理开始，到最后一个作业在机器2上处理结束上处理结束所需时间最少所需时间最少。 批处理作业调度问题批处理作业

25、调度问题 作业作业1:2作业作业2:3作业作业3:2空闲空闲:2作业作业1:1机器机器1机器机器2作业作业2:1作业作业3:3(a) 调度方案调度方案(1, 2, 3)，最后，最后完成时间为完成时间为10作业作业1:2作业作业2:3作业作业3:2空闲空闲:2作业作业1:1机器机器1机器机器2作业作业2:1作业作业3:3(b) 调度方案调度方案(1, 3, 2)，最后，最后完成时间为完成时间为8批处理作业调度问题批处理作业调度问题 *作业作业2:3作业作业1:2作业作业3:2空闲空闲作业作业2:1机器机器1机器机器2作业作业1:1作业作业3:3(c) 调度方案调度方案(2, 1, 3)，最后，最后完成时间为完成时间为10作业作业2:3作业作业3:2作业作业1:2空闲空闲:3作业作业2:1机器机器1机器机器2作业作业1:1作业作业3:3(d) 调度方案调度方案(2