《人工智能》第三章：搜索算法问题求解

问题求解算法的性能

• 完备性：当问题有解时，这个算法是否能保证找到解？
• 最优性：搜索策略是否能找到开销最小的最优解？
• 时间复杂度：找到解需要花费多长时间？
• 空间复杂度：在执行搜索的过程中需要多少内存？

概念：

• 典型度量方式：状态空间图大小，|V|+|E|，其中V是图中顶点（结点）的集合，E是图中边（连接）的集合。
• 复杂度通常由三个量确定
  b，分支因子，或者说任何结点的最多后继
  d，目标结点所在的最浅深度（根节点到目标状态的步数）
  m，状态空间中任何路径的最大长度
  时间由搜索过程中产生的结点数目来度量，而空间由在内存中存储的最多结点数来度量。一般用来描述搜索树，对于图，这个方法依赖于状态空间中的路径有多冗余。

评价搜索算法的有效性

搜索代价：通常取决于时间复杂度，包括内存的使用
总代价：包括求解的搜索代价和解路径的路径代价。

一、无信息搜索策略

无信息搜索也称盲目搜索，指的是除了问题定义中提供的状态信息外没有任何附加信息。知道一个非目标状态是否比其他状态“更有希望”接近目标的策略称为有信息搜索策略或者启发式搜索策略

1、宽度优先搜索

• 宽度优先就是简单搜索策略，先拓展根节点，接着扩展根节点的所有后继，然后再扩展它们的后继，以此类推。
  一般来说，在下一层的任何结点扩展之前，搜索树上本层深度的所有结点都应该已经扩展过。

1.1 实现方法：FIFO队列

1.2 评价

• 宽度优先搜索是完备的
• 若可以找到目标节点，那么一定是最浅的目标节点，最浅的目标节点不一定就是目标节点
• 如果路劲是非递减函数，宽度搜索是最优的

时空复杂度

最坏情况下，解是最后一层结点
此时结点数：$b+b^2+b^3+...+b^d=O(b^d)$b+b2+b3+...+bd=O(bd)

• 空间复杂度：对宽度有限搜索，每个生成的结点都存在内存中，有$O(b^{d-1} )$O(bd−1)都在探索集中，$O(b^d )$O(bd)个结点在边缘节点集中，所以空间杂度为$O(b^d)$O(bd)，由边缘节点集决定

• 时间复杂度为$O(b^d)$O(bd)

• 时空复杂度高

• 当每一步的行动代价都相等时宽度优先搜索是最优的，因为它总是先扩展深度最浅的未扩展结点。更进一步，我们可以找到一个对任何单步代价函数都是最优的算法。

2、一致代价搜索

一致代价搜索扩展的是路径消耗g(n)最小的结点n。可以通过将边缘结点集组织成按g值排序的队列来实现。

• 使用优先队列并在边缘中的状态发现更小代价路径时引入了额外的检查
• 扩展未扩展结点中代价最小的
  实现：队列按照代价从小到大排列
  
  一致代价与宽度优先相比：

1. 目标检测应用于结点被选择扩展时，而不是生成时使用
2. 如果边缘中的结点有更好的路径到达该结点那么会引入一个测试

评价

• 一致代价搜索是完备的
• 一致代价与宽度优先搜索相比，一致代价会检查目标深度的所有结点看谁的代价最小，所以最后结果是最优的
• $C^*$C∗代表最优的代价$^2$2,假设每个行动的代价至少为e，最坏情况下， 时空复杂度都为$O(b1+lowbound(C^*/e))$O(b1+lowbound(C∗/e))

3、深度优先搜索

深度优先总是扩展搜索树的当前边缘结点集中最深的结点。
搜索很快到达树的最深层，那里的结点没有后继，当那些结点扩展完之后，就从边缘结点集中去掉，然后搜索算法回溯到下一个还有未拓展后继的深度稍浅的结点。
实现：LIFO（栈）存储节点




深度优先搜索算法的效率严重依赖于使用的是图搜索还是树搜索。

评价

• 避免重复状态和冗余的图搜索，在有限的状态空间内是完备的，因为它至多扩展所有结点
• 树搜索不完备，陷入死循环，遭到无限的又无法到达目标结点的路径，图和树都会失败。
• 空间$O(bm)$O(bm)

