高级人工智能总结--搜索

1. 搜索问题

搜索问题的构成：状态空间、后继函数（actions + costs）、初始状态和目标测试。解是一个行动序列，将初始状态转换成目标状态。搜索问题是对原问题的建模。

1.1. 状态空间

状态空间包含环境中的每一个细节，搜索状态只保留行动需要的细节。

状态空间

世界状态：

Agent positions : 120
Food count : 30
Ghost positions : 12
Agent facing : NSEW

状态数量：

世界状态：\(120 \times 2^{30} \times 12^{2} \times 4\)
路线规划状态：120

1.2. 状态空间图

搜索问题的数学表示：

Nodes are world configurations(abstracted)；
Arcs represent successors(action results)；
The goal test is a set of goal nodes(maybe only one)。

-c

状态空间图中每种状态只出现一次。几乎不在内存中构建完整的状态空间图。

1.3. 搜索树

搜索树：

根节点对应初始节点；
子节点对应父节点的后继；
节点显示状态，对应的是到达这些状态的行动；
对于大多数问题，实际上不会构建完整的搜索树。

状态空间图 vs 搜索树

基于搜索树的搜索：

扩展出潜在的行动（tree nodes）；
维护所考虑行动的边缘节点；
试图扩展尽可能少的树节点。

边缘节点：树中未处理的子节点。处理过程是扫描叶子节点并做判断，在未找到目标节点并且叶节点可扩展的情况下扩展出新的叶子节点，即产生边缘节点。

重要的ideas：

Fringe
Expansion
Exploration strategy

主要问题：对哪一个边缘节点进行扩展？？

1.4. 搜索算法特性

特性：

完备性：当问题有解时，是否能保证找到一个解；
最优性：保证能找到最优解（最小耗散路径）；
时间复杂度
空间复杂度

2. 无信息搜索

2.1. 深度优先搜索（DFS）

-c500

DFS会优先扩展树中靠左的节点，直到遍历树中所有节点。
利用栈结构实现（LIFO）。
时间复杂度：\(O(b^m)\)
空间复杂度：\(O(bm)\)（只需保留路径上的节点和它们的兄弟节点）
完备性：不具备，如果状态图中不含有环，那么m是有限的。
最优性：不具备，会找到搜索树中最左边的目标节点，不考虑搜索深度和代价。

2.2. 广度优先搜索（BFS）

-c500

BFS优先扩展树中最浅的节点，直到遍历树中的所有节点。
利用队列实现（FIFO）。
时间复杂度：\(O(b^s)\)
空间复杂度：\(O(b^s)\)（大约需要保存最后一层的所有节点）
完备性：具备，如果存在路径，那么s一定是有限的。
最优性：只有在每一步行动的代价为1时最优。（路径最短）

2.3. 迭代深入搜索（Iterative Deepening）

-c350

思想：结合DFS的空间优势和BFS的时间优势。

在搜索深度限制为1的情况下运行DFS，如果没有结果...
在搜索深度限制为2的情况下运行DFS，如果没有结果...
在搜索深度限制为3的情况下运行DFS，...

存在浪费冗余现象，即上层节点多次遍历，但是大部分节点都在底层，所以上层节点生成多次影响不大。

2.4. 代价一致搜索（Uniform Cost Search）

-c500

策略：寻找代价最小的节点进行扩展。利用优先队列实现。

会遍历所有搜索代价小于最优路径所需代价的节点。
如果最优路径的代价为\(C^*\)，图中边的最小代价为\(\varepsilon\)，则搜索的有效深度为\(C^*/ \varepsilon\)。
时间复杂度：\(O(b^{C^*/ \varepsilon})\)
空间复杂度：\(O(b^{C^*/ \varepsilon})\)
完备性：具备（条件：最优路径的代价有限并且图中边的最小代价为正值）
最优性：具备
优点：完备性，最优性
缺点：（i）在每一个方向上进行搜索（ii）没有关于目标的信息

2.5. 搜索算法的比较

（1）所有的搜索算法都是相同的，除了对边缘的处理策略；
（2）从概念上说，所有的边缘都是优先队列（即附加优先级的节点集合）；
（3）对于DFS和BFS，可使用栈和队列代替优先队列，减少log(n)的开支；
（4）比较： -c500

3. 启发式搜索

启发策略：

估计一个状态到目标距离的函数；
问题给予算法的额外信息，为特定搜索问题设计；
例如：曼哈顿距离，欧氏距离。

示例： -c500

3.1. 贪婪搜索

-c350 策略：扩展离目标状态最接近的节点（估计）

启发式：对每个状态估计到最近目标的距离；
只使用启发函数\(f(n)=h(n)\)来评价节点。

完备性：不具备最优性：不具备通常情况：选择最佳路线到达目标节点。最坏情况：类似于DFS。

3.2. \(A^*\)搜索

-c500

结合UCS和Greedy：

Uniform cost：已经历过的路径的代价，backward cost g(n)；
Greedy：距离目标节点的估计距离，forward cost h(n)。

结束条件：当目标节点出优先队列时停止。

3.2.1. 可采纳启发

启发函数\(h\)是可采纳的，那么： \[0 \leq h(n) \leq h^*(n)\] 其中\(h^*(n)\)是到最近目标节点的真实代价。
可采纳的启发函数是\(A^*\)算法实际使用中的重点。
通常，可采纳启发函数是松弛问题的解的代价。

3.2.2 启发函数

-c120

底层：零启发式
占优势：\(h_a \geq h_c\) if \(\forall n:h_a(n) \geq h_c(n)\)
可采纳的启发函数组合：\(h(n)=\max({h_a(n),h_b(n)})\)
顶层：精确启发式

3.2.3 \(A^*\)算法最优性证明

-c350 假定A是最优目标节点，B是次优目标节点，h是可采纳的，证明A在B之前离开边缘集合。

证明： 假设B在边缘集合上，A的某个祖先节点n也在边缘集合上，定义目标节点的h(n)值为0： \[\begin{eqnarray} f(n)&=&g(n)+h(n) \nonumber \\ f(n) &\leq& g(A) \nonumber \\ g(A)&=&f(A) \nonumber \end{eqnarray}\] 所以有： \[f(n) \leq f(A)\] 又因为： \[\begin{eqnarray} g(A) < g(B) \nonumber \\ f(A) < f(B) \nonumber \end{eqnarray}\] 得到： \[f(n) \leq f(A) < f(B)\] 那么n将在B之前扩展，A的所有祖先将在B之前扩展，A也将在B之前扩展，所以\(A^*\)是最优的。