数学建模 分支界限法ppt课件.ppt

2020 4 5 计算机算法设计与分析 1 第六章分支限界法 2020 4 5 计算机算法设计与分析 2 分支限界法是最佳优先搜索法 分支限界法就是最佳优先 包括广度优先在内 的搜索法 分支限界法将要搜索的结点按评价函数的优劣排序 让好的结点优先搜索 将坏的结点剪去 所以准确说 此方法应称为界限剪支法 分支限界法中有两个要点 1 评价函数的构造 2 搜索路径的构造 2020 4 5 计算机算法设计与分析 3 评价函数的构造 评价函数要能够提供一个评定候选扩展结点的方法 以便确定哪个结点最有可能在通往目标的最佳路径上 一个评价函数f d 通常可以由两个部分构成 从开始结点到结点d的已有耗损值g d 和 再从结点d到达目标的期望耗损值h d 即 f d g d h d 通常g d 的构造较易 h d 的构造较难 2020 4 5 计算机算法设计与分析 4 搜索路径的构造 在回溯法中 每次仅考察一条路径 因而只需要构造这一条路径即可 前进时记下相应结点 回溯时删去最末尾结点的记录 这比较容易实现 在分支限界法中 是同时考察若干条路径 那么又该如何构造搜索的路径呢 对每一个扩展的结点 建立三个信息 1 该结点的名称 2 它的评价函数值 3 指向其前驱的指针 这样一旦找到目标 即可逆向构造其路径 用一个表保存准备扩展的结点 称为Open表 用一个表保存已搜索过的结点 称为Closed表 2020 4 5 计算机算法设计与分析 5 分支限界法的一般算法 计算初始结点s的f s s f s nil 放入Open while Open 从Open中取出 p f p x f p 为最小 将 p f p x 放入Closed 若p是目标 则成功返回 否则 产生p的后继d并计算f d 对每个后继d 有二种情况 d Closed d Open d Open d Closed 若 d f d p Closed d f d p Open 否则 将 d f d p 插入到Open中 2020 4 5 计算机算法设计与分析 6 分支限界法求单源最短路径 单源最短路径问题的评价函数的构造 g d 定义为从源s到结点d所走的路径长度 g d g p C p d 这里p为d的前驱结点 C p d 为p到d的距离 h d 定义为0 于是f d g d 源s的评价函数f s 0 评价函数的下界为0 上界初始时为 以后不断用取得的更短路径的长度来替代 2020 4 5 计算机算法设计与分析 7 分支限界法求最短路径举例 1 2 5 4 3 10 20 50 100 30 10 60 赋权图G 初始时 将源 1 0 0 放入Open Closed为空 Open表 Closed表 取出 1 0 0 放入Closed 生成其后继 2 10 1 4 30 1 和 5 100 1 并依序放入Open 取出 2 10 1 放入Closed 生成其后继 3 60 2 并依序插入Open 取出 4 30 1 放入Closed 生成其后继 3 50 4 和 5 90 4 修订Open中已有的两个结点并依序排列 取出 3 50 4 放入Closed 生成其后继 2 100 3 和 5 60 3 前者因劣于Closed中的 2 10 1 而被抛弃 后者修订了Open中的 5 90 4 取出 5 60 3 因其已经是目标结点 算法成功并终止 依据逆向指针可得最短路径为1 4 3 5 2020 4 5 计算机算法设计与分析 8 界限 Bounding 评价函数f d 关系着算法的效率乃至成败 因为在大多数问题中f d 只是个估计值 所以单靠f d 是不够的 通常还要设计它的上下界函数U d 和L d L d f d U d 所谓分支限界法就是通过评价函数及其上下界函数的计算 将状态空间中不可能产生最佳解的子树剪去 减少搜索的范围 提高效率 因而更准确的称呼应是 界限剪支法 2020 4 5 计算机算法设计与分析 9 用分支限界法求TSP TSP是求排列的问题 不是仅找一条路径而已 因而需要对分支限界法的一般算法作些修改 1 待扩展的结点如果在本路径上已经出现 则不再扩展 但若是在其他路径上出现过 则仍需要扩展 2 新结点 无论其优劣 既不影响其它路径上的结点 也不受其它路径上的结点的影响 3 依据上界函数决定结点是否可以剪去 2020 4 5 计算机算法设计与分析 10 分支限界法求排列 计算初始结点s的f s s f s nil 放入Open while Open 从Open中取出 p f p L L是路径已有结点 若f p U 则抛弃该路径 若p是目标 则考虑修改上界函数值 否则 将 p f p L 放入Closed 在该路径上扩展结点p 对每个后继d 计算f d 若f d U 则 L L p 将 d f d L 依序放入Open 2020 4 5 计算机算法设计与分析 11 分支限界法求TSP举例 设有向图G V E 的边的代价矩阵为C cij 若不存在有向边 E 则定义cij 且规定cii 不失一般性 设周游路线均以顶点1为起点 左下为一个有向图G的代价矩阵C 254031275 1730251915 6195024 6228710 评价函数f d 为1到d的代价减去已经过的边数 初始时f 1 0 f d f p cpd 1 这里p是d的前驱 2020 4 5 计算机算法设计与分析 12 分支限界法求TSP的搜索 254031275 1730251915 6195024 6228710 1 0 2 24 3 39 4 30 5 26 2 3 40 4 53 5 48 5 2 33 3 32 4 35 4 2 79 3 53 5 45 3 2 46 4 37 2 3 49 4 62 4 2 84 3 58 4 2 86 找到了第一条周游路线1 5 3 4 2 1 其长度为95 这不是最短周游路线 需要修改上界后继续搜索 2020 4 5 计算机算法设计与分析 13 归约矩阵以及约数 前面的搜索的效率不高 几乎要搜索全部的状态空间 其原因是评价函数以及上下界的估计太低 为了设计求解TSP问题的更好的评价函数 先定义其代价矩阵的归约矩阵和约数 给定代价矩阵C 从C的任何行i 或列i 的各元素中减去此行 或此列 的最小元素的值r i 或r i 称为对i行 或i列 的归约 将C的各行和各列都归约后的矩阵称为C的归约矩阵 和数r i nr i i nr i 称为C的约数 2020 4 5 计算机算法设计与分析 14 例子中的归约矩阵和约数 计算前面例子中的归约矩阵及其约数如下 254031275 1730251915 6195024 6228710 先做行归约 r 1 25 01562 r 2 5 0 122520 r 3 1 1814 50 r 4 6 34421 0 r 5 7 15103 再做列归约 r 1 r 2 r 3 r 5 0r 4 3 3222 0 约数r 47 2020 4 5 计算机算法设计与分析 15 约数是周游路线长度的下界 定理 设C是图G的代价矩阵 P是周游路线 则P的代价 即 Pcij r Pc ij 式中C c ij 是C的归约矩阵 r为约数 证明 由归约矩阵的构造可知 c ij cij r i r j 即cij c ij r i r j 任何周游路线包含n条边并且对应在C中的每行每列有且仅有一条边 于是 Pcij P c ij r i r j r Pc ij 2020 4 5 计算机算法设计与分析 16 定义期望函数h d 对开始结点1 令g 1 0 h 1 r f 1 r 若从结点1选择了一条边 不妨设边 则令g 2 f 1 从1到2的距离l 显然l应该是c 12 而不应该再是c12了 那么h 2 自然可以想到h 2 可以是从2开始的路线的下界r2 是否也可用类似求r一样去求新的约数r2呢 可以 但在此之前应将边和所有边和边都删去 即置c 12 c 1k和c k2为 设C p为某路线上结点p的归约矩阵 从p选择边所得到结点d的归约矩阵C d和约数rd为 1 将C p中的c pd c pk和c kd置为 1 k n 2 依照求归约矩阵C 的方法对C p进行行归约和列归约 便得到了C d和rd 令f 1 g 1 h 1 其中g 1 0 h 1 r 对任意路线上的结点d 设p是其前驱结点 则f d g d h d 其中 g d f p C p p d h d rd 2020 4 5 计算机算法设计与分析 17 用新的评价函数求TSP 下面用新的评价函数求前面的例子 我们已经求得了它的归约矩阵C 和约数r 47 015320 1222201814 2034418 015100 1 47 2 g 2 47 0 47 0 10 8 0 15 12 h 2 12 3 15 f 2 47 15 62 62 3 015320 1222201814 2034418 015100 g 3 47 15 62 0 43 13 h 3 1 f 3 63 63 4 类似地可求出f 4 51 51 5 类似地可求出f 5 50 50 下面优先扩展的是结点5 2 此时C 2是在C 5的基础上进行 右边就是C 5 0 1222 1814 2 34418 000 g 2 50 0 50 0 16 0 15 0 3 h 2 17 f 2 67 67 3 类似地计算出f 3 68 68 4 类似地计算出f 4 81 81 下面扩展f 4 51的结点4 并用同样方法计算它们的评价函数值 2 121 3 69 4 64 1 5 4 下面要扩展的结点是f 2 62的结点2 右边是其对应的归约矩阵C 2 2 010815 200 18 012 00 3 g 3 62 0 62 对C 2进行归约 得h 3 0 于是f 3 62 62 对结点2的另外两个儿子进行同样的计算 得 f 4 84 f 5 72 4 84 5 72 下面对f 3 62的结点3进行扩展 它有两个后继结点 3 4 5 对结点4 g 4 62 2 64 0 h 4 12 于是f 4 64 12 76 76 对结点5 g 5 62 0 62 15 200 012 0 h 5 0 于是f 5 62 0 62 62 对结点5 f 5 62 再进行扩展 5 4 g 4 62 0 62 h 4 0 f 4 62 62 结点4是目标结点 找到了第一条路线 4 这条路线的长度为62 以其为上界 其余未扩展的结点的评价函数值均超过上界 因而不再需要扩展了 于是找到了一条最短的周游路线 1 2 3 5 4 1 2020 4 5 计算机算法设计与分析 18 分支边与二叉树 在构造求TSP的搜索树时 还有另外一种算法稍有点不同 就是将搜索树构造成二叉树 给定一条最短周游路线P 对于任一条边只有两种情况 即 P或者 P 这就可以表示成右边的二叉树 k m n 其中 表示 P 这样的边称为分支边 2020 4 5 计算机算法设计与分析 19 用二叉树求TSP 1 2 50 3 62 2 4 53 5 68 4 6 64 7 65 3 8 62 9 74 8 10 62 11 70 10 12 62 13 66 12 14 62 15 66 14 16 62 17 结点16给出了一条最短周游路线 1 2 3 5 4 1 2020 4 5 计算机算法设计与分析 20 分支限界法的效率 从TSP问题的计算可看出 分支限界法搜索的状态空间为O 2n 对每个结点的计算时间为O n2 因此在最坏情况下 分支限界法计算TSP的时间复杂性为O n22n 显然 用分支限界法计算TSP的空间复杂性为O n22n 因为对每个结点需要n2的空间 2020 4 5 计算机算法设计与分析 21 对评价函数的讨论 分支限界法总耗时为O n22n 它与回溯法 动态规划法等在时间复杂性上没有本质的区别 然而 如果评价函数选择得好 采用分支限界法可能有一个小得多的常数因子 好的评价函数应该有一个尽可能高的下界估计和一个尽可能低的上界估计 从而使得搜索空间能够得到有效的压缩 从而提高效率 在理论上可以证明好的评价函数所搜索的结点不会多于坏的评价函数所搜索的结点 2020 4 5 计算机算法设计与分析 22 关系 传递闭包与搜索 定义在集合S上关系R是笛卡儿直积S S的一个子集 R S S 关系R的传递闭包是包含R的最小的具有传递性质的关系 若S是有限的 S n 则R可表示为一个n n的关系矩阵M或n个结点的有向图G 求关系R的传递闭包实际上也就是在有向图G上的搜索 而反过来 在有向图G上的搜索也就是求某种关系的传递闭包 2020 4 5 计算机算法设计与分析 23 传递闭包的集合算法 给定关系R以及S中的元素a 求R a 初始化 U A a q true while q for p A U U d d S且pRd if U A q false elseA U 这个算法稍加修改即可变成求R a 中满足某性质的元素的算法 不难看出此算法实际也就是分支限界法 2020 4 5 计算机算法设计与分析 24 传递闭包的矩阵算法 若 S n 则R可表示为一个矩阵M 于是R的传递闭包R 的矩阵M 为 i nM Mi M0 M1 Mni 0其中M0为单位矩阵E Mi为M的i次幂 M E for i 1 i n i M M M M 不难看出此算法的时间复杂性为O n4 2020 4 5 计算机算法设计与分析 25 传递闭包的Warshall算法 下面给出求传递闭包的Warshall算