《算法设计与分析》第章

《《算法设计与分析》第章》由会员分享，可在线阅读，更多相关《《算法设计与分析》第章（54页珍藏版）》请在金锄头文库上搜索。

1、 8 1一般方法8 2n 皇后8 3子集和数8 4图的着色8 5哈密顿环8 60 1背包8 7批处理作业调度 第8章回溯法 8 1 1基本概念 规定每个xi取值的约束条件称为显式约束 explicitconstraint 对给定的一个问题实例 显式约束规定了所有可能的元组 它们组成问题的候选解集 被称为该问题实例的解空间 solutionspace 隐式约束 implicitconstraint 给出了判定一个候选解是否为可行解的条件 8 1一般方法 目标函数 也称代价函数 costfunction 用来衡量每个可行解的优劣 使目标函数取最大 或最小 值的可行解为问题的最优解 状态空间树 st

2、atespace 是描述问题解空间的树形结构 树中每个结点称为一个问题状态 problemstate 如果从根到树中某个状态的路径代表一个作为候选解的元组 则称该状态为解状态 solutionstate 如果从根到某个解状态的路径代表一个作为可行解的元组 则称该解状态为答案状态 answerstate 8 1 2剪枝函数和回溯法 为了提高搜索效率 在搜索过程中使用约束函数 constraintfunction 可以避免无谓地搜索那些已知不含答案状态的子树 如果是最优化问题 还可使用限界函数 boundfunction 剪去那些不可能包含最优答案结点的子树 约束函数和限界函数的目的是相同的 都为

3、了剪去不必要搜索的子树 减少问题求解所需实际生成的状态结点数 它们统称为剪枝函数 pruningfunction 使用剪枝函数的深度优先生成状态空间树中结点的求解方法称为回溯法 backtracking 广度优先生成结点 并使用剪枝函数的方法称为分枝限界法 branch and bound 程序8 1 递归回溯法VoidRBacktrack intk 应以Rbacktrack 0 调用本函数for 每个x k 使得x k T x 0 x k 1 程序8 2 迭代回溯法VoidIBacktrack intn intk 0 while k 0 if 还剩下尚未检测的x k 使得x k T x 0

4、x k 1 8 1 3回溯法的效率分析 回溯算法的最坏情况时间复杂度可达O p n n 或O p n 2n 或O p n nn 这里p n 是n的多项式 是生成一个结点所需的时间 蒙特卡罗方法 MonteCarlo 这种估计方法的基本思想是在状态空间树中随机选择一条路径 x0 x1 xn 1 设X是这条随机路径上 代表部分向量 x0 x1 xk 1 的结点 如果在X处不受限制的孩子数目是mk 则认为与X同层的其他结点不受限制的孩子数目也都是mk 整个状态空间树上将实际生成的结点数估计为m 1 m0 m0m1 m0m1m2 程序8 3 蒙特卡罗算法intEstimate SType x intk

5、 0 m 1 r 1 do SetTypeS x k x k T x 1 x k 1 8 2 1问题描述 n 皇后问题要求在一个n n的棋盘上放置n个皇后 使得它们彼此不受 攻击 n 皇后问题要求寻找在棋盘上放置这n个皇后的方案 使得它们中任何两个都不在同一行 同一列或同一斜线上 8 2n 皇后 8 2 2回溯法求解 皇后问题可用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且 此时的解空间大小为nn 另一种显式约束的观

6、点是 Si 0 1 n 1 0 i n 且xi xj 0 i j n i j 相应的隐式约束为 对任意0 i j n 当i j时 与此相对应的解空间大小为n 皇后问题的状态空间树是一棵排列树 排列树有n 个叶结点 遍历排列树的时间为 n 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 returntrue voidNQueens intn int x NQueens 0 n x voi

7、dNQueens intk intn int x for inti 0 i n i if Place k i x x k i if k n 1 for i 0 i n i cout x i cout endl elseNQueens k 1 n x 8 2 4时间分析 可通过计算得到这5次试验中实际需要生成的结点数的平均值为1625 8 皇后问题状态空间树的结点总数是 因此 需要实际生成的结点数目大约占总结点数的1 55 8 3 1问题描述 已知n个不同正数wi 0 i n 1 的集合 求该集合的所有满足条件的子集 使得每个子集中的正数之和等于另一个给定的正数M 例8 2设有n 4个正数的集合

