登录「搜索（search）」这个术语在人工智能领域内的意思主要是指驱动计算机/智能体的搜索算法，它们可以使计算机以人类的方式求解各种问题。搜索算法一般可以分成两类：无信息（uninformed）搜索和有信息（informed）搜索。其中有信息启发式搜索是相当流行的，因为它能根据一些指示快速找到解答。这一类别中包含一种最受欢迎的搜索算法：A*搜索。A*搜索可被定义为是一种（贪婪）最佳优先搜索（（greedy）best-first search）。其它的启发式（有信息）搜索算法还包括递归最佳优先搜索（RBFS）、简化有限内存A*（Simplified Memory-Bounded algorithm/SMA*）、蒙特卡洛树搜索（MCTS）和束搜索（Beam Search）。
无信息搜索算法包括宽度优先搜索、深度优先搜索、深度限制搜索、双向搜索和迭代深化搜索。启发式搜索算法有一个特定类别是局部搜索算法，其对于约束满足问题（CSP）尤其有效。流行的本地搜索算法还包括爬山算法、模拟退火算法、局部束搜索和遗传算法（随机束搜索的变体）。
除了用于传统优化问题的没有对手的单智能体搜索之外，还有特别专注于「针对不同一方进行规划」的搜索算法（比如，竞争性博弈问题），这种算法被称为对抗搜索算法（adversarial search algorithm）。对抗搜索问题所用的经典算法包括最小最大（Minimax）搜索和α-β剪枝。
[描述来源：Russell, S. J., & Norvig, P. (2010). Artificial Intelligence (A Modern Approach). ]
发展历史
描述
搜索算法的历史始于20世纪50年代人工智能的孕育时期，那时候人们关注的重点是问题求解。1959年Allen Newell和Herbert A. Simon开发了通用问题求解器（General Problem Solver，GPS）系统。该系统将从一个目标开始，然后将这个目标分解成子目标，再开始构建能够完成每个子目标的策略。1968年，斯坦福研究所（现为SRI国际）的Peter Hart，Nils Nilsson和Bertram Raphael首先在1968年描述了该算法。它是Edsger Dijkstra 1959年提出的提出Dijkstra算法的延伸。A *通过使用启发式指导搜索来实现更好的性能，目前已经是有信息启发式搜索中最流行的算法之一。1992年Russell提出了SMA*（Simplified Memory-Bounded algorithm/SMA*），是基于A*算法的最短路径算法。SMA的主要优点是它使用有界内存，而A *算法可能需要指数内存。SMA的所有其他特征都是从A*继承的。1993年，Richard E. Korf对BFS进行延伸，提出RBFS，将A*储存空间减小为线性增长。
1975年，John Holland的著作《自然系统和人工系统中的自适应（Adaptation in Natural and Artificial Systems）》普及了他所提出的遗传算法——这一算法用于是解决最优化问题的搜索算法，是进化算法的一种——其在随后几十年变得越来越流行。由于理论上讲遗传算法能够跳出局部最优而找到全局最优点，而且遗传算法允许使用非常复杂的适应度函数，并对变量的变化范围可以加以限制，目前遗传算法是搜索算法领域的经典之一。
大名鼎鼎的卡内基梅隆大学实验室设计的深蓝系统使用了α-β搜索驱动，并于1997年5月在比赛中击败卡斯巴罗夫，成为第一个在标准比赛时限内击败国际象棋世界冠军的电脑系统。2016年，DeepMind公司在Nature上发布了击败欧洲围棋冠军樊麾（Fan Hui）的AlphaGo版本论文，该项目由Martin Müller的学生David Silver和黄世杰，以及Demis Hassabis主持，结合深度神经网络和树搜索技术。3月，通过自我对弈进行练习的加强版AlphaGo在比赛中以4: 1击败了世界围棋冠军李世石，成为第一个在无让子情况下击败围棋职业九段棋手的计算机程序，并在之后不断刷新其所取得的最好成绩。
随着人工智能技术的不断突破，越来越多的搜索方法也被应用于人工智能领域。鉴于当前认知神经科学和人工智能工程所遇到的困难，华为2012实验室的研究人员提出了一种新的通用人工智能工程方法：使用学习算法的稳定性作为在特定场景中的适合度函数的启发式搜索方法。通过比较人工设计方法和仿生学方法，表明该方法更加有望实现通用人工智能，并且和认知神经科学有更好的交互作用。
主要事件
1959 | Allen Newell，Herbert A. Simon和Shaw创造了通用问题解算器（General Purpose Problem Solver/GPS）（目的是用作一种通用型的问题解算机器） | Newell A.; Shaw J. C.; Simon H. A.(1959). A variety of intelligent learning in a general problem solver. Rand cooperation. |
1968 | Peter Hart，Nils Nilsson和Bertram Raphael提出A*搜索使用两个代价函数作为目标函数 | 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. |
1975 | John Holland的著作《自然系统和人工系统中的自适应（Adaptation in Natural and Artificial Systems）》普及了遗传算法 | Holland, J. H. (1992).Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control and Artificial Intelligence.MIT Press. |
1992 | 1992年Russell提出了SMA*（Simplified Memory-Bounded algorithm/SMA*） | Russell, S. (1992). Efficient memory-bounded search methods.Proceedings of the 10th European Conference on Artificial intelligence. pp. 1–5. |
1993 | 1993年，Richard E. Korf对BFS进行延伸，提出RBFS，将A*储存空间减小为线性增长 | Korf, R. E. (1993).Linear-space best-first search.Artificial Intelligence.62(1):41-78. |
1997 | IBM用α-β搜索驱动的超级计算机「深蓝」在六局比赛中击败了世界国际象棋冠军Garry Kasparov | Campbell, M.; Hoane, A. J.; Hsu, F. H. (2002).Deep Blue.Artificial Intelligence.134(1–2):57-83. |
2016 | DeepMind公司在Nature上发布了击败欧洲围棋冠军樊麾（Fan Hui）的AlphaGo版本论文，结合深度神经网络和树搜索技术 | Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., Van Den Driessche, G., ... & Dieleman, S. (2016). Mastering the game of Go with deep neural networks and tree search. Nature, 529(7587), 484-489. |
2017 | 鉴于当前认知神经科学和人工智能工程所遇到的困难，华为2012实验室的研究人员提出了一种新的通用人工智能工程方法 | Li, Z. (2017). A Heuristic Search Algorithm Using the Stability of Learning Algorithms in Certain Scenarios as the Fitness Function: An Artificial General Intelligence Engineering Approach. arXiv:1712.03043. |
发展分析
瓶颈
尽管不同的搜索算法都有应用，但目前搜索算法技术还没有明确直接的商业化解决方案。
未来发展方向
随着深度学习的发展，与搜索算法进行整合是很有前景的（比如使用深度强化学习的 MCTS）。最近，整合了一些对抗搜索元素的生成对抗网络（GAN）大受欢迎。可以预见，未来将会有更多智能体出现在更多不同的应用领域。
Contributor: Yuanyuan Li, Mos Zhang
