搜索

一个问题可以用如下部分描述：

1. 初始状态 s
2. 可能行动 a
3. 转移模型 RESULT(s, a) 生成一个状态的后继状态
4. 目标测试，是否到达目标状态
5. 路径耗散

无信息搜索

无信息搜索是指除了问题定义中提供的状态信息外没有任何附加信息。

1. 广度优先搜索
2. 一致代价搜索，在广度搜索的基础上，总是扩展路径消耗最小的的节点
3. 深度优先搜索
4. 深度受限搜索，在无限状态空间中，对深度优先搜索设置界限 \(l\)，如果最浅的目标节点深度超过了界限，则搜索是不完备的

5. 迭代加深的深度优先搜索，不断增大深度界限，并进行深度受限搜索，直至达到目标节点的最浅深度。尽管状态被重复生成，其实际时间复杂度与广度优先搜索相近

   \[ d·b+(d-1)b^2+\dots+1·b^d=O(b^d) \]

   空间复杂度与深度优先搜索相近，即 \(O(d)\). 6. 双向搜索，同时从初始状态向前和从目标状态向后搜索，目标测试替换为检查两个方向的搜索的边缘节点集是否相交，时间复杂度为 \(O(b^{d/2}+b^{d/2})\lt O(b^d)\).

启发式搜索

参考

• 人工智能：一种现代的方法. 第3版