启发式搜索算法引论------A*算法理论与实践 - 生活的智慧 - CSDNBlog

jiangtao收录，使用标签：算法, A*算法, 启发式搜索，时间：2006-10-18 17:37:45 | 相关网摘，我也收藏

P. E. Hart , N. J. Nilsson 和B. Raphael共同发表了一篇在启发式搜索方面有深远影响力的论文：

“P. E. Hart, N. J. Nilsson, and B. Raphael. A formal basis for the heuristic determination of minimum cost paths in graphs. IEEE Trans. Syst. Sci. and Cybernetics, SSC-4(2):100-107, 1968”。从此，一种精巧、高效的算法------A*算法横空出世了，并在相关领域得到了广泛的应用。
A*算法的思想来源并不是什么高深莫测的东西，事实上，它与我们所熟悉的另外两种搜索策略：DFS（深度优先Deep First Search）和 BFS(广度优先Breadth First Search)有着自然而紧密的联系。

首先要提一下搜索树的概念，一个可以搜索出某个可行解的问题，如“农夫、白菜、羊、狼”和“八皇后”等，虽然从表面上看上去和“树”这种结构无关，但是整个搜索过程中的可能试探点所行成的搜索空间总可以对应到一颗搜索树上去。所以，将各类形式上不同的搜索问题抽象并统一成为搜索树的形式，为算法的设计与分析带来巨大的方便。

http://blog.csdn.net/EmilMatthew/archive/2006/10/17/1338808.aspx