A* 算法（启发式算法）

A*算法
这是我写的第一篇有关A*算法的文章，写得比较简洁，我决定再写一篇，补充一下对A*算法的理解。

A*算法的启发函数：

f(n) = g(n) + h(n)

A*算法把Dijkstra算法（靠近初始点的结点）和BFS算法（靠近目标点的结点）的信息块结合起来。
g(n)表示从初始结点到任意结点n的实际代价
h(n)表示从结点n到目标点的启发式评估代价

启发式函数

（1）h(n)=0，一种极端情况
如果h(n)=0，则只有g(n)起作用，此时A*演变成Dijkstra算法，这保证能找到最短路径，但效率不到，因为得不到启发。
（2）h(n)<实际代价
如果h(n)经常都比从n移动到目标的实际代价小（或者相等），则A*保证能找到一条最短路径。h(n)越小，A*扩展的结点越多，运行就越慢。
（3）h(n)=实际代价
如果h(n)精确地等于从n移动到目标的实际代价，则A*将会仅仅寻找最佳路径而不扩展别的任何结点，这会运行得非常快。尽管这不可能在所有情况下发生，你仍可以在一些特殊情况下让它们精确地相等（指让h(n)精确地等于实际代价）。只要提供完美的信息，A*就会运行得很完美。
（4）h(n)>实际代价
如果h(n)有时比从n移动到目标的实际代价大，则A*不能保证找到一条最短路径，但它运行得更快。
（5）h(n)>>实际代价（>>远大于），另一种极端情况
如果h(n)比g(n)大很多，则只有h(n)起作用，A*演变成BFS算法。

实现Open集和Close集的数据结构是什么？

数组？链表？
在Open集上主要有三种操作：查找优先级最高的结点&删除结点、查找相邻结点是否在集合中、插入新结点
在Close集上主要有两种操作：查找相邻结点是否在集合中、插入新节点
（1）未排序数组或链表
最简单的数据结构是未排序数组或链表。查找结点，花费O(N)；插入结点，花费O(1)；删除结点，花费O(N)
（2）排序数组
为了加快删除操作，可以对数组进行排序。查找结点，变成O(logN)，因为可以使用折半查找；插入结点，花费O(N)；查找和删除优先级最高的结点，花费O(1)
（3）排序链表
在排序数组中，插入操作很慢。如果使用链表则可以加速该操作。查找结点，花费O(N)；插入结点，花费O(1)，但查找插入位置，需要花费O(N)
（4）哈希表
使用哈希表，查找结点，花费O(1)；插入结点，花费O(1)；查找和删除优先级最高的结点，花费O(N)

https://blog.****.net/coutamg/article/details/53923717#!/_alzvzu0wsphb4nstr5bbro1or