界限( 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)。 ◼ 所谓分支限界法就是通过评价函数及其上下界 函数的计算，将状态空间中不可能产生最佳解 的子树剪去，减少搜索的范围，提高效率。因 而更准确的称呼应是“界限剪支法