感谢秦晓卫老师的指导！！

回顾

无信息搜索(Uninformed Search)：仅使用问题形式化定义所用的信息

最佳优先搜索需要定义一个评价函数 $f(n)$ ，不同的评价函数对应了不同的搜索算法。如评价函数可以为

若记 frontier 为边界节点集合，reached 为已达节点集合，那么最佳优先搜索可以描述如下

搜索策略的性能评估指标

为了评价一个搜索策略，考虑以下指标

为了衡量时间和空间复杂度，考虑以下指标

Note

BFS策略：优先扩展最浅的未扩展节点

广度优先搜索的评价函数为节点深度的负数。记分支因子为b，最浅的目标节点深度为d，那么时间复杂度为

1+b+b^2+\cdots+b^d+b(b^d-1)=O(b^{d+1})

空间复杂度也为 $O(b^{d+1})$ 。这是相当大的，不过当d有限时能确保找到解，并且状态转移代价为常数时找到的解为最优解（因为深度最小）

Note

UCS策略：优先扩展代价最小的未扩展节点

一致代价搜索的平均函数为路径的代价。在图论中UCS的一个实例是最短路算法Dijkstra

UCS的时间与空间复杂度取决于最优解的代价。记最优解的代价为 $C^*$ ，动作代价的下界为 $\epsilon$ ，则时间与空间复杂度为

O(b^{floor(C^*/\epsilon)+1})

它是完备的，并且找到的解是最优的

Note

DFS策略：优先扩展最深的未扩展节点

DFS的评价函数为节点的深度。朴素的DFS其时间复杂度为 $O(b^m)$ ，空间复杂度为 $O(bm)$ 。在有环的有限状态空间可能会陷入无限循环；无环无限状态空间可能会陷入无限路径，因而它不是完备的。只有在树型有限状态空间中DFS找到的解是最优的

为了解决DFS无限循环与无限路径的问题，可以设置一个深度上限 $l$ ，忽略所有深度大于 $l$ 的节点，即 深度受限搜索。不过这样的策略依然是不完备的，因为解的深度可能出现在 $l$ 以外，因此可以进行多轮搜索，每轮增加深度上限 $l$ 直到找到解，即迭代加深搜索

迭代加深搜索的时间复杂度为

(d+1)b^0+(d)b^1+(d-1)b^2+\cdots+b^d=O(b^d)

空间复杂度为 $O(bd)$

迭代加深搜索与深度优先搜索类似，不过空间复杂度要小得多。同样在状态转移代价为常数时找到的解是最优的