：A*算法的理解与应用算法

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

A*算法的启发式函数：f(n) = g(n) + h(n)

A*算法结合了算法的信息块（靠近初始点的节点）和BFS算法（靠近目标点的节点）。

g(n)表示从初始节点到任意节点n的实际成本

h(n)表示从节点n到目标点的启发式评估成本

启发式函数

(1)h(n)=0，极端情况

如果 h(n)=0，则只有 g(n) 有效。 这时候A*就演化成了一种算法，保证能找到最短路径，但是效率不高，因为没有灵感。

(2) h(n) 实际成本

如果h(n)有时大于从n移动到目标的实际成本，A*不能保证找到最短路径，但它运行得更快。

(5) h(n) >> 实际成本（>> 远大于），另一个极端情况

如果 h(n) 远大于 g(n)，则只有 h(n) 起作用，A* 演变成 BFS 算法。

实现开集和闭集的数据结构是什么？

大批？ 链接列表？

Open集合的操作主要有3个：查找优先级最高的节点并删除该节点、查找相邻节点是否在集合中、插入新节点。

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)。

#!/