历史回顾

搜索算法在人工智能研究的早期就出现并展现其威力。Newell和Simon分别在1957年和1961年将搜索算法应用于军事领域，包括早期的GPS等重要项目和研究。

盲目搜索算法是20世纪60—70年代经典计算机科学和运筹学的中心问题之一。宽度优先搜索最早由Moore于1959年正式提出，用于解决迷宫问题。1957年由Bellman提出的动态规划算法也可以看作是宽度优先搜索的一个变种。

启发式搜索最早可以追溯到1958年Newell和Simon有关启发式信息的论文。启发式算法中经典的A^*算法由Hart，Nilsson和Raphael三人在1968年提出，并由Nilsson在1972年做出修正。1985年由Korf提出的IDA^*算法是对A^*算法的进一步改进之一，能够在给定内存限制的情况下执行，因此被广泛采用。同样基于A^*算法的D^*算法由Stentz于1994年提出，可以处理环境动态变化的情况。D^*算法被成功应用于火星探测器的寻路，并且帮助卡耐基·梅隆大学于2007年取得DARPA自动驾驶挑战赛的冠军。

最早的局部搜索算法可以追溯到牛顿时代。由牛顿和Raphson分别独立提出的牛顿法可以看作是最早的基于梯度的局部搜索算法。局部搜索算法在20世纪90年代早期重新得到重视，并出现了一系列的基于爬山法的改进算法，如1994年提出的Tabu搜索算法和1997年提出的STAGE算法等。

对抗式搜索则与博弈论的发展密切相关。极小极大算法可追溯到Ernst Zermelo于1912年发表的论文，博弈论中大名鼎鼎的Zermelo定理也在该论文中提出。1956年John MacCarthy最早构思了Alpha-Beta剪枝搜索，并由Hart和Edwards于1961年正式提出。1979年提出的SSS^*算法对Alpha-Beta剪枝搜索进行了改进，可被看作是A^*算法对应的多智能体版本。对抗式搜索被广泛应用于博弈问题的求解，包括国际象棋、围棋、桥牌、德州扑克等。1958年Newell等人最早在国际象棋程序NSS中使用了简化版本的Alpha-Beta搜索。1996年，Deep Blue使用并行化的Alpha-Beta剪枝搜索，击败了国际象棋冠军卡斯帕罗夫。2016年，AlphaGo将蒙特卡洛树搜索与深度神经网络结合，成功击败了世界围棋冠军李世石。

搜索问题是人工智能研究的核心问题之一，目前已有许多成熟的结果，并在诸多实际问题中得到了广泛的应用。但同时，领域内依然有若干深入的问题有待发展。结合实际问题，探索有效实用的搜索策略，仍是研究和开发的一个活跃领域。