小小总结几种搜索策略

Posted by liveipool on September 20, 2016

小小总结几种搜索策略

近日在上人工智能课程,其中有一章一口气讲了很多种搜索算法,虽然大致流程都懂了,但一些细节及原理可能理解得并不深刻,在此小小总结一下。 可能描述得非常简单,仅仅帮助记忆。
b: 分支因子,任何节点的最多后继数。
d: 目标结点所在的最浅的深度,(从根节点到目标状态的步数)。
m: 状态空间中任何路径的最大长度。
C*: 最优解的代价
e: 假设每个行动的代价至少为e
g(n): 从开始结点到结点n的真实路径代价
h(n): 从结点n到目标结点的最小代价路径的估计值
f(n): 评估函数

无信息搜索策略

无信息搜索也称为盲目搜索。它是指出了问题定义中提供的状态信息之外没有任何附加信息。搜索算法要做的是生成后即并区分目标状态与非目标状态。这些搜索策略是以结点扩展的次序来分类的。

宽度优先搜索

(breadth-first search)BFS:是简单的搜索策略,先扩展根节点,接着扩展根节点的所有后继,然后再扩展它们的后继。 a1.png
宽度优先搜索十一班的图搜索算法的一个实例,每次总是扩展深度最浅的结点。这可以通过将边缘组织成FIFO队列来实现。目标的测试是在结点被生成的时候,而不是节点被选择扩展的时候。
BFS的时间和控件耗费都很高,它的时间复杂度为O(b的(d+1)次方) ,空间复杂度为O(b的d次方),这两个复杂度都是高得让人头疼的。

一致代价搜索

(uniform-cost search):当每一步的行动代价都相等时宽度优先搜索是最优的,因为它总是先扩展深度最浅的未扩展节点。而一致代价搜索扩展的是路径消耗g(n)最小的结点n。
它和BFS的不同在于:目标检测应用于节点被选择扩展时,而不是在生成的时候进行。
一致代价搜索由路径代价而不是深度来引导,所以算法复杂度不可能简单地使用b和d来表示。最坏的情况下,时间和空间复杂度为O(b的(1+(C*/e))次方)。
一致代价搜索与宽度优先搜索类似,除了算法终止条件,BFS在找到解时终止,而一致代价搜索则会检查目标深度的所有节点,看谁的代价嘴下;这样,在这种情况下一致代价搜索在深度d无意义地做了更多的工作。

深度优先搜索

(depth-first search)DFS总是扩展搜索树的当前边缘结点集中最深的结点。

depth-first search.png
BFS使用FIFO队列,DFS使用LIFO队列
DFS算法的效率严重依赖于使用的是图搜索还是书搜索。避免重复状态和荣誉路径的图搜索,在有限状态空间是晚辈的,因为它至多扩展所有节点,而树搜索则不完备,算法可能会进入死循环。DFS可以改成无需额外内存耗费,它只检查从根节点到当前结点的新结点,这避免了有限状态空间的死循环,但无法避免冗余路径。在无限状态空间中,如果遭遇看无限的又无法到达目标结点的卢杰,无论是图搜索还是树搜索都会失败。
DFS的时间复杂度受限于状态空间的规模,深度优先的树搜索,可能在搜索树上生成所有O(b的m次方)个结点。
而DFS相比于BFS,在空间复杂度上有优势。它只需要存储O(bm)个结点。

深度受限搜索

在无限状态空间的DFS会失败,而这个问题可以通过对DFS设置界限 l 来避免。就是说,深度为 l 的结点被当作没有后继对待。这种方法称为深度受限搜索(depth-limited search)
不幸的是,如果l < d,即最浅的目标结点的深度超过了最深限制,那么这种搜索算法是不完备的。如果l > d,那么深度受限搜索也不是最优的。它的时间复杂度是O(b的 l 次方),空间复杂度是O(bl)。

迭代加深的深度优先搜索

(iterative deeping search)是一种常用策略,它使用不断增大深度限制来结合DFS使用,它结合了BFS和DFS的有点,空间需求是合适的:O(bd)。

双向搜索

(bidirectional search)的思想是同时运行两个搜索–一个从初始状态向前搜索,一个同时从目标状态向后搜索,思想是两个b的二分之d次方小于一个b的d次方。
双向搜索可以这样实现:目标测试替换为检查两个方向的搜索的边缘结点集是否相交,如果交集不为空就有解。
双向搜索的时间和空间复杂度都是O(b的二分之d次方)。
降低时间复杂度使得双向搜索很诱人,但如何向后搜索并不简单,并且如果目标状态是一种抽象描述的话,如n后问题的目标是“没有皇后攻击另一个皇后”,就很难使用双向搜索。
因此,双向搜索可以在很大程度上降低时间复杂度,但它不总是可行的并且可能需要太多的内存空间。

有信息(启发式)的搜索策略

知道一个非目标状态是否比其他状态“更有希望”接近目标的策略称为有信息搜索策略启发式搜索策略
(informed search):使用问题 本身的定义之外的特定知识,比无信息的搜索策略更有效地进行问题求解。
我们要考虑的一般算法称为最佳优先搜索,它是根据评估函数f(n)来选择扩展结点的。

贪婪最佳优先搜索

(greedy best-first search)试图扩展离目标最近的结点,理由是这样可能很快能找到解。因此,它只用启发式信息,即f(n) = h(n)。 在最坏的情况下,算法的时间复杂度和空间复杂度都是O(b的m次方)。然而,如果有一个好的启发式函数,复杂度可以得到有效降低。

A*搜索:缩小总评估代价

最佳优先搜索的最广为人知的形式称为A星搜索,它对结点的评估结合了g(n), 即:
f(n) = g(n) + h(n)
如果h(n)满足以下两个条件,A星算法就是完备且最优的(但空间复杂度依然很高):
一、可采纳性: **
第一个条件是h(n)是一个可采纳启发式。可采纳启发式是指它从不会过高估计到达目标的代价,也因此f(n)永远不会超过经过结点n的解的实际代价。
**二、一致性: **
第二个条件只作用于
图搜索中使用A星算法。如果对于每个结点n和通过任一行动a生成的n的每个后集结点N,从节点到达目标的估计代价不大于从n到N的单步代价与从N到达目标的估计代价之和:h(n) <= c(n, a, N) + h(N),这样我们就称启发式h(n)是一致性的。
即:
如果h(n)是可采纳的,那么A星的树搜索版本是最优的;如果h(n)是一致的,那么图搜索的A星算法是最优的**