人工智能（A*算法）一、A*算法概述A*算法是到目前为止最快的一种计算最短路径的算法，但它一种'较优'算法，即它一般只能找到较优解，而非最优解，但由于其高效性，使其在实时系统、人工智能等方面应用极其广泛
A*算法结合了启发式方法（这种方法通过充分利用图给出的信息来动态地作出决定而使搜索次数大大降低）和形式化方法（这种方法不利用图给出的信息，而仅通过数学的形式分析，如Dijkstra算法）
它通过一个估价函数（HeuristicFunction）f（h）来估计图中的当前点p到终点的距离（带权值），并由此决定它的搜索方向，当这条路径失败时，它会尝试其它路径
因而我们可以发现，A*算法成功与否的关键在于估价函数的正确选择，从理论上说，一个完全正确的估价函数是可以非常迅速地得到问题的正确解答，但一般完全正确的估价函数是得不到的，因而A*算法不能保证它每次都得到正确解答
一个不理想的估价函数可能会使它工作得很慢，甚至会给出错误的解答
为了提高解答的正确性，我们可以适当地降低估价函数的值，从而使之进行更多的搜索，但这是以降低它的速度为代价的，因而我们可以根据实际对解答的速度和正确性的要求而设计出不同的方案，使之更具弹性
二、A*算法分析众所周知，对图的表示可以采用数组或链表，而且这些表示法也各也优缺点，数组可以方便地实现对其中某个元素的存取，但插入和删除操作却很困难，而链表则利于插入和删除，但对某个特定元素的定位却需借助于搜索
而A*算法则需要快速插入和删除所求得的最优值以及可以对当前结点以下结点的操作，因而数组或链表都显得太通用了，用来实现A*算法会使速度有所降低
要实现这些，可以通过二分树、跳转表等数据结构来实现，我采用的是简单而高效的带优先权的堆栈，经实验表明，一个1000个结点的图，插入而且移动一个排序的链表平均需500次比较和2次移动；未排序的链表平均需1