8、W w0 w1 w2 w3 11 13 24 7 和整数M 31 求W的所有满足条件的子集 使得子集中的正数之和等于M 8 3子集和数 8 3 2回溯法求解 解结构形式 可变长度元组和固定长度元组 可变长度元组 x0 xk 1 xk 0 k n 元组的每个分量的取值可以是元素值 也可以是选入子集的正数的下标 固定长度n 元组 x0 x1 xn 1 xi 0 1 0 i n xi 0 表示wi未选入子集 xi 1 表示wi入选子集 称这种从n个元素的集合中找出满足某些性质的子集的状态空间树为子集树 子集树有2n个解状态 遍历子集树的时间为 2n 约束函数 Bk x0 x1 xk 为true 当且

9、仅当 8 3 3子集和数算法 程序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 elseif s w k w k 1 m 例8 3设有n 6个正数的集合W 5 10 12 13 15 18 和整数M 30 求W的所有元素之和为M的子集 8 4 1问题描述 已知无向图G V E 和m种不同的颜色 如果只允许使用这m种颜色对图G的结点着色 每个结点着一种颜色 问是否存在一种着色方案 使得图中任意相邻的两个结点

10、都有不同的颜色 这就是m 着色判定问题 m colorabilitydecisionproblem 8 4图的着色 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 约束函数 对所有i和j 0 i j k i j 若a i j 1 则xi xj 8 4 3图着色算法 程序8 6 图的m着色算法templatevoidMGraph NextValue intk intm

11、int x do x k x k 1 m 1 if x k return for intj 0 j k j if a k j 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 templatevoidMGraph mColoring intm int x mColoring 0 m x 8 4 4时间分析 算法的计算时间上界可由状态空间树的结点

12、数确定 每个结点的处理时间即NextValue的执行时间 为O mn 因此总时间为 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 路径上其余结点各不相同 8 5哈密顿环 8 5 2哈密顿环算法 对于n个结点的图G V E 的哈密顿环问题 可采用n 元组表示问题的解 x0

13、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 着色问题非常相似 程序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

14、k n 1 k n 1 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 templatevoidExtMGraph Hamiltonian int x Hamiltonian 1 x 8 7 1问题描述 设有n个作业的集合 0 1 n 1 每个作业有两项任务要求分别在2台设备P1和P2上完成 每个作业必须先在P1上加工 然后在P2上加工 P1和P

15、2加工作业i所需的时间分别为ai和bi 作业i的完成时间fi S 是指在调度方案S下 该作业的所有任务得以完成的时间 则是采用调度方案S的平均完成时间 8 7批处理作业调度 批处理作业调度 batchjobschedule 问题要求确定这n个作业的最优作业调度方案使其MFT最小 这等价于求使得所有作业的完成时间之和最小的调度方案 例8 5设有三个作业和两台设备 作业任务的处理时间为 a0 a1 a2 2 3 2 和 b0 b1 b2 1 1 3 这三个作业有6种可能的调度方案 0 1 2 0 2 1 1 0 2 1 2 0 2 0 1 2 1 0 它们相应的完成时间之和分别是19 18 20

16、21 19 19 其中 最佳调度方案S 0 2 1 在这一调度方案下 f0 S 3 f1 S 7 f2 S 8 FT 3 7 8 18 8 7 2回溯法求解 对于双机批处理作业调度问题 其可行解是n个作业所有可能的排列 每一种排列代表一种作业调度方案S 其目标函数是使FT S 具有最小值的调度方案或作业排列是问题的最优解 对于双机作业调度 存在一个最优非抢先调度方案 使得在P1和P2上的作业完全以相同次序处理 批处理作业调度问题的状态空间树解空间的大小为n 求解这一问题没有有效的约束函数 但可以使用最优解的上界值U进行剪枝 如果对于已经调度的作业子集的某种排列 所需的完成时间和已经大于迄今为止所记录下的关于最优调度方案的完成时间和的上界值U 则该分枝可以剪去 8 7 3批处理作业调度算法 程序8 9 批处理作业调度算法classBatchJob public BatchJob intsz int aa int bb intup n sz U up f f1 0 a newint n b newint n f2 newint n y newint n for inti 0 i n i a