第9章 分支限界法PPT课件.ppt

第9章分支限界法 学习要点 理解分支限界法的剪枝搜索策略掌握分支限界法的算法框架队列式 FIFO 分支限界法优先队列式分支限界法通过应用范例学习分支限界算法设计策略 9 1 1分支限界法分支限界法类似于回溯法 也是一种在问题的解空间树T中搜索问题解的算法 分支限界法常以广度优先或以最小耗费 LC 优先的方式搜索问题的解空间树 在遍历过程中 对已经扩展出的每一个结点根据限界函数估算目标函数的可能取值 从中选取使目标函数取得极值的结点优先进行广度优先搜索 从而不断调整搜索方向 尽快找到问题的解 适用于求解最优化问题 9 1概述 9 1 2分支限界法的设计思想首先 确定一个合理的限界函数 并根据限界函数确定问题的目标函数的界 down up 具体问题可以只有下界down 或上界up 然后 按照广度优先策略遍历问题的解空间树 当搜索到达一个扩展结点时 一次性扩展它的所有孩子 估算每一个孩子结点的目标函数的可能取值 又称为耗费函数值 将那些满足约束条件且耗费函数值不超过目标函数的界的孩子 插入活动结点表PT中 再从PT表中取耗费函数值极大 小 的下一结点同样扩展 直到找到所需的解或PT表为空为止 怎样确定 限界函数 又如何求得目标函数的界呢 对于PT中的叶子结点 其耗费函数值是极值 极大或极小 则该叶子结点对应的解就是问题的最优解 否则 将问题目标函数的界 down up 调整为该叶子结点的耗费函数值 然后丢弃PT表中超出目标函数界的结点 再次选取结点继续扩展 例9 1 0 1背包问题 实例 假设有4个物品 其重量分别为 4 7 5 3 价值分别为 40 42 25 12 背包容量W 10 将给定物品按单位重量价值从大到小排序 结果如下 分析 问题的解可表示为n元向量 x1 x2 xn xi 0 1 则可用子集树表示解空间 在树中做广度优先搜索 约束条件 目标函数 下界Vdb 40 1 0 0 0 贪心思想 上界Vub 0 W 0 v1 w1 0 10 0 10 100 上限界函数 式9 1 目标函数的界 40 100 前i个物品获得的价值 剩余容量全部装入物品i 1 最多能够获得的价值 分支限界法求解0 1背包问题 w 0 v 0ub 100 w 4 v 40ub 76 w 0 v 0ub 60 w 11 w 4 v 40ub 70 w 9 v 65ub 69 w 4 v 40ub 64 w 12 w 9 v 65ub 65 2 3 4 5 6 7 8 9 1 PT 2 3 无效解 PT 5 3 PT 6 7 3 无效解 x1 1 x1 0 x2 1 x2 0 x3 1 x3 0 x4 1 x4 0 PT 9 7 3 V 65X 1 0 1 0 目标函数范围 40 100 wi 4 7 5 3 vi 40 42 25 12 vi wi 10 6 5 4 分支限界法的一般过程 1 根据限界函数确定目标函数的界 down up 2 将待处理结点表PT初始化为空 3 对根结点的每个孩子结点x执行下列操作3 1估算结点x的目标函数值value 3 2若 value down 则将结点x加入表PT中 4 循环直到某个叶子结点的目标函数值在表PT中最大4 1i 表PT中值最大的结点 4 2对结点i的每个孩子结点x执行下列操作4 2 1估算结点x的目标函数值value 4 2 2若 value down 则将结点x加入表PT中 4 2 3若 结点x是叶子结点且结点x的value值在表PT中最大 则将结点x对应的解输出 算法结束 4 2 4若 结点x是叶子结点但结点x的value值在表PT中不是最大 则令down value 并且将表PT中所有小于value的结点删除 常见的两种分支限界法 从表PT中选择下一扩展结点的不同方式导致不同的分支限界法 队列式 FIFO 分支限界法 从左往右依次插入结点到队尾 按照队列先进先出 FIFO 原则选取下一个节点为扩展节点 优先队列式分支限界法 按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点 最大优先队列 使用最大堆 体现最大效益优先 最小优先队列 使用最小堆 体现最小费用优先 例如 上例0 1背包问题 采用最大优先队列式分支限界法 应用分支限界法的其他关键问题 如何确定最优解中的各个分量 对每个扩展结点保存根结点到该结点的路径 例如 0 1背包问题 将部分解 x1 xi 和该部分解的目标函数的上界值都存储在待处理结点表PT中 在搜索过程中表PT的状态如下 在搜索的过程中构建搜索经过的树结构 在求得最优解时 从叶子结点不断回溯到根结点 以确定最优解中的各个分量 例如 0 1背包问题 设一个表ST 在表PT中取出最大值结点进行扩充时 将最大值结点存储到表ST中 表PT和表ST的数据结构为 物品i 1的选择结果 ub 在搜索过程中表PT和表ST的状态如下 说明 ST中记录的就是得到最优解的搜索路径上的各个结点 分支限界法与回溯法的区别 求解目标不同 回溯法 找出满足约束条件的所有解分支限界法 找出满足条件的一个解 或某种意义下的最优解搜索方式不同 回溯法 深度优先分支限界法 广度优先或最小耗费优先此外 在分支限界法中 每一个活结点只有一次机会成为扩展结点 9 2 1TSP问题例9 2 TSP问题 问题描述 略 各个城市间的距离用代价矩阵来表示 如果 i j E 则cij 分析 设城市按自然数1 2 n编号解向量 x1 x2 xn 约束条件 显式约束 xi 1 2 n i 1 2 n 隐式约束 xi xj cij 9 2广度优先分支限界法应用举例 目标函数 k V 下界 ddb 1 3 3 6 1 2 3 4 2 3 2 14上界 dub 16 1 3 5 4 2 1 下限界函数 设已确定的顶点集合U r1 r2 rk 式9 2 目标函数的界 14 16 从集合U中出来的边 一条进边 一条出边 优先队列式分支限界法求解TSP问题 目标函数范围 14 16 4 1 2db 14 2 3 5 6 7 8 1 startdb 14 1 3db 14 1 4db 16 1 5db 19 2 3db 16 2 4db 16 2 5db 19 3 2db 16 3 4db 15 3 5db 14 9 10 11 5 2db 19 5 4db 14 12 13 4 2db 16 14 4 2db 18 4 5db 15 15 16 5 2db 20 17 db 19 PT 2 3 4 db 19 PT 6 7 9 10 11 4 db 18 db 19 PT 6 7 9 16 14 4 db 20 PT 6 7 9 14 4 PT 6 7 9 10 13 4 PT 6 7 3 4 PT 6 7 9 10 14 4 d 161 3 5 4 2 1 对每个扩展结点保存根结点到该结点的路径 TSP问题算法的伪代码描述 1 根据限界函数计算目标函数的下界down 采用贪心法得到上界up 2 将待处理结点表PT初始化为空 3 for i 1 i 1 5 1i k 1 5 2x i 1 5 3while x i n 5 3 1如果路径上顶点不重复 则5 3 1 1根据式7 2计算目标函数值db 5 3 1 2if db up 将路径上的顶点和db值存储在表PT中 5 3 2x i x i 1 5 4若i n且叶子结点的目标函数值在表PT中最小 则将该叶子结点对应的最优解输出 5 5否则 若i n 则在表PT中取叶子结点的目标函数值最小的结点db 令up db 将表PT中目标函数值db超出up的结点删除 5 6k 表PT中db最小的路径上顶点个数 课后作业 应用分支限界法求解下图的TSP问题 9 2 2单源最短路径问题问题描述 略 例9 3 分析 采用优先队列式分支限界法 并用一极小堆来存储活结点表 其优先级是结点所对应的当前路长 解向量 X s x2 t s和t分别为起点和终点约束条件 显式 xi A B i 2 n 隐式 cij 目标函数 cost i min cij cost j i j n且顶点j是i的邻接点 下界 把每一段最小的代价相加 2 4 5 3 14上界 2 7 6 3 18 s B E H t 下限界函数 假设已经确定了i段 1 i k 其路径为 r1 r2 ri ri 1 与顶点ri 1相连的边中 代价最小的边 剩余顶点能够达到的最小代价 优先队列式分支限界法求解 6 4 s Adb 20 2 3 1 startdb 14 s Bdb 16 s Cdb 15 7 B Ddb 18 8 B Edb 18 9 B Fdb 18 5 C Edb 16 C Fdb 18 11 10 E Gdb 22 E Hdb 16 目标函数范围 14 18 PT 3 4 PT 3 5 6 PT 7 8 9 5 6 PT 7 8 9 11 6 c 16s C E H t 4 8 5 3 搜索算法描述 while true for intj 1 jN N i j N length dist j H Insert N try H DeleteMin E 取下一扩展结点catch OutOfBounds break 优先队列空 顶点i和j间有边 且此路径长小于原先从原点到j的路径长 9 2 3装载问题问题描述 略 分析 解空间 X x1 x2 xn xi Si 0 1 i 1 2 n约束函数 目标函数 下界 上界 上限界函数 左孩子 Ew w i 1 c1 右孩子 Ew bestw 改进 搜索算法设计 队列式分支限界 while true 检查左儿子结点Typewt Ew w i 左儿子结点的重量if wtbestw bestw wt 加入活结点队列if ibestw 进入下一层 提前更新bestw 右儿子剪枝 优先队列式分支限界 采用最大优先队列存储活结点表 活结点x在优先队列中的优先级定义为 从根结点到结点x的路径所相应的载重量Ew 剩余集装箱的重量r 子集树中叶结点所相应的载重量与其优先级相同 一旦有一个叶结点成为当前扩展结点 则可以断言该叶结点所相应的解即为最优解 此时可终止算法 实现方法 PT表结点的结构 在活结点中保存从解空间树的根结点到该活结点的路径 搜索进程中保存当前已构造出的部分解空间树 算法描述 采用第二种方式实现PT表 templateclassHeapNode classbbnode friendvoidAddLiveNode MaxHeap friendTypeMaxLoading Type Type int int public operatorType const returnuweight private bbnode ptr 指向活结点在子集树中相应结点的指针Typeuweight 活结点优先级 上界 intlevel 活结点在子集树中所处的层序号 templatevoidAddLiveNode MaxHeap N uweight wt N level lev N ptr b H Inset N templateTypeMaxLoading Typew Typec intn intbestx 优先队列式分支限界法 返回最优装载重量 bestx返回最优解 定义最大堆的容量为1000MaxHeap H 1000 定义剩余重量数组rType r newType n 1 r n 0 for intj n 1 j 0 j r j r j 1 w j 1 初始化inti 1 当前扩展结点所处的层bbnode E 0 当前扩展结点TypeEw 0 扩展结点所相应的载重量 搜索子集空间树while i n 1 非叶子结点 检查当前扩展结点的孩子结点if Ew w i N H DeleteMax N 非空i N level E N prt Ew N uweight r i 1 构造当前最优解for intj n j 0 j bestx j E Lchild E E parent returnEw 9 2 4批处理作业调度问题例9 4 批处理作业调度问题 问题描述 给定n个作业的集合J J1 J2 Jn 每个作业都有3项任务分别在3台机器上完成 作业Ji需要机器j的处理时间为tij 1 i n 1 j 3 每个作业必须先由机器1处理 再由机器2处理 最后由机器3处理 批处理作业调度问题要求确定这n个作业的最优处理顺序 使得从第1个作业在机器1上处理开始 到最后一个作业在机器3上处理结束所需的时间最少 实例 设J J1 J2 J3 J4 是4个待处理的作业 需要的处理时间如下所示 若处理顺序为 J2 J3 J1 J4 则从作业2在机器1处理开始到作业4在机器3处理完成的调度方案如下 等待时间 处理时间 分析 解向量 X x1 x2 xn 排列树约束条件 显式 xi J1 J2 Jn目标函数 sum3 下限界函数 机器3有空闲 机器3有积压 极小化 其中 sum2 n max sum1 n sum2 n 1 tn2 sum1 n sum1 n 1 tn1 设M是已安排好的作业集合 M 1 2 n M k 现在要处理作业k 1 有 sum1 k 1 sum1 k tk 1 1sum2 k 1 max sum1 k 1 sum2 k tk 1 2 max sum2 n sum3 n 1 tn3 目标函数的下界 sum3db 说明 最理想的情况下 机器1和机器2均无空闲 最后处理的作业恰好是在机器3上处理时间最短的作业 如上实例 sum3db 36遍历并估算解空间树上各结点的目标函数的下界值 根结点 sum1 0 sum2 0 M k 0 优先队列式分支限界法求解过程 J4 sum1 0 7db 38sum2 15 2M k 1 J1 sum1 0 5db 36sum2 5 7 12 1M k 0 startsum1 0 sum2 0 3M k 1 J2 sum1 0 10db 44sum2 12 4M k 1 J3 sum1 0 9db 40sum2 18 5M k 1 6M 1 k 2 J1J2 sum1 15db 42sum2 20 7M 1 k 2 J1J3 sum1 14db 38sum2 22 8M 1 k 2 J1J4 sum1 12db 36sum2 20 9M 1 4 k 3 J1J4J2 sum1 22db 41sum2 27 10M 1 4 k 3 J1J4J3 sum1 21db 37sum2 30 11M 1 4 3 k 4 J1J4J3J2 sum1 31db 36sum2 4 36 PT 2 3 4 5 PT 6 7 8 3 4 5 PT 6 7 9 10 3 4 5 PT 6 7 9 11 3 4 5 X J1 J4 J3 J2 sum3 sum2 4 t23 38 sum1 k sum1 k 1 tk 1sum2 k max sum1 k sum2 k 1 tk 2 下界sum3db 36 从上例可知 优先队列式分支限界法中 扩展结点表PT取得极值的叶子结点就对应的是问题的最优解 扩展结点的过程 一开始实际类似 深度优先 思考 将例9 2和例9 4改成FIFO式分支限界法 搜索过程有何不同 在算法的实现上 FIFO式分支限界法和优先队列式分支限界法的PT表数据结构一样吗 课后作业 采用分支限界法求解下列作业调度问题 4个作业J1 J2 J3 J4在机器M1 M2上处理的时间矩阵如图所示 求最佳的处理顺序 使得4个作业从开始到结束处理的时间最短 要求 画出解空间的展开 M1 M2 J1 J2 J3 J4 9 3最小消耗 LC 搜索法 9 3 1LC检索在FIFO分枝限界法中 对下一个E 结点的选择规则相当死板 在某种意义上是盲目的 对活结点使用一个 有智力 的排序函数c 来选取下一个E 结点往往可以加快到达一答案结点的速度 对任意结点x 可用两种标准来量度 在生成一个答案结点之前 子树x需要生成的结点个数 在子树x中离x最近的那个答案结点到x的路径长度 使用第一种度量 图中树的根结点付出的代价是4 结点 18和34 29和35 以及 30和38 的代价分别是3 2和1 所有在2 3和4级上剩余结点的代价应分别大于3 2和1 以这些代价作为选择下一个E 结点的依据 则E 结点依次为1 18 29和30 另外 不得已生成的结点为2 34 50 19 24 32 使用第二种度量 则E 结点只是由根到最近的那个答案结点路径上的那些结点 图9 14 皇后问题 总是生成最小数目的结点 9 3 2LC方法要点对状态空间树上的一个答案结点x 定义实际代价函数cost x cost x 的内涵 从状态空间树根结点出发 到达一个答案结点x 实际需要付出的 代价 cost x 的定义 原则上应根据具体问题加以定义 对状态空间树上任一结点x 定义代价函数c x c x 的内涵 从状态空间树根结点出发 经过x结点 在以结点x为根的子树上 搜索到一个答案结点 所需要付出的代价 定义c x 的一般原则 若x是答案结点 则 c x cost x 若x不是答案结点 但以x为根的子树上至少有一个答案结点 则 c x min c answer answer x上所有答案结点 若x不是答案结点 且以x为根的子树上也没有答案结点 则 c x 对状态空间树上结点x 定义估算函数 且使满足 c x 注 与c x 相比 应是当前 可计算 的 设计一个活结点表L 用于存放搜索过程的 活结点 该表的数据结构可选择有序表或堆 即要求 活结点表上的所有结点 按照它们估算函数取值 构成一个有序表或堆 h x g x LC法搜索过程 初始 把状态空间树的根结点 做为活结点表L的第一个结点 重复以下两步 直到找到一个解 或L为空 从L上选出具有最小的结点 作为当前E 结点 依次搜索当前E 结点的所有子结点 若子结点是答案结点 则结束 否则 把子结点加入有序表L 9 3 3LC方法应用举例15迷问题 问题描述 把编号为1 15的棋子 随意放在4 4格的棋盘上 空出一个格 要求 经过有限步的移动 把棋盘上棋子的 初态 变成棋子号与棋盘号一致的目标状态 注 移动 仅限于空格周围棋子 实例 初态目标状态 分析 实际代价函数cost x 若x是目标状态 则 cost x 等于从棋盘初态 经逐步移动棋子而到达目标状态x 实际需要移动棋子总步数 代价函数c x 若x是目标状态 则 c x cost x 若x不是目标状态 但x所在子树上存在目标状态结点 则 c x min c x x x子树上所有目标状态结点 若x不是目标状态 且x所在子树上也不存在任何目标状态结点 则c x 定义估算函数 h x g x 其中 h x 从状态空间树的根结点到x结点路径长度 g x x状态下 没有达到 目标状态 的棋子数量 g1 6 h1 0 1 g2