分支限界法求单源最短路径 ■单源最短路径问题的评价涵数的构造: 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)依据上界函数决定结点是否可以剪去