算法分析与设计-第08章

南京邮电大学计算机学院2020 4 19 算法设计与分析 DesignandAnalysisofAlgorithmsInC 主讲王海艳计算机学院wanghy 南京邮电大学计算机学院2020 4 19 第8章回溯法 基本要求 理解回溯法的算法框架和深度优先搜索策略 掌握状态空间树中结点的生成方法和如何使用剪枝函数来减少实际生成的结点数 并通过范例掌握如何通过搜索状态空间树用回溯法来解决子集和数等典型问题 南京邮电大学计算机学院2020 4 19 学习要点 理解回溯法的深度优先搜索策略理解剪枝函数 约束函数和限界函数 的作用掌握回溯法解题的算法框架 1 递归回溯的算法框架 2 迭代回溯的算法框架 3 蒙特卡罗方法进行效率分析通过应用范例学习回溯法的设计策略 1 n 皇后问题 2 子集和数问题 南京邮电大学计算机学院2020 4 19 8 1一般方法8 2n 皇后8 3子集和数8 4图的着色8 5哈密顿环8 60 1背包8 7批处理作业调度 南京邮电大学计算机学院2020 4 19 8 1一般方法 南京邮电大学计算机学院2020 4 19 8 1 1基本概念 贪心法和动态规划法它们的解都被表示成一个n 元组 x0 x1 xn 1 其中每个分量xi的值取自某个集合Si 所有允许的元组组成一个候选解集 Kruskal所有边 0 1背包问题 x0 x1 xn 1 问题描述中给出用于判定一个候选解是否是可行解的约束条件 边上两个顶点不在同一棵树上 0 1背包问题中的背包载重量 南京邮电大学计算机学院2020 4 19 满足约束条件的候选解称为可行解 目标函数是一个数值函数 用于衡量每个可行解的优劣 最优解 使目标函数取最大 或最小 值的可行解 它们都要求问题最优解具有最优子结构特性 贪心法求解还要求设计最优量度标准 但这并非易事 南京邮电大学计算机学院2020 4 19 对于一个解结构形式为n 元组的问题 如果解的每个分量xi取自一个有限集Si 则可以用穷举法求解 设 Si m 穷举法求解的最坏情况时间复杂度达到O mn 南京邮电大学计算机学院2020 4 19 例8 1排序问题 对n个元素 a0 a1 an 1 进行排序 实质上是求元素下标 0 1 n 1 的一种排列X x0 x1 xn 1 使得 比如 设n 3 对 a0 a1 a2 排序 可能的排列数目为3 6 对 13 24 09 排序 则X x0 x1 x2 2 0 1 对 24 13 09 排序 则X x0 x1 x2 2 1 0 南京邮电大学计算机学院2020 4 19 8 1回溯法的一般方法 回溯法是比贪心法和动态规划法更一般的方法 解为n 元组 x0 x1 xn 1 形式 通过搜索状态空间树来求问题的可行解 满足约束条件 或最优解 使目标函数取最大或最小值 回溯法使用约束函数和限界函数来压缩需要实际生成的状态空间树的结点数 通常情况下 回溯法是为了找出满足约束条件的所有可行解 南京邮电大学计算机学院2020 4 19 问题的解空间 回溯法要求问题的解向量具有n 元组 x1 x2 xn 的形式 每个解分量xi从一个给定的集合Si取值 显式约束 规定每个xi取值的约束条件 显式约束规定了问题的候选解集 解空间 对于问题的一个实例 解向量满足显式约束条件的所有多元组 构成了该实例的一个解空间 通常情况下 回溯法的求解目标是在状态空间树上找出满足约束条件的所有可行解 隐式约束 给出了判定一个候选解是否为可行解的条件 为满足问题的解而对不同分量之间施加的约束 目标函数 代价函数 衡量每个可行解的优劣 使目标函数取最大 或最小 值的可行解为问题的最优解 南京邮电大学计算机学院2020 4 19 例如 例8 1 对n个元素 a0 a1 an 1 进行排序 求元素下标 0 1 n 1 的一种排列X x0 x1 xn 1 使 0 i n 1 一种方法 显式约束 xi Si Si 0 1 n 1 此时解空间大小为nn 隐式约束 0 i n 1 且xi xj i j 另一种方法 显式约束 xi Si Si 0 1 n 1 且xi xj i j 此时解空间大小为n 隐式约束 0 i n 1 注意 同一个问题可以有多种表示 有些表示方法更简单 所需表示的状态空间更小 搜索方法更简单 南京邮电大学计算机学院2020 4 19 有n 个叶结点 解状态 如 例8 1 n个元素排序问题 若n 3则状态空间树为 排序问题一般不用回溯法求解 南京邮电大学计算机学院2020 4 19 又如 0 1背包问题 若n 3则状态空间树为一个完全二叉树 有2n个解状态 南京邮电大学计算机学院2020 4 19 状态空间树 状态空间树 描述问题解空间的树形结构 树中每个结点称为一个问题状态 若从根到树中某个状态的路径代表一个候选解元组 则该状态为解状态 若从根到某个解状态的路径代表一个可行解元组 则该解状态为答案状态 如果求解的是最优化问题 还要用目标函数衡量每个答案结点 找出其中目标函数取最优值的最优答案结点 南京邮电大学计算机学院2020 4 19 穷举法的一般方法 穷举搜索法 使用某种搜索方法 检查状态空间树中每个问题状态 如果是解状态则用判定函数判定它是否是答案结点 对于最优化问题 搜索过程中还需对每个答案结点计算其目标函数值 记录下其中最优者 回溯法适用于解一些组合数相当大的问题 南京邮电大学计算机学院2020 4 19 回溯法的一般方法 采用深度优先产生状态空间树的结点 并使用剪枝函数的方法称为 回溯法 回溯法 在求解的过程中 以深度优先方式逐个生成状态空间树中结点 求问题的可行解或最优解 为提高搜索效率 在搜索过程中用约束函数和限界函数 统称剪枝函数 来剪去不必要搜索的子树 减少问题求解所需实际生成的状态空间树结点数 从而避免无效搜索 常用的剪枝函数 用约束函数剪去已知不含答案状态 可行解 的子树 用限界函数剪去得不到最优答案结点 最优解 的子树 回溯法解题的一个显著特征是 在搜索过程中动态产生问题的解空间 算法搜索至任一结点时 先判断以该结点为根的子树是否包含问题的解 如果肯定不包含 则跳过对该结点为根的子树的搜索 逐层向其祖先结点回溯 否则 进入该子树 继续按深度优先策略搜索 南京邮电大学计算机学院2020 4 19 递归回溯 回溯法对解空间作深度优先搜索 因此 在一般情况下用递归方法实现回溯法 程序8 1递归回溯算法框架voidRBacktrack intk for 每个x k 使得x k T x 0 x k 1 深度优先进入下一层 由于叶结点的孩子集合T 为空集合 因此对于有限状态空间树 算法必能终止 南京邮电大学计算机学院2020 4 19 迭代回溯 采用树的非递归深度优先遍历算法 可将回溯法表示为一个非递归迭代过程 程序8 2迭代回溯算法框架voidIBacktrack intn intk 0 while k 0 if 还剩下尚未检测的x k 使得x k T x 0 x k 1 回溯到上一层 南京邮电大学计算机学院2020 4 19 回溯法的效率分析 用蒙特卡罗 MonteCarlo 方法估计回溯法处理实例时 实际生成的结点数 在状态空间树中 从根开始随机选择一条路径 x0 x1 xn 1 假定搜索树中这条随机选出的路径上 代表部分向量 x0 x1 xk 1 的结点处不受限制的孩子数目 与同层的其他路径上的结点不受限制的孩子数目一样 都是mk 则可以估计整个状态空间树上实际生成的结点数为 m 1 m0 m0m1 m0m1m2 回溯法的时间通常取决于 状态空间树上实际生成的那部分问题状态的数目 即 结点总数 南京邮电大学计算机学院2020 4 19 程序8 3蒙特卡罗算法do SetTypeS x k x k T x 1 x k 1 南京邮电大学计算机学院2020 4 19 显式约束 explicitconstraint 规定每个xi取值的约束条件 回溯法中的基本术语 问题实例的解空间 solutionspace 对给定的一个问题实例 显式约束规定了所有可能的元组 它们组成问题的候选解集 xi 0 即Si 所有非负实数 xi 0或1 即Si 0 1 li xi ui 即Si b li b ui 南京邮电大学计算机学院2020 4 19 隐式约束 implicitconstraint 给出了判定一个候选解是否为可行解的条件 判定函数 一般需要从问题描述的隐式约束出发 设计一个判定函数p x0 x1 xn 1 使得当且仅当p x0 x1 xn 1 为真时 n 元组 x0 x1 xn 1 是问题实例的满足隐式约束的一个可行解 南京邮电大学计算机学院2020 4 19 观点一 显式约束 xi Si Si 0 1 n 1 解空间nn 隐式约束 观点二 显式约束 xi Si Si 0 1 n 1 且xi xj i j 解空间n 隐式约束 南京邮电大学计算机学院2020 4 19 目标函数 也称代价函数 costfunction 用来衡量每个可行解的优劣 使目标函数取最大 或最小 值的可行解为问题的最优解 南京邮电大学计算机学院2020 4 19 状态空间树 statespace 是描述问题解空间的树形结构 问题状态 problemstate 树中每个结点 解状态 solutionstate 从根到树中某个状态的路径代表一个作为候选解的元组 则称该状态为解状态 答案状态 answerstate 从根到某个解状态的路径代表一个作为可行解的元组 则称该解状态为答案状态 南京邮电大学计算机学院2020 4 19 x0 0 图8 1n 3的排序问题的状态空间树 4 6 3 5 2 1 x1 1 x1 2 x2 2 x2 1 x0 1 9 11 8 10 7 x1 0 x1 2 x2 2 x2 0 x0 2 14 16 13 15 12 x1 0 x1 1 x2 1 x2 0 每个结点都是一个问题状态 所有叶结点都是解状态 解状态 X 0 2 1 答案状态 13 24 09 进行排序 X 2 0 1 可以通过搜索状态树寻找答案状态 南京邮电大学计算机学院2020 4 19 8 1 2剪枝函数和回溯法 寻找答案状态可以通过搜索状态空间树寻找答案状态 方法 用深度优先搜索和广度优先搜索来搜索状态空间树 如果某个状态是解状态 则用判定函数判定它是否是答案状态 对于最优化问题 在搜索过程中还要对每个答案结点计算其目标函数值 记录下其中的优胜者 这种遍历状态树的求解方法是穷举法 南京邮电大学计算机学院2020 4 19 状态空间树的生成实际上 状态空间树并不需要事先生成 是在求解过程中 随着搜索算法的进展 逐个动态生成状态空间树的问题状态结点 南京邮电大学计算机学院2020 4 19 对不含答案状态结点 子树 的处理为了提高搜索效率 在搜索过程中使用约束函数 constraintfunction 可以避免无谓地搜索那些已知不含答案状态的子树 如果是最优化问题 还可使用限界函数 boundfunction 剪去那些不可能包含最优答案结点的子树 约束函数和限界函数的目的是相同的 都为了剪去不必要搜索的子树 减少问题求解所需实际生成的状态结点数 它们统称为剪枝函数 pruningfunction 南京邮电大学计算机学院2020 4 19 约束函数设Y是状态空间树中一个问题状态 部分向量 从根到Y的一条路径代表正在构造中的n 元组的一部分 x0 x1 xk 约束函数 是关于部分向量的函数Bk x0 x1 xk 含义 如果可以判定Y的子树上不含任何答案状态 则Bk x0 x1 xk 为false 否则为true 南京邮电大学计算机学院2020 4 19 x0 0 4 6 3 5 2 1 x1 1 x1 2 x2 2 x2 1 x0 1 7 x0 2 14 16 13 15 12 x1 0 x1 1 x2 1 x2 0 图8 1n 3的排序问题的状态空间树 使用约束函数B1 x0 x1 B1 1 0 false 则结点8无需生成 剪去该子树 同理剪去该子树 n个元素排序 有n 个叶结点 解状态 最坏为O n 故一般不用回溯法求解 012例如对 13 24 09 排序 南京邮电大学计算机学院2020 4 19 回溯法和分枝限界法使用剪枝函数的深度优先生成状态空间树中结点的求解方法称为回溯法 backtrack ing 使用剪枝函数的广度优先生成结点的求解方法称为分枝限界法 branch and bound 本章讨论回溯法 下一章讨论分枝限界法 南京邮电大学计算机学院2020 4 19 回溯法的本质是一种深度优先搜索方式 逐一动态生成状态空间树中结点并检测答案结点的方法 不同于穷举搜索 回溯法使用约束函数 剪去那些可以判定不含答案状态的子树 从而提高算法效率 南京邮电大学计算机学院2020 4 19 程序8 1中T的含义 x0 x1 xk 1 是状态空间树上从根到某个问题状态Y的路径 令T x0 x1 xk 1 表示xk可取值的集合 它规定了结点Y有哪些孩子结点 对于xk的每个值 x0 x1 xk 是一条从根到Y的一个孩子Z的路径 若约束函数Bk x0 x1 xk 为真 则要继续检测以Z为根的子树 否则不再生成 T 代表x0所有可取值的集合 如果路径 x0 x1 xk 到达某个叶子结点W 则应为空集 南京邮电大学计算机学院2020 4 19 程序8 1 递归回溯法VoidRBacktrack intk 应以Rbacktrack 0 调用本函数for 每个x k 使得x k T x 0 x k 1 深度优先进入下一层 南京邮电大学计算机学院2020 4 19 程序8 2 迭代回溯法VoidIBacktrack intn intk 0 while k 0 if 还剩下尚未检测的x k 使得x k T x 0 x k 1 回溯到上一层 南京邮电大学计算机学院2020 4 19 8 1 3回溯法的效率分析 p n 是n的多项式 是生成一个结点所需的时间 回溯算法的最坏情况时间复杂度可达O p n n 或O p n 2n 或O p n nn 蒙特卡罗方法 MonteCarlo 通过不受限制的孩子数目估计整个状态空间树上实际生成的结点数 m 1 m0 m0m1 m0m1m2 等介绍过n 皇后问题后 再详细讨论 南京邮电大学计算机学院2020 4 19 8 2n 皇后 南京邮电大学计算机学院2020 4 19 8 2 1问题描述 n 皇后问题要求在一个n n的棋盘上放置n个皇后 使得它们彼此不受 攻击 n 皇后问题要求寻找在棋盘上放置这n个皇后的方案 使得它们中任何两个都不在同一行 同一列或同一斜线上 南京邮电大学计算机学院2020 4 19 01234567 01234567 图8 28 皇后问题的一个可行解 x0 x1 x2 x3 x4 x5 x6 x7 3 5 7 1 6 0 2 4 南京邮电大学计算机学院2020 4 19 一个问题能够用回溯法求解 它的解具有n 元组形式 问题提供显式约束来确定状态空间树 并提供隐式约束来判断可行解 应能设计有效的约束函数 缩小检索空间 8 2 2回溯法求解 南京邮电大学计算机学院2020 4 19 皇后问题可用n 元组 x0 x1 xn 1 表示n 皇后问题的解 其中xi表示第i行的皇后所处的列号 0 xi n 显式约束的一种观点是 Si 0 1 n 1 0 i n 相应的隐式约束为 对任意0 i j n 当i j时 xi xj且 i j xi xj 此时的解空间大小为nn 两皇后不在同一列 两皇后不在同一行 两皇后不在同一斜线 南京邮电大学计算机学院2020 4 19 另一种显式约束观点是 Si 0 1 n 1 0 i n 且xi xj 0 i j n i j 相应的隐式约束为 对任意0 i j n 当i j时 i j xi xj 与此相对应的解空间大小为n 南京邮电大学计算机学院2020 4 19 皇后问题的状态空间树是一棵排列树 排列树有n 个叶结点 遍历排列树的时间为 n 图8 34 皇后问题状态空间树 结点按深度优先遍历编号 受第二种显式约束xi xj的限制 故没有x1 0的分枝 x1 0 南京邮电大学计算机学院2020 4 19 x0 x1 x2 x3 1 3 0 2 x0 x1 x2 x3 2 0 3 1 南京邮电大学计算机学院2020 4 19 8 2 3n 皇后算法 程序8 4 n 皇后问题的回溯算法boolPlace intk inti int x 约束函数 判定两个皇后是否在同一列或在同一斜线上for intj 0 j k j if x j i abs x j i abs j k returnfalse 在同一列或同一斜线 返回falsereturntrue voidNQueens intn int x NQueens 0 n x 南京邮电大学计算机学院2020 4 19 voidNQueens intk intn int x for inti 0 i n i if Place k i x 判断第k个皇后能否放在下标i列 x k i if k n 1 放满n个皇后 输出一个可行解 for i 0 i n i cout x i cout endl elseNQueens k 1 n x 未放满n个皇后 则继续 深度优先进入下一层 南京邮电大学计算机学院2020 4 19 0123 0123 0123 0123 x0 x1 x2 x3 1 3 0 2 x0 x1 x2 x3 2 0 3 1 图8 44 皇后问题的两个可行解 南京邮电大学计算机学院2020 4 19 0123 0123 图8 5回溯法求4 皇后问题的一个可行解 回溯法求4 皇后问题一个可行解的演示 南京邮电大学计算机学院2020 4 19 0123 0123 图8 5回溯法求4 皇后问题的一个可行解 回溯法求4 皇后问题一个可行解的演示 南京邮电大学计算机学院2020 4 19 0123 0123 图8 5回溯法求4 皇后问题的一个可行解 回溯法求4 皇后问题一个可行解的演示 x0 x1 x2 x3 1 3 0 2 南京邮电大学计算机学院2020 4 19 18 1 x0 0 2 31 29 30 19 24 8 3 13 14 15 9 11 x0 1 x1 1 x1 3 x1 2 x2 1 x2 3 x2 2 x3 2 x2 0 16 x1 1 x1 3 x1 2 x2 1 x3 2 图8 6回溯法实际生成的状态空间树的部分 B B B B B B B ans 南京邮电大学计算机学院2020 4 19 1 B ans 回溯法实际生成的状态空间树的过程 受隐式约束 i j时 i j xi xj 的约束函数的限制 结点 是被限制结点 不再往下生成结点 答案结点 可行解 x0 x1 x2 x3 1 3 0 2 受第二种显式约束xi xj的限制 故没有x1 0的分枝 南京邮电大学计算机学院2020 4 19 蒙特卡罗方法 MonteCarlo 基本思想 是在状态空间树中随机选择一条路径 x0 x1 xn 1 设X是这条随机路径上 代表部分向量 x0 x1 xk 1 的结点 如果在X处不受限制的孩子数目是mk 则认为与X同层的其他结点不受限制的孩子数目也都是mk 整个状态空间树上将实际生成的结点数估计为 m 1 m0 m0m1 m0m1m2 m0m1 mk 8 2 4时间分析 南京邮电大学计算机学院2020 4 19 程序8 3 蒙特卡罗算法intEstimate SType x intk 0 m 1 r 1 do SetTypeS x k x k T x 1 x k 1 南京邮电大学计算机学院2020 4 19 估计8 皇后问题状态空间树的实际大小 随机路径 1 3 0 2 4 01234567 01234567 x0可取值的列号有8个 x1有5个 NNN NNNN x2有4个 NNNNN x3有3个 NNNNNN x4有2个 各层不受限制的结点数为 8 5 4 3 2 选择 1 3 0 2 4 路经 状态空间树上实际生成的问题状态数 8 5 4 3 2 1649 1 8 8 5 8 5 4 8 5 4 3 8 5 4 3 2 南京邮电大学计算机学院2020 4 19 估计8 皇后问题状态空间树的实际大小 随机路径 3 5 2 4 6 0 01234567 01234567 Q Q Q Q Q Q 8 5 3 1 2 1 769 随机路径 0 7 5 2 6 1 3 01234567 01234567 8 6 4 2 1 1 1 1401 南京邮电大学计算机学院2020 4 19 估计8 皇后问题状态空间树的实际大小 随机路径 0 2 4 1 3 01234567 01234567 Q 8 6 4 3 2 1977 随机路径 2 5 1 6 0 3 7 4 01234567 01234567 8 5 3 2 2 1 1 1 2329 南京邮电大学计算机学院2020 4 19 这5次试验中实际需要生成的结点数的平均值为1625 8 皇后问题状态空间树的结点总数是 需要实际生成的结点数目大约占总结点数的1 48 南京邮电大学计算机学院2020 4 19 8 3子集和数 南京邮电大学计算机学院2020 4 19 8 3 1问题描述 已知n个不同正数wi 0 i n 1 的集合 求该集合的所有满足条件的子集 使得每个子集中的正数之和等于另一个给定的正数M 例8 2设有n 4个正数的集合W w0 w1 w2 w3 11 13 24 7 和整数M 31 求W的所有满足条件的子集 使得子集中的正数之和等于M 南京邮电大学计算机学院2020 4 19 8 3 2回溯法求解 解结构形式 可变长度元组和固定长度元组 可变长度元组 每个可行解的元组长度可以不同 固定长度元组 每个可行解的元组长度相同 南京邮电大学计算机学院2020 4 19 可变长度元组 x0 xk 1 xk 0 k n 元组的每个分量的取值可以是元素值 也可以是选入子集的正数的下标 11 13 7 24 7 或 0 1 3 2 3 其解的显式约束 xi j j是整数且0 j n 且xi xi 1 0 j n 加入条件xi xi 1可以避免产生重复子集现象 如 1 2 4 和 1 4 2 隐式约束 南京邮电大学计算机学院2020 4 19 图8 8子集和数问题可变元组解的状态空间 0 1 3 11 13 24 7 2 3 0123 按深度优先次序编号 每个问题状态都是一个解状态 代表一个候选解元组 南京邮电大学计算机学院2020 4 19 固定长度n 元组 x0 x1 xn 1 xi 0 1 0 i n xi 0 表示wi未选入子集 xi 1 表示wi选入子集 1 1 0 1 0 0 1 1 其解的显式约束 xi 0 1 0 j n 隐式约束 南京邮电大学计算机学院2020 4 19 x0 1 图8 9子集和数问题固定长度元组解的状态空间树 30 31 28 29 24 25 22 23 16 17 14 15 10 11 8 9 26 27 20 21 12 13 6 7 18 19 4 5 2 3 1 x0 0 x1 1 x1 0 x1 1 x1 0 x2 1 x2 0 x2 1 x2 0 x2 1 x2 0 x2 1 x2 0 x3 1 x3 0 x3 1 x3 0 x3 1 x3 0 x3 1 x3 0 x3 1 x3 0 x3 1 x3 0 x3 1 x3 0 x3 1 x3 0 1 1 0 1 0 0 1 1 按D 检索编号 即BFS 用栈 问题 如何编号 南京邮电大学计算机学院2020 4 19 称这种从n个元素的集合中找出满足某些性质的子集的状态空间树为子集树 子集树有2n个解状态 遍历子集树的时间为 2n 约束函数 Bk x0 x1 xk 为true 当且仅当 要求n个正数wi已经按非减次序排列 前k个元素带权之和s 剩余元素之和r 南京邮电大学计算机学院2020 4 19 x0 x1 1 0 k 2 例如 故要继续考察 x0 x1 的子树 南京邮电大学计算机学院2020 4 19 x0 x1 x2 1 1 1 k 3 再例如 故无需继续考察 x0 x1 x2 的子树 南京邮电大学计算机学院2020 4 19 8 3 3子集和数算法 例8 3设有n 6个正数的集合W 5 10 12 13 15 18 和整数M 30 求W的所有元素之和为M的子集 s k r 0 0 73 5 1 68 0 1 68 x 0 1 x 0 0 15 2 58 5 2 58 x 1 1 x 1 0 012345 南京邮电大学计算机学院2020 4 19 n 6 W 5 10 12 13 15 18 M 30 12 4 33 0 0 73 5 1 68 15 2 58 5 2 58 15 3 46 17 3 46 5 3 46 5 4 33 15 4 33 B A 0 1 68 10 2 58 0 2 58 10 3 46 12 3 46 0 3 46 0 4 33 10 4 33 13 4 33 12 5 18 C x 0 1 x 0 0 x 1 1 x 1 0 x 1 1 x 1 0 x 2 0 x 3 0 x 4 1 0 0 0 0 1 0 0 x 5 1 x 2 1 x 4 0 x 3 0 x 3 1 x 2 1 012345 1 1 0 0 1 1 0 1 1 0 0 1 0 0 1 南京邮电大学计算机学院2020 4 19 程序8 5 见下页 的前置条件 若wi已按非减次序排列 后置条件 在以 x0 x1 xk 为根的子树上搜索答案结点 采用固定长度元组解 每次选择xk之前 应判断约束函数Bk x0 x1 xk 是否为真 假定n个正数wi已按非减次序排列 南京邮电大学计算机学院2020 4 19 程序8 5 子集和数的回溯算法 递归函数voidSumOfSub floats intk floatr int x floatM float w x k 1 if s w k M 得到一个可行解 输出之 for intj 0 j k j cout x j cout endl 南京邮电大学计算机学院2020 4 19 elseif s w k w k 1 M 由于进入第k层之前 总满足前置条件 s wk 1 m且s r m 而进入第n 1层 最后一层 又有r wn 1 因此必有s wn 1 s r m 所以 只要进入第n 1层 函数总能终止 否则不可能进入第n 1层 南京邮电大学计算机学院2020 4 19 非递归函数voidSumOfSub int x intn floatM float w floatr 0 for inti 0 i M s k 南京邮电大学计算机学院2020 4 19 n 6 W 5 10 12 13 15 18 M 30 12 4 33 0 0 73 5 1 68 15 2 58 5 2 58 15 3 46 17 3 46 5 3 46 5 4 33 15 4 33 B A 0 1 68 10 2 58 0 2 58 10 3 46 12 3 46 0 3 46 0 4 33 10 4 33 13 4 33 12 5 18 C x 0 1 x 0 0 x 1 1 x 1 0 x 1 1 x 1 0 x 2 0 x 3 0 x 4 1 0 0 0 0 1 0 0 x 5 1 x 2 1 x 4 0 x 3 0 x 3 1 x 2 1 012345 为何不生成 elseif s w k w k 1 M 30 故不生成左子树 南京邮电大学计算机学院2020 4 19 n 6 W 5 10 12 13 15 18 M 30 12 4 33 0 0 73 5 1 68 15 2 58 5 2 58 15 3 46 17 3 46 5 3 46 5 4 33 15 4 33 B A 0 1 68 10 2 58 0 2 58 10 3 46 12 3 46 0 3 46 0 4 33 10 4 33 13 4 33 12 5 18 C x 0 1 x 0 0 x 1 1 x 1 0 x 1 1 x 1 0 x 2 0 x 3 0 x 4 1 0 0 0 0 1 0 0 x 5 1 x 2 1 x 4 0 x 3 0 x 3 1 x 2 1 012345 为何不生成 if s r w k M s w k 1 M 30 故不生成右子树 南京邮电大学计算机学院2020 4 19 8 4图的着色 南京邮电大学计算机学院2020 4 19 8 4 1问题描述 已知无向图G V E 和m种不同的颜色 如果只允许使用这m种颜色对图G的结点着色 每个结点着一种颜色 问是否存在一种着色方案 使得图中任意相邻的两个结点都有不同的颜色 这就是m 着色判定问题 m colorabilitydecisionproblem 南京邮电大学计算机学院2020 4 19 南京邮电大学计算机学院2020 4 19 8 4 2回溯法求解 设无向图G V E 采用如下定义的邻接矩阵a表示 解的形式 n 元组 x0 x1 xn 1 xi 1 m 0 i n 表示结点i的颜色 这就是显式约束 xi 0表示没有可用的颜色 因此解空间的大小为mn 隐式约束可描述为 如果边 i j E 则xi xj 南京邮电大学计算机学院2020 4 19 约束函数 对所有i和j 0 i j k i j 若a i j 1 则xi xj 南京邮电大学计算机学院2020 4 19 8 4 3图着色算法 程序8 6 图的m着色算法templatevoidMGraph NextValue intk intm int x do x k x k 1 m 1 if x k return 出口1for intj 0 j k j if a k j 南京邮电大学计算机学院2020 4 19 templatevoidMGraph mColoring intk intm int x do NextValue k m x if x k break if k n 1 for inti 0 i n i cout x i cout endl elsemColoring k 1 m x while 1 南京邮电大学计算机学院2020 4 19 templatevoidMGraph mColoring intm int x mColoring 0 m x 南京邮电大学计算机学院2020 4 19 8 4 4时间分析 算法的计算时间上界可由状态空间树的结点数确定 每个结点的处理时间即NextValue的执行时间 为O mn 因此总时间为 南京邮电大学计算机学院2020 4 19 8 5哈密顿环 南京邮电大学计算机学院2020 4 19 8 5 1问题描述 已知图G V E 是一个n个结点的连通图 连通图G的一个哈密顿环 Hamiltonlancycle 是图G的一个回路 它经过图中每个结点 且只经过一次 一个哈密顿环是从某个结点v0 V开始 沿着图G的n条边环行的一条路径 v0 v1 vn 1 vn 其中 vi vi 1 E 0 i n 它访问图中每个结点且只访问一次 最后返回开始结点 即除v0 vn 路径上其余结点各不相同 南京邮电大学计算机学院2020 4 19 南京邮电大学计算机学院2020 4 19 8 5 2哈密顿环算法 对于n个结点的图G V E 的哈密顿环问题 可采用n 元组表示问题的解 x0 x1 xn 1 每个xi 0 1 n 1 0 i n 代表路径上一个结点的编号 这就是显式约束 因此解空间的大小为nn 其隐式约束可描述为 xi xj 0 i j n i j 且 xi xi 1 E xi xi 1 V i 0 1 n 2 又 xn 1 x0 E 哈密顿环问题的分析和求解方法与图的m 着色问题非常相似 南京邮电大学计算机学院2020 4 19 程序8 7 哈密顿环算法templatevoidMGraph NextValue intk int x do x k x k 1 n if x k return if a x k 1 x k for intj 0 j k j if x j x k break if j k if k n 1 k n 1 南京邮电大学计算机学院2020 4 19 templatevoidExtMGraph Hamiltonian intk int x do NextValue k x if x k return if k n 1 for inti 0 i n i cout x i cout 0 n elseHamiltonian k 1 x while 1 南京邮电大学计算机学院2020 4 19 templatevoidExtMGraph Hamiltonian int x Hamiltonian 1 x 南京邮电大学计算机学院2020 4 19 8 7批处理作业调度 南京