第六章
分支限界法
分支限界法是最佳优先搜索法
分支限界法就是最佳优先(包括广度优先在内)的搜索法.
分支限界法将要搜索的结点按评价函数的优劣排序,让好的结点优先搜索,将坏的结点剪去.所以准确说,此方法应称为界限剪支法.
分支限界法中有两个要点:
(1)评价函数的构造;
(2)搜索路径的构造.
评价函数的构造
评价函数要能够提供一个评定候选扩展结点的方法,以便确定哪个结点最有可能在通往目标的最佳路径上.
一个评价函数f(d)通常可以由两个部分构成:⑴从开始结点到结点d的已有耗损值g(d),和⑵再从结点d到达目标的期望耗损值h(d).即:
f(d) = g(d) + h(d)
通常g(d)的构造较易,h(d)的构造较难.
搜索路径的构造
在回溯法中,每次仅考察一条路径,因而只需要构造这一条路径即可:前进时记下相应结点,回溯时删去最末尾结点的记录.这比较容易实现.
在分支限界法中,是同时考察若干条路径,那么又该如何构造搜索的路径呢
对每一个扩展的结点,建立三个信息:
(1)该结点的名称;
(2)它的评价函数值;
(3)指向其前驱的指针;
这样一旦找到目标,即可逆向构造其路径.
用一个表保存准备扩展的结点,称为Open表.
用一个表保存已搜索过的结点,称为Closed表.
分支限界法的一般算法
⑴计算初始结点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
有二种情况:
①d Closed || d Open;
②d Open && d Closed.
⑺ {若([d, f'(d), p] Closed || [d, f'(d), p] Open)
&& f(d)
⑻ 将[d, f(d), p] 插入到Open中}}}.
分支限界法求单源最短路径
单源最短路径问题的评价函数的构造:
g(d)定义为从源s到结点d所走的路径长度: