发展历史
描述
19世纪，法国数学家查尔斯·皮埃尔·特雷莫(Charles Pierre Tremaux)对深度优先搜索Depth-first search (DFS)的一个版本进行了研究，认为这是一种解决迷宫的策略。BFS( Breadth-first search )和它在寻找图形的连接部分的应用是由Michael Burke和Konrad Zuse在1945年发明的.Edsger Dijkstra在1959年在ARMAC计算机上写出了Dijkstra算法，它来搜索最短路径的算法，只使用f(p)=cost(p)。
在1968年，人工智能研究员尼尔斯·尼尔森(Nils Nilsson)试图改进机器人Shakey所做的路径规划，这个机器人原型可以通过在一个包含障碍物的房间进行导航。这种寻路算法，Nilsson称之为A1，是当时最著名的Hans Berliner于1979算法的更快版本，用于在图中找到最短路径。Bertram Raphael建议对这个算法进行一些重要的改进，并调用了修改后的A2。然后Peter E. Hart引入了一个论证，建立了A2，只有微小的变化，才能成为寻找最短路径的最佳算法。此时A星算法使用的评价函数是f(p)=cost(p)+h(p).
B*(发音为“B星”)是一种最佳的图形搜索算法，它从给定的初始节点到任何目标节点(在一个或多个可能的目标中)找到最小成本路径。由Hans Berliner于1979年首次出版。
1985 Richard Korf Iterative deepening A* (IDA*)是一种图遍历和路径搜索算法，它可以在一个加权图中找到指定的起始节点和一组目标节点的任何成员之间的最短路径。它是迭代深化深度优先搜索的一个变体，它借用了一个启发函数来评估剩余的成本，以从a *搜索算法获得目标。由于它是深度优先的搜索算法，它的内存使用率低于A*，但与普通的迭代深化搜索不同，它专注于探索最有希望的节点，因此不会访问。与A*不同，IDA*不使用动态编程，因此经常会多次访问相同的节点。
Russell, S. (1992)SMA*Simplified Memory Bounded A*或简化内存有界A*是基于A*算法的最短路径算法。SMA的主要优点是它使用有界内存，而a *算法可能需要指数内存。SMA的所有其他特征都是从一个A*继承的。
下图是对经典的搜索算法进行总结：
深度优先法在空间上与探索的路径长度成线性关系，但如果存在，则不保证找到解决方案。宽度优先算法，成本最低第一，A*可能是在空间和时间是指数，但他们保证找到一个解决方案，如果存在，即使图是无限的。
Lowest-cost-first和A*搜索保证找到第一个解决方案的最低成本解决方案。
[来源：Artificial intelligence, URL : http://artint.info/html/ArtInt_58.html]
主要事件
年份 | 事件 | 相关论文/Reference |
1959 | Dijkstra, E. W.提出Dijkstra算法搜索最短路径 | Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische mathematik, 1(1), 269-271. |
1958 | Hart, P. E., Nilsson, N. J., & Raphael, B.提出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. |
1985 | Korf, R. E.对A星算法进行了优化减小了A星算法的消耗 | Korf, R. E. (1985). Depth-first iterative-deepening: An optimal admissible tree search. Artificial intelligence, 27(1), 97-109. |
发展分析
瓶颈
A*算法进行下一步将要走的节点的搜索的时候，每次都是选择F值最小的节点，因此找到的是最优路径。但是正因为如此A*算法每次都要扩展当前节点的全部后继节点，运用启发函数计算它们的F值，然后选择F值最小的节点作为下一步走的节点。在这个过程中，OPEN表需要保存大量的节点信息，不仅存储量大是一个问题，而且在查找F值最小的节点时，需要查询的节点也非常多，当然就非常耗时，这个问题就非常严重了。
未来发展方向
其实搜索算法一直是最优值和复杂度之间的权衡，也是大家一直研究的问题。目前也已经有很多成熟的搜索算法可以直接运用。搜索算法可以分为四类，大家可以根据不同的类型对它们进行研究：1.为了虚拟搜索空间的算法，比如 minimax algorithm, alpha–beta pruning；2.对于给定结构的子结构,如Dijkstra's algorithm, Kruskal's algorithm, the nearest neighbour algorithm, and Prim's algorithm；3.搜索功能的最大值；4.量子计算机, 比如 Grover's algorithm。
Contributor: Ruiying Cai