4、深度受限搜索&&迭代加深

深度受限：深度为 L的结点被当作没有后继来对待，深度界限解决了无穷路径的问题。
迭代加深的深度：不断增大深度限制——首先为0，下一个是1,2,…直到找到目标，当深度界限达到d，即最浅的目标节点所在深度时，找到目标节点。

深度受限：

• 如果我们选择(L<d), 最浅的目标节点深度超过深度界限，那么这种搜索是不完备的
• 如果(L>d)，深度受限搜索同样也不是最优的。
• 时间复杂度为$O(B^l)$O(Bl)，空间是$O(Bl)$O(Bl)。
  深度遍历可看成无穷深度的深度受限搜索。

迭代加深的深度搜索：结合了宽度和深度优点

• 空间复杂度：$O(bd)$O(bd)
• 时间复杂度：$O^{b^d}$Obd
• 结合深度和广度特点，当路径代价是结点深度的非递减函数时算法最优。

无信息搜索对比

5、双向搜索

同时运行两个搜索—一个从初始状态向前搜索，同时另一个从目标状态向后搜索——希望它们在中间某点相遇，此时搜索停止

• 时间、空间复杂度：$b^{d/2}$bd/2
• 实现：目标测试替换为检查两个方向的搜索边缘点集是否相交；如果交集不为空就找到一个解，这样的解可能不是最优解，两个方向都是采用宽度优先搜索；保证最短路径还需要额外的搜索。

二、有信息（启发式）搜索策略

有信息搜索策略：使用问题本身的定义之外的特定知识——比无信息的搜索策略更有效地进行问题的求解。
最佳优先搜索
最佳优先搜索是一般 TREE-SEARCH 和GRAPH-SEARCH算法的一个实例，结点是基于评估函数$f(n)$f(n)值被选择扩展

• 基本思路：通过对每一个结点计算评估函数f(n)值，找到一个f(n)最低的未扩散的结点
• 实现：队列中，结点按照评价函数值从低到高排序
• 大多数评价函数由启发式函数h构成：h(n)表示结点到目标结点的最小代价估计值

1、贪婪最佳优先搜索

贪婪最佳优先搜索试图扩展离目标最近的结点，只需要启发式信息

• 罗马尼亚问题：使用两点之间的直线距离$h_{SLD}$hSLD​来估测两点之间的实际距离。
  
  
  使用$h_{SLD}$hSLD​的贪婪最佳优先搜索在没有扩展任何不在解路径上的结点前就找到了问题的解；所以，它的搜索代价是最小的，但不是最优的——每一步都试图找到离目标最近的点

评价

• 完备性：不完备，与深度优先搜索类似，即使是有限状态空间，也是不完备的。
• 不是最优的
• 时间复杂度和空间复杂度都是$O(b^m)$O(bm)，m是搜索空间的最大深度，如果有一个好的启发式函数，复杂度可以降低

2、$A^*$A∗搜索：缩小总评估代价

$A^*$A∗搜索对结点的评估结合了$g(n)$g(n)，即到达此结点已经花费的代价，和$h(n)$h(n)，从该结点到目标节点所花的代价：
$f(n)=g(n)+h(n)$f(n)=g(n)+h(n)
$g(n)=$g(n)=到达结点n已经花费的代价
$h(n)=$h(n)=结点n到目标结点的最小代价路劲的估计值
$f(n)=$f(n)= 经过结点n的最小代价解的估计代价
假设$h(n)$h(n)满足特定的条件，A搜索既是完备的页是最优的，算法与一致代价搜索类似，除了A使用$g+h$g+h而不是g

保证最优性的条件：可采纳性和一致性

• 可采纳启发式指它不会过高估计到达目标的代价
• 一致性（单调性），如果对于每个结点n，$h(n)&lt;h^*(n)$h(n)<h∗(n)，$h^*(n)$h∗(n)是指到目标节点的真实代价
  
• 定理（最优）：如果$h(n)$h(n)是一致的，A*使用图搜索是最优的
• 完备性：每步的代价都大于某个常数e，并且分支数b是有限的
• 时间、空间复杂度$O(b^▷)$O(b▷)