什么是搜索问题？
许多AI问题都可以表述为状态空间搜索：可能的情形是状态，在状态间转移的动作是算子，任务是找到一串从初始状态到达目标状态的算子。路径规划、谜题、机器人路径规划以及国际象棋等博弈都属于此类。机器“智能地”解决问题的想法，可以追溯到围绕AI定义的图灵测试之争。
无信息搜索
- 广度优先搜索（BFS）：先扩展离初始状态最近的状态。当每一步代价相同时能找到最短路径，但占用大量内存。
- 深度优先搜索（DFS）：沿一个分支走到底再回溯。内存占用少，但不保证最短路径，在无限空间中可能迷失。
- 一致代价搜索／Dijkstra算法：扩展当前已花费代价g(n)最低的状态。Dijkstra（1959年）证明，当代价非负时，这样能找到最短路径。
A*算法
A*由斯坦福研究所的彼得·哈特、尼尔斯·尼尔森和伯特伦·拉斐尔于1968年发表，源于Shakey机器人的路径规划。它按以下评价函数的值由小到大扩展状态。
f(n) = g(n) + h(n)
- g(n)：从初始状态到n的实际代价。
- h(n)：从n到目标剩余代价的启发式估计，如地图上的直线距离或网格上的曼哈顿距离。
- 可采纳性：若h(n)从不高估真实剩余代价，A*保证找到最优路径。
- 一致性：若相邻状态之间h的下降不超过步骤代价，则无需重新扩展任何状态，效率更高。
- 当h(n)=0时，A*退化为Dijkstra算法；启发式越准确，扩展的状态越少。
博弈搜索：极小化极大
在双人博弈中，对手也在争取胜利。极小化极大算法对博弈树的叶节点（或固定深度的局面）打分，然后在己方回合（MAX）向上传递最大值，在对方回合（MIN）向上传递最小值，以选出最佳走法。其理论基础是冯·诺依曼1928年的极小化极大定理，克劳德·香农1950年的论文则提出将其与评价函数结合，让计算机下国际象棋。
Alpha-Beta剪枝
极小化极大要检查整棵树，代价随深度爆炸式增长。Alpha-Beta剪枝记录目前找到的最佳值（α：MAX能确保的最小值；β：MIN能确保的最大值），跳过不可能影响结果的分支。它以少得多的计算得出与极小化极大相同的答案；Knuth和Moore（1975年）证明，在走法排序完美时，检查的节点数大约降至平方根。
局限与后续发展
- 在围棋这样规模极大的博弈中，组合爆炸限制了极小化极大，由此出现了与神经网络评估相结合的蒙特卡洛树搜索。
- A*要把整个搜索前沿保存在内存中，因此大型问题会使用IDA*等节省内存的变体。
- 设计好的启发式和评价函数本身就很困难，需要领域知识。
参考文献
- von Neumann, J. (1928). Zur Theorie der Gesellschaftsspiele. Mathematische Annalen, 100, 295–320.
- Shannon, C. E. (1950). Programming a computer for playing chess. Philosophical Magazine, 41(314), 256–275.
- Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1, 269–271.
- Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100–107.
- Knuth, D. E., & Moore, R. W. (1975). An analysis of alpha-beta pruning. Artificial Intelligence, 6(4), 293–326.