第六章 分支限界法 2021/2/21 计算机算法设计与分析
2021/2/21 计算机算法设计与分析 1 第六章 分支限界法
分支限界法是最佳优先搜索法 分支限界法就是最佳优先(包括广度优先在内) 的搜索法 ■分支限界法将要搜索的结点按评价函数的优劣 排序,让好的结点优先搜索,将坏的结点剪去。 所以准确说,此方法应称为界限剪支法。 分支限界法中有两个要点 ■(1)评价函数的构造; (2搜索路径的构造。 2021/221 计算机算法设计与分析 2
2021/2/21 计算机算法设计与分析 2 分支限界法是最佳优先搜索法 ◼ 分支限界法就是最佳优先(包括广度优先在内) 的搜索法。 ◼ 分支限界法将要搜索的结点按评价函数的优劣 排序，让好的结点优先搜索，将坏的结点剪去。 所以准确说，此方法应称为界限剪支法。 ◼ 分支限界法中有两个要点： ◼ (1)评价函数的构造； ◼ (2)搜索路径的构造
评价函数的构造 ■评价函数要能够提供一个评定候选扩展结点的 方法,以便确定哪个结点最有可能在通往目标 的最佳路径上。 个评价函数f(d通常可以由两个部分构成: (1)从开始结点到结点d的已有耗损值g(d),和(2) 再从结点d到达目标的期望耗损值h(d)。即: f(d)=g(d)+h(d) 通常g(d)的构造较易,h(d)的构造较难 2021/22 计算机算法设计与分析 3
2021/2/21 计算机算法设计与分析 3 评价函数的构造 ◼ 评价函数要能够提供一个评定候选扩展结点的 方法，以便确定哪个结点最有可能在通往目标 的最佳路径上。 ◼ 一个评价函数f(d)通常可以由两个部分构成： ⑴从开始结点到结点d的已有耗损值g(d)，和⑵ 再从结点d到达目标的期望耗损值h(d)。即： f(d) = g(d) + h(d) ◼ 通常g(d)的构造较易，h(d)的构造较难
搜索路径的构造 ■粧锄溯展的缚敚儐栲个条愍径,因 而只需要构造这点路径即可:前进时 记下相应筠点約溯删去最末尾结点 的记录a这啪稼瘠易滤针 ■桷支溏称,趔南蹇粪罐係路 ,磲礬撇索踯郤曜 ■用一个表保存已搜索过的结点,称为 Closed表。 2021/22 计算机算法设计与分析
2021/2/21 计算机算法设计与分析 4 搜索路径的构造 ◼ 在回溯法中，每次仅考察一条路径，因 而只需要构造这一条路径即可：前进时 记下相应结点，回溯时删去最末尾结点 的记录。这比较容易实现。 ◼ 在分支限界法中，是同时考察若干条路 径，那么又该如何构造搜索的路径呢？ ◼ 对每一个扩展的结点，建立三个信息： ◼ (1)该结点的名称； ◼ (2)它的评价函数值； ◼ (3)指向其前驱的指针； ◼ 这样一旦找到目标，即可逆向构造其路径。 ◼ 用一个表保存准备扩展的结点，称为Open表。 ◼ 用一个表保存已搜索过的结点，称为Closed表
分支限界法的一般算法 ()计算初始结点s的f(s);s,f(s),ni放入Open; (2)whle(Open约){ (3)从Open中取出[p,fp),x](p)为最小) (4)将[p,fp),x放入 Closed; (⑤5)若p是目标,则成功返回;否则 (6){产生p的后继d并计算f(d);对每个后继d ■(7){若([d,f(d),p]∈ Closed[d,f(d),p]∈Open) &&f(d)<f(d),则删去旧结点并将[d,fd),p] 重新插入到Open中;否则 (8)将[d,f(d),p插入到open中}} 2021/221 计算机算法设计与分析 5
2021/2/21 计算机算法设计与分析 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 有二种情况：①dClosed || d Open； ②dOpen && dClosed。 ◼ ⑺ {若([d, f’(d), p]Closed || [d, f’(d), p]Open) && f(d)＜f’(d)，则删去旧结点并将[d, f(d), p] 重新插入到Open中; 否则 ◼ ⑻ 将[d, f(d), p] 插入到Open中}}}
分支限界法求单源最短路径 ■单源最短路径问题的评价涵数的构造: g(d)定义为从源到结点d所走的路径长度: g(d)=g(p)+ clplld 这里p为d的前驱结点,C[p]d为p到d的距离 h(d)定义为0。于是d)=g(d) ■源s的评价函数f(s)=0 ■评价函数的下界为0;上界初始时为∞,以后不 断用取得的更短路径的长度来替代。 2021/221 计算机算法设计与分析 6
2021/2/21 计算机算法设计与分析 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；上界初始时为∞，以后不 断用取得的更短路径的长度来替代
分支限界法求最短路径举例 赋权图G Open表 Closed表 [5,60,3] 1,0,0] 100 [2,10,1 30 2 4,30,1] 50 [3,50,4 60 4 取出[5,60,3],因其已经是目标结点,算法成 功并终止。 依据逆向指针可得最短路径为1→4→3→5。 2021/221 计算机算法设计与分析
2021/2/21 计算机算法设计与分析 7 分支限界法求最短路径举例 1 2 5 3 4 10 20 50 100 30 10 60 赋权图G 初始时，将源[1, 0, 0]放入Open，Closed为空。 Open表 [1, 0, 0] Closed表 取出[1, 0, 0]放入Closed；生成其后继[2, 10, 1]、 [4, 30, 1]和[5, 100, 1]，并依序放入Open。 [5, 100, 1] [1, 0, 0] [4, 30, 1] [2, 10, 1] 取出[2, 10, 1]放入Closed；生成其后继[3, 60, 2]， 并依序插入Open。 [3, 60, 2] [2, 10, 1] [4, 30, 1] 取出[4, 30, 1]放入Closed；生成其后继[3, 50, 4] 和[5, 90, 4] ，修订Open中已有的两个结点并依 序排列。 [4, 30, 1] [5, 90, 4] [3, 50, 4] 取出[3, 50, 4]放入Closed；生成其后继[2, 100, 3] 和[5, 60, 3]，前者因劣于Closed中的[2, 10, 1]而 被抛弃，后者修订了Open中的[5, 90, 4]。 [3, 50, 4] [5, 60, 3] 取出[5, 60, 3]，因其已经是目标结点，算法成 功并终止。 依据逆向指针可得最短路径为1→4→3→5
界限( Bounding) 评价函数f(d)关系着算法的效率乃至成败 因为在大多数问题中fd)只是个估计值,所以 单靠fd)是不够的。通常还要设计它的上下界 函数U(d)和L(d)。L(d)≤fd)≤U(d) ■所谓分支限界法就是通过评价函数及其上下界 函数的计算,将状态空间中不可能产生最佳解 的子树剪去,减少搜索的范围,提高效率。因 而更准确的称呼应是“界限剪支法” 2021/22 计算机算法设计与分析
2021/2/21 计算机算法设计与分析 8 界限(Bounding) ◼ 评价函数f(d)关系着算法的效率乃至成败。 ◼ 因为在大多数问题中f(d)只是个估计值，所以 单靠f(d)是不够的。通常还要设计它的上下界 函数U(d)和L(d)。 L(d)≤f(d)≤U(d)。 ◼ 所谓分支限界法就是通过评价函数及其上下界 函数的计算，将状态空间中不可能产生最佳解 的子树剪去，减少搜索的范围，提高效率。因 而更准确的称呼应是“界限剪支法
用分支限界法求TSP ■TSP是求排列的问题,不是仅找一条路径而已 因而需要对分支限界法的一般算法作些修改: (1)待扩展的结点如果在本路径上已经出现,则 不再扩展,但若是在其他路径上出现过,则仍 需要扩展。 (2)新结点,无论其优劣,既不影响其它路径上 的结点,也不受其它路径上的结点的影响。 (3)依据上界函数决定结点是否可以剪去。 2021/221 计算机算法设计与分析 9
2021/2/21 计算机算法设计与分析 9 用分支限界法求TSP ◼ TSP是求排列的问题，不是仅找一条路径而已。 因而需要对分支限界法的一般算法作些修改： ◼ (1)待扩展的结点如果在本路径上已经出现，则 不再扩展，但若是在其他路径上出现过，则仍 需要扩展。 ◼ (2)新结点，无论其优劣，既不影响其它路径上 的结点，也不受其它路径上的结点的影响。 ◼ (3)依据上界函数决定结点是否可以剪去
分支限界法求排列 ■(1)计算初始结点s的fs),[s,f(s),n放入Open; ■(2)whle(Open约){ (3)从Open中取出[p,f(p),L];M是路径已有结点 ■(4)若fp)U,则抛弃该路径 (5)若p是目标,则考虑修改上界函数值;否则 (6){将[p,f(p),D放入 Closed; 在该路径上扩展结点p:对每个后继d (8){计算f(d) (9)若f(d)<U,则{L=L∪{p} 将[d,fd,L]依序放入Open。} 2021/221 计算机算法设计与分析 10
2021/2/21 计算机算法设计与分析 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。} ◼ } } }