2022/12/6 计算机算法设计与分析 1第六章分支限界法2022/12/6 计算机算法设计与分析 2分支限界法是最佳优先搜索法n 分支限界法就是最佳优先( 包括广度优先在内)的搜索法。n 分支限界法将要搜索的结点按评价函数的优劣排序，让好的结点优先搜索，将坏的结点剪去。所以准确说，此方法应称为界限剪支法。n 分支限界法中有两个要点：n (1) 评价函数的构造；n (2) 搜索路径的构造。2022/12/6 计算机算法设计与分析 3评价函数的构造n 评价函数要能够提供一个评定候选扩展结点的方法，以便确定哪个结点最有可能在通往目标的最佳路径上。n 一个评价函数f(d) 通常可以由两个部分构成：从开始结点到结点d的已有耗损值g(d) ，和再从结点d到达目标的期望耗损值h(d) 。即：f(d) = g(d) + h(d)n 通常g(d) 的构造较易，h(d) 的构造较难。2022/12/6 计算机算法设计与分析 4搜索路径的构造n 在回溯法中，每次仅考察一条路径，因而只需要构造这一条路径即可：前进时记下相应结点，回溯时删去最末尾结点的记录。这比较容易实现。n 在分支限界法中，是同时考察若干
