经典搜索算法
问题求解Agent的一般形式
一个问题(Problem)可以由5个组成部分形式化描述：
1. Agent的状态\(S\)和初始状态\(s_0\in S\)
2. Agent可能的行动Actions，给定状态s，Agent可以应用的行动包括\(a\in Actions(s)\)
3. 转移模型(transition model) \(Result(s, a):S\times A\to S\)
4. 目标测试(Goal test). 检查当前状态是否已达目标，可以是显示集合也可能是隐式表达式
5. 路径好散函数(cost) \(c:S\times A \times S\to R_{\ge 0}\), 描述某组状态和动作的代价\(c(s,a,s')\).
问题的解是从初始状态到目标状态到一组行动序列。
搜索求解
先约定一些记号：用F(frontier)存储当前搜索的结点集合（如栈，队列），R(reached)存储已经搜索过的结点。用b(branch)表示搜索树中所有结点的子结点个数最大值， d(depth)表示最优解的搜索深度，m表示搜索空间的最大深度(可能是\(\infty\)). 对于结点s，约定\(g(s)\)为当前到达s的路径的损失。当有启发式信息时，用\(h(s)\)表示当前结点到目标结点的最小代价路径的估计值。
搜索策略的性能主要由以下几方面评价：
1. 完备性(completness): 问题有解时，是否一定能得到解；
2. 最优性(optimality): 有解时，得到的解是否一定是最优（代价最小的）
3. 时间复杂度
4. 空间复杂度
无信息搜索
1. 广度优先搜索(Breadth-first search)
每次扩展当前F中深度最浅的点。
当F非空时，选择F第一个点s，根据s下所有可行的动作得到一组新的s', 检验其中是否有已经达到目标的结点；若否，将s'都加入F的末尾，并将s加入R中(下同)。
完备性：True, 最优性：每步代价为1时 True
时间：\(O(b^{d+1})\), 空间\(O(b^{d+1})\)
2. 一致代价搜索(uniform-cost search)
每次扩展路径消耗\(g(n)\)最小的结点。通过对边缘结点集F的路径损失值g进行排序，并选择其中代价最小的点进行扩展。
完备性：当每个行动有一致下界\(\epsilon\)时True,否则可能进入无行动循环。 最优性：完备性成立时True
时间：\(O(b^{[C^*/\epsilon]+1})\), 空间\(O(b^{[C^*/\epsilon]+1})\), \(C^*\)为最优解的代价。
3. 深度优先搜索(Depth-first search)
每次选择F中最深的点进行扩展。
完备性：无穷深度的搜索空间下为False，最优性：False
时间：\(O({b^m})\). 空间：\(O(bm)\)
4. 深度受限搜索\(Depth-limited search)
对深度优先搜索设置深度上限\(l\), 使得深度为\(l\)的结点没有后继。
5. 迭代加深搜索(Iterative deepening search)
对深度受限搜索中的深度上限进行\(0\to\infty\)迭代。
有信息（启发式）搜索
1. 贪婪最佳优先搜索(best-first search)
每次扩展启发式信息最小（距离目标估计最近）的结点。如罗马尼亚问题中，采用到目标的直线距离作为\(h(s)\).
完备性：结点有限且有访问集R检验时为True, 最优性：False
时间/空间：\(O(b^m)\)
2. \(A^*\)搜索
评估\(f(s) = g(s) + h(s)\)并选取最小的点进行扩展。
当启发式函数\(h(s)\)满足可采纳性时，树搜索\(A^*\)算法是最优的。
当启发式函数\(h(s)\)满足可采纳性、一致性时，图搜索\(A^*\)算法是最优的。
可采纳性(admissible): 不会过高估计到达目标的代价。若从结点n出发，到达目标的实际代价为\(h^*(n)\)，可采纳性要求\(h(n)\le h^*(n)\).
一致性(consistent/ monotonic):
\[h(n)\le c(n,a,n') + h(n'),\quad\forall a\]这个条件比可采纳性更强一些。
3. 递归最佳优先搜索(Recursive best-first search, RBFS)
最佳优先搜索，但是存储空间受限，只使用线性空间。
每扩展一个结点，用变量\(f_{limit}\)记录从当前结点的祖先可得到的最佳可选路径（初始化为同级结点中最佳）的f值。如果当前结点超过了这个限制，即当前的路径有更好的替代方案可以选择，递归将回到可选路径上。
如果递归回溯，对当前路径上每个结点，用其余子结点的最佳f值替换原来的f值。
因此，RBFS可以记住被遗忘的子树中，最佳叶结点的f值，用于决定以后是否值得重新扩展该子树。
所属分类：人工智能 发表于2022-05-13