搜索求解之启发式搜索策略

启发式搜索也叫有信息搜索策略,区别于前面的无信息搜索。她指使用问题本身的定义之外的特定知识,这将更有效的进行求解。

考虑一个一般算法称为最佳优先搜索(best first search)。最佳优先是树搜索或图搜索的一个实例。

这里插入提一下树搜索和图搜索,树搜索

1.利用初始状态初始化边缘节点集(通常为初始状态的子节点)
2.如果边缘节点为空,则返回搜索失败
3.选择一个叶节点,并将她从边缘节点集移除
4.如果这个节点是解,那么搜索结束
5.扩展这个节点,把扩展节点加入到边缘节点,回到第二步

图搜索

1.利用初始状态初始化边缘节点集(通常为初始状态的子节点)
2.初始化已测试节点为空
3.如果边缘节点为空,则搜索失败
4.选择一个叶节点,并将他移除边缘节点集
5.如果这个节点是解,搜索结束,返回解
6.把这个节点加入到已测试节点集
7.扩展这个节点,把扩展的节点加入到边缘节点 (仅仅这个节点不再已测试节点集或者边缘节点时),回到第3步

由上面的算法看出,图搜索可以避免树搜索中的死循环问题。

最佳优先搜索中,节点是基于评价函数f(n)来进行选取的,评估函数被称为是代价估计,代价最低的节点被优先选择进行扩展,她与一致代价搜索类似,不同的是,最佳优先是根据f值而不是g值(耗散值)进行优先排队的。

大多数的最佳优先算法的f由启发函数h(n)构成,

h(n)=节点n到目标节点的最小代价路径的代价估计值。

注意这里的h(n)与g(n)是不同的,g(n)表示初始状态到当前节点的耗散值,而h(n)表示的是当前节点到目标节点的最小代价估计值,因为这个路径此时是待解的,只能是一个估计值。这个估计值并不是对每个问题都可估计,因此对一个问题,如果当前节点到目标节点可估计,那么这个问题就可以使用最佳优先算法来进行搜索。

贪婪最佳优先搜索:该策略视图扩展距离目标最近的节点,她使用f(n)=h(n)。 这种算法不完备也不是最优。因为经常这个算法会收敛到局部极大值而找不到全局的最大值。

A*搜索:她的评估函数由两部分组成,f(n) =g(n)+h(n). 即f(n)表示经过节点n的最小代价解的估计代价。该搜索如果要达到最优,其h(n)必须满足一定的条件:可采纳行和一致性。

h(n)可采纳性是指她不会过高估计到达目标的代价,即f(n)=g(n)+h(n)永远不会超过经过节点n的解的实际代价。

h(n)的一致性是指,对于每个节点n和通过任一单步行动a,达到n’ 。从节点n到达目标的估计代价不大于从n到n’的单步代价与n’到目标的估计代价之和,也就是                          h(n) <= c(n,a,n’) + h(n’)
c(n,a,n’) 表示从n经过action a到达n‘的耗散值。

通过上面的定义,我们有A*的树搜索算法是最优的,如果h(n)是可采纳的。 A*的图搜索是最优的,如果h(n)是一致的。

具体的证明可以在书中找到。这里一致性实际上是个比较强的条件,而且为了找到最优解,算法必须探索所有的f(n)<C*的节点,这里C*表示最优解的耗散值。有时候,这个节点数也太大。

为了解决A*搜索的内存问题,我们给出递归最佳优先搜索(RBFS)。这中搜索算法类似于深度优先,但是在某个节点的搜索过程中,如果其f值超出了当前节点的祖先节点给定的f_limit值,那么搜索会切换到另一棵f_limit更小的子树,删除当前子树,释放内存。同时会把这棵子树上已搜索的最小f_limit标在当前路径的节点上。以便于今后决定是否要重新搜索此子树。

(注:注意这里的f是一个随深度递增的函数,因此探索层次越深,这个f值就会越大,因此原本f值较小的子树随着搜索层次的加深,f值会变得大于旁边子树,此时就需要切换到旁边子树去了,而旁边子树随着探索层次的加深,可能会又变得大于其他子树了,因此这个算法存在子树来回切换,重新生成大量节点的问题。当然,这个算法和A*一样是完备的,最优的)

最后介绍一种折衷的算法,SMA ,即简化的内存受限算法(这里没有介绍MA,即内存受限算法),在A*算法中,需要记录下当前所有的边缘节点,并对这些节点的f值进行排序。去最小f节点进行扩展。SMA中,并不保留所有的边缘节点,她在加入新的节点时,会把边缘节点中f值最大的值删除。在删除这个节点的同时,和RBFS一样,会回填一个f值给自己的父节点。SMA和RBFS相比,存储了更多的边缘节点,最大限度的利用了内存。但也存在重新生成子树的问题。

 



本文地址: http://www.bagualu.net/wordpress/archives/3424 转载请注明




“搜索求解之启发式搜索策略”的一个回复

发表评论

电子邮件地址不会被公开。 必填项已用*标注