算法设计与分析分支限界法第六章.ppt

2020 4 21 计算机算法设计与分析 1 树搜索的一般形式 SearchTree SpaceT ok 0 L T initial while ok L a L first if aisgoal unfinish falseelseControl put in L Sons a 三种搜索方法的不同就在于存放待考察的结点的表L的控制方式不同 DFS 回溯法 是栈 WFS是队列 BFS是队列中的元素排序 2020 4 21 计算机算法设计与分析 2 分支限界法基本思想 分支限界法就是最佳优先 包括广度优先 的搜索法 其基本思想是 将要待考察的结点按其优劣排序 优先搜索好结点 于是便有了两个问题 1 如何知道结点的优劣 2 在回溯法中 表L中结点的层次分明 因而路径也分明 但是这里排序会打乱表L中结点的层次 那又如何找回解的路径呢 2020 4 21 计算机算法设计与分析 3 分支限界法基本思想 分支限界法就是最佳优先 包括广度优先 的搜索法 其基本思想是 将要待考察的结点按其优劣排序 优先搜索好结点 于是便有了两个要点 1 需要构造评价结点优劣的评价函数 2 需要能够重新构造解的路径 也就是搜索的路径 2020 4 21 计算机算法设计与分析 4 评价函数的构造 评价函数要能够提供一个评定候选扩展结点的方法 以便确定哪个结点最有可能在通往目标的最佳路径上 一个评价函数f d 通常由两个部分构成 从开始结点到d的已有耗损值g d 和 再从d到达目标的期望耗损值h d 即 f d g d h d 通常g d 的构造较易 h d 的构造较难 2020 4 21 计算机算法设计与分析 5 搜索路径的构造 在回溯法中 每次仅考察一条路径 因而只需要构造这一条路径即可 前进时记下相应结点 回溯时删去最末尾结点的记录 这比较容易实现 在分支限界法中 是同时考察若干条路径 那么又该如何构造搜索的路径呢 往前看 前程无数 往回看 来路一条 每个结点只要记住其前驱结点就行了 2020 4 21 计算机算法设计与分析 6 搜索路径的构造 为此 只需要对每一个扩展的结点d 建立三个信息 1 该结点的名称d 2 它的评价函数值f d 3 指向其前驱的指针p 即表示为 d f d p 这样一旦找到目标 即可以很方便地逆向构造出该路径 2020 4 21 计算机算法设计与分析 7 Open表与Closed表 搜索中 表L用来保存准备扩展的结点 即下一步的结点 把表L称为Open表 此外 为了构造解的路径 还需要一个表来保存已经搜索过的结点 即已经走过的结点 此表被称为Closed表 故任意结点d必是 d Open d Closed d Closed d Open 结点d尚未被考察 结点d已经被考察 2020 4 21 计算机算法设计与分析 8 分支限界法的一般算法 初始化 计算起点s的f s s f s nil 放入Open while Open 从Open中取出 p f p x f p 为最小 if f p U 将 p f p x 放入Closed if p是目标 成功返回 else 产生p的后继d并计算f d 对每个后继d 有二种情况 d Open d Closed d Closed d Open 若结点d尚未被考察 则将 d f d p 插入到Open中 若f p U 则剪去该路径 2020 4 21 计算机算法设计与分析 9 分支限界法的一般算法 初始化 计算起点s的f s s f s nil 放入Open while Open 从Open中取出 p f p x f p 为最小 if f p U 将 p f p x 放入Closed if p是目标 成功返回 else 产生p的后继d并计算f d 对每个后继d 有二种情况 d Open d Closed d Closed d Open 若结点d已被考察 则说明这次是通过另一条路径到达到d 设d原来评价为f d 将其与新的评价f d 比较 若新评价更好 则删去旧的 将新的插入到Open中 否则丢弃 2020 4 21 计算机算法设计与分析 10 分支限界法的一般算法 初始化 计算起点s的f s s f s nil 放入Open while Open 从Open中取出 p f p x f p 为最小 if f p U 将 p f p x 放入Closed if p是目标 成功返回 else 产生p的后继d并计算f d 对每个后继d if d Closed d Open 将 d f d p 插入到Open中 else if f d f d 删去旧结点并将 d f d p 重新插入到Open中 2020 4 21 计算机算法设计与分析 11 分支限界法求单源最短路径 单源最短路径问题的评价函数的构造 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 21 计算机算法设计与分析 12 分支限界法求最短路径举例 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 21 计算机算法设计与分析 13 界限 Bounding 评价函数f d 关系着算法的效率乃至成败 因为在大多数问题中f d 只是个估计值 所以单靠f d 是不够的 通常还要设计它的上下界函数U d 和L d L d f d U d 所谓分支限界法就是通过评价函数及其上下界函数的计算 将状态空间中不可能产生最佳解的子树剪去 减少搜索的范围 提高效率 因而更准确的称呼应是 界限剪支法 2020 4 21 计算机算法设计与分析 14 用分支限界法求TSP TSP是求排列的问题 不是仅找一条路径而已 因而需要对分支限界法的一般算法作些修改 1 待扩展结点若已在本路径上 则不再扩展 但若是在其他路径上出现过 则仍需要扩展 为此 用一个表L来存储该路径出现的结点 即将 d f d p 改为 d f d L 该结点是否已经出现过 可查Closed表或者Open表 但是要查它出现在哪条路径上 就颇费周章了 这个L该怎么做 2020 4 21 计算机算法设计与分析 15 用分支限界法求TSP TSP是求排列的问题 不是仅找一条路径而已 因而需要对分支限界法的一般算法作些修改 1 待扩展结点若在本路径上已经出现 则不再扩展 但若是在其他路径上出现过 则仍需要扩展 为此 用一个表L来存储该路径出现的结点 2 新结点 无论其优劣 既不影响其它路径上的结点 也不受其它路径上的结点的影响 3 若考察结点的评价值超过上界值 则可以剪去 这实际上是剪去了这一支 L可设计为数组L n 初始值都为n 每加入新结点i 则L i p 这里p是i的前驱结点 若L i n 则i已在此路径中 这样结点i的插入时间和判定时间都为常量 2020 4 21 计算机算法设计与分析 16 分支限界法的一般算法 初始化 计算起点s的f s s f s nil 放入Open while Open 从Open中取出 p f p x f p 为最小 if f p U 将 p f p x 放入Closed if p是目标 成功返回 else 产生p的后继d并计算f d 对每个后继d if d Closed d Open 将 d f d p 插入到Open中 else if f d f d 删去旧结点并将 d f d p 重新插入到Open中 不失一般性 令0为起点 U为上界值 Initialization U Open Closed 计算f 0 产生空表L L0 0 n n Put ordered in Open 0 f 0 L 把 0 f 0 L 按序放入Open表中 2020 4 21 计算机算法设计与分析 17 分支限界法的一般算法 Initialization while Open 从Open中取出 p f p x f p 为最小 if f p U 将 p f p x 放入Closed if p是目标 成功返回 else 产生p的后继d并计算f d 对每个后继d if d Closed d Open 将 d f d p 插入到Open中 else if f d f d 删去旧结点并将 d f d p 重新插入到Open中 L 此处改为表L 2020 4 21 计算机算法设计与分析 18 分支限界法的一般算法 Initialization while Open 从Open中取出 p f p L f p 为最小 if f p U 将 p f p x 放入Closed if p是目标 成功返回 else 产生p的后继d并计算f d 对每个后继d if d Closed d Open 将 d f d p 插入到Open中 else if f d f d 删去旧结点并将 d f d p 重新插入到Open中 此句可以不要了 因为每条通路上考察过的结点放在表L中了 Closed表L不再需要了 2020 4 21 计算机算法设计与分析 19 分支限界法的一般算法 Initialization while Open 从Open中取出 p f p L f p 为最小 if f p U if p是目标 成功返回 else 产生p的后继d并计算f d 对每个后继d if d Closed d Open 将 d f d p 插入到Open中 else if f d f d 删去旧结点并将 d f d p 重新插入到Open中 如何知道p是目标 如果L中已有n个结点了 则p是目标 那又如何知道L中已有n个结点了 2020 4 21 计算机算法设计与分析 20 分支限界法的一般算法 Initialization while Open 从Open中取出 p f p L f p 为最小 if f p U if p是目标 成功返回 else 产生p的后继d并计算f d 对每个后继d if d Closed d Open 将 d f d p 插入到Open中 else if f d f d 删去旧结点并将 d f d p 重新插入到Open中 L中存放的是每个结点的前驱 故可用L 0 作计数器 初始化时L 0 1 之后每加入一个结点 L 0 当L 0 n 则已达目标 2020 4 21 计算机算法设计与分析 21 分支限界法的一般算法 Initialization while Open 从Open中取出 p f p L f p 为最小 if f p U if p是目标 成功返回 else 产生p的后继d并计算f d 对每个后继d if d Closed d Open 将 d f d p 插入到Open中 else if f d f d 删去旧结点并将 d f d p 重新插入到Open中 所以 这里应改为 if L 0 n S p f p Lp U f p else 这里变量S用于存放解 2020 4 21 计算机算法设计与分析 22 分支限界法的一般算法 Initialization while Open 从Open中取出 p f p L f p 为最小 if f p U if L 0 n S p f p Lp U f p else 产生p的后继d并计算f d 对每个后继d if d Closed d Open 将 d f d p 插入到Open中 else if f d f d 删去旧结点并将 d f d p 重新插入到Open中 因为TSP要考察每一条通路 只要这条通路没走完 就要继续考察 扩展结点p 对p的每个后继结点d 若d不在L中 则 计算f d 若f d U 则生成 d f d Ld 并将其按序放入Open表中 2020 4 21 计算机算法设计与分析 23 扩展结点p 扩展结点p需要做的事情有 对p的每个后继结点d 若d不在L中 则 计算f d 若f d U 则生成 d f d Ld 并将其按序放入Open表中 什么样的结点是p的后继结点 令代价矩阵为C n n 若C p d 则d是p的后继结点 即 for d 1 d n d if C p d 0是起点 无需考虑 if L d n then 2020 4 21 计算机算法设计与分析 24 扩展结点p 扩展结点p需要做的事情有 对p的每个后继结点d 若d不在L中 则 计算f d 若f d U 则生成 d f d L 并将其按序放入Open表中 for d 1 d n d if L d n C p d then V f d 调用评价函数计算f d if V U 生成Ld Ld L d Put ordered in Open d f d Ld 需要为d生成一个其自有的路径表Ld 将p的路径表L插入p的后继结点d之后再赋值给Ld 最后将新扩展结点d按序放入Open表中 2020 4 21 计算机算法设计与分析 25 扩展结点p Develop p f p L for d 1 d n d if L d nPut ordered in Open d f d Ld 2020 4 21 计算机算法设计与分析 26 分支限界法的一般算法 Branch bounding for TSP n C Initialization while Open 从Open中取出 p f p L f p 为最小 if f p U if L 0 n S p f p Lp U f p else Develop p f p Lp 2020 4 21 计算机算法设计与分析 27 分支限界法求TSP举例 设有向图G V E 的边的代价矩阵为C cij 若没有有向边 E 则定义cij 且规定cii 不失一般性 设周游路线均以顶点1为起点 左下为一个有向图G的代价矩阵C 评价函数f d 为1到d的代价减去已经过的边数 初始时f 1 0 f d f p cpd 1 这里p是d的前驱 2020 4 21 计算机算法设计与分析 28 分支限界法求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 21 计算机算法设计与分析 29 评价函数影响搜索效率 前面的搜索的效率不高 几乎要搜索全部的状态空间 其原因是评价函数性能不好以及上下界的估计太低 要提高搜索效率 就必须要提高评价函数的性能 并精确上界的估计值 为了设计求解TSP问题的更好的评价函数 先定义其代价矩阵的归约矩阵和约数 2020 4 21 计算机算法设计与分析 30 归约矩阵以及约数 给定代价矩阵C 从C的任何行i 或列i 的各元素中减去此行 或此列 的最小元素的值r i 或r i 称为对i行 或i列 的归约 将C的各行和各列都归约后的矩阵称为C的归约矩阵 数r i nr i i nr i 即各行最小元素的值之和加上各列最小元素之和 称为C的约数 2020 4 21 计算机算法设计与分析 31 例子中的归约矩阵和约数 计算前面例子中的归约矩阵及其约数如下 先做行归约 r 1 25 01562 r 2 5 0 122520 r 3 1 1814 50 r 4 6 34421 0 r 5 7 15103 2020 4 21 计算机算法设计与分析 32 例子中的归约矩阵和约数 计算前面例子中的归约矩阵及其约数如下 再做列归约 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 0 r 4 3 322 0 47 约数r 47 归约矩阵 这个约数r是什么呢 2020 4 21 计算机算法设计与分析 33 约数是周游路线代价的下界 定理 设C是图G的代价矩阵 P是周游路线 则P的代价 即 Pcij r Pcij 式中C cij 是C的归约矩阵 r为约数 证明 由归约矩阵的构造可知 cij cij r i r j 即cij cij r i r j 任何周游路线包含n条边并且对应在C中的每行每列有且仅有一条边 于是 Pcij P cij r i r j r Pcij 原来约数r是图G的任何一条周游路线的代价的下界 2020 4 21 计算机算法设计与分析 34 用约数定义期望函数h d 既然约数是周游路线长度的下界 可以考虑用约数来定义期望函数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呢 2020 4 21 计算机算法设计与分析 35 求新的约数r2 可以 要先将边和所有边和边都删去 即置c12 c1k 和ck2 为 设Cp 为路线上点p的归约矩阵 从p选择边所得点d的归约矩阵Cd 和约数rd为 先将Cp 中的cpd cpk 和ckd 都置为 这里1 k n 即删去这些边 依照求归约矩阵C 的方法对C p进行行归约和列归约 便得到了Cd 和rd 因为边已走过 所以不可能再走边和边了 2020 4 21 计算机算法设计与分析 36 新的评价函数f d 不失一般性 将图G中结点标记为1 n 并设0为起点 将图G的代价矩阵C的约数r和归约矩阵C 分别为起点0的约数r1和归约矩阵C1 对任意路线上结点d 定义其评价函数为 f d g d h d 其中 g d f p Cp p d 这里p为d的前驱结点 并规定g 1 0 h d rd 两点在p的归约矩阵中的代价 2020 4 21 计算机算法设计与分析 37 用新的评价函数求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 C1 C2 C1 r3的计算仍然要用C1 故恢复为C1 下面与此相类似 不再演示 2020 4 21 计算机算法设计与分析 38 评价函数的程序设计 对任意路线上结点d 定义其评价函数为 f d g d h d 其中 g d f p Cp p d 这里p为d的前驱结点 并规定g 1 0 h d rd 其中用到了d的前驱结点p的归约矩阵Cp 因此 评价函数的计算中需要用到的参数有 p f p Cp 和d 计算的结果有f d 和Cd 注意到Cp 是与路径有关的 因此在 p f p L 中应增加Cp 改为 p f p L Cp 2020 4 21 计算机算法设计与分析 39 评价函数的数据结构 1 输入数据