A＊ 算法及优化思路

在介绍A星算法之前，先聊聊Dijkstra算法与最佳优先算法（BFS）

Dijkstra算法

Dijkstra算法的思路是从起点开始，向外扩散搜索，从树结构上观察就是广度优先搜索，把每一层的节点都尝试搜索一下，直到搜索到目标节点，则搜索完毕，认为找到了最短路径，出于广度优先的搜索方式，意味着搜索过程中效率并非是最高的，因为整个搜索过程，很多节点都是无意义的搜索。

下图是Dijkstra算法执行的示意图

最佳优先算法（BFS）

最佳优先算法（BFS）是带有启发式的，它评估的是任意节点到目标节点所需要的代价，这与选择离起始节点代价最小不同的是，它选择的是离目标点代价最小，所以这不能保证搜索的路径是最短的，但是却可以保证搜索效率是最快的，当然找到的路径可能不是期望的。因为它未把从起始点的代价算进去，进行的是贪心算法的搜索，所求出来的路径不是最佳路径。

下图是BFS算法搜索的示意图

BFS算法的搜索得到非最优解

下图得到的解是非最优解，搜索过程中，直接搜索到死胡同中去了。

下图是BFS搜索示意图，虽然效率不高，但是确实找到了最优解。

A星算法

启发式搜索就是在状态空间中的搜索，首先对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径，提高了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。
启发中的估价是用估价函数表示的，如：f(n)=g(n) + h(n)
其中f(n) 是节点n的估价函数，g(n)是在状态空间中从初始节点到n节点的实际代价，h(n)是从n到目标节点最佳路径的估计代价。在这里主要是h(n)体现了搜索的启发信息，因为g(n)是已知的。如果说详细点，g(n)代表了搜索的广度的优先趋势。但是当h(n) >> g(n)时，可以省略g(n)，而提高效率。

考虑到Dijkstra算法与BFS算法都有缺点，因此结合两个算法的优点，得到的就是A星算法。

表示方程式如下

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

g(n)表示 从起始节点到 n 节点所需要的代价。

h(n)表示 从n节点到目标节点所需要的代价。

f(n)点的价值全取决于 g(n) 与 h(n)

h(n) 对A星算法的影响

• h(n) 等于0，那么意味着 f(n)=g(n) , A星算法变成了Dijkstra算法
• 如果h(n) 小于 实际 cost(n) 代价，A星算法可以找到最短路径，但是搜索效率略低，h(n)越小，意味着搜索节点越多，效率上越低，但是精度上越准确，越接近最优解，因为趋近于Dijkstra算法。（cost(n) 表示实际从n节点到目标节点的代价 ）
• h(n) 等于 cost(n)，是A星最优状态。
• h(n) 远远大于 g(n) ,那么 f(n)的值就主要取决于 h(n),A星就演变成了BFS算法。

A星算法的优化

• 动态衡量启发式：f(n)=g(n) + w(n) * h(n) , 其中 w(n) >=1 。与传统的A星不同的是，原本的h(n) ，变成了 w(n) * h(n) , w(n) 可以影响评估值。在搜索过程中，我们可以通过改变w(n) 来影响搜索过程如上面提到的 h(n) 对A星算法的影响。可以推理出，w(n) 越大，越趋近于BFS算法，而 w(n) 相对越小，则相对于趋近于Dijkstra算法。

• 简化搜索空间：传统的A星算法是效率并不高的算法，常常会因为搜索空间的太大，而影响搜索效率。
• 分级寻径：把搜索过程拆分开了，如查找空间A中的p1点到空间B中的p2点最短路径，那么可以分为两部分，先查找p1点到空间B的路径，再搜索到p2的路径，整个过程分为了两步，甚至是将计算一次的消耗，拆分成了两次，计算压力也变小了

• 优化Open表：传统的Open表，因为语言的不同，可能选择的是：Array、List、Queue等等结构来存储。而在A星搜索过程中，随着搜索深度越深，意味着可能要查找的节点越多，后期Open表中存储的节点越点。在数据结构的选择上，我们希望所选择的节点带有“可参照性”，而不是单单的直接从Open表中取。如果Open表在放入数据之前，我们就让它按照一定顺序，那么我们从Open表中取数据时，这些数据就是具备顺序的，是有“可参照性的”。可以选择优先队列的方式。