http://www.cnblogs.com/technology/archive/2011/05/26/2058842.html

http://www.itdecent.cn/p/22dfcca70064

http://blog.csdn.net/yiyikela/article/details/46134339

A*算法 ?

關鍵點 ?開啟列表【有序列表】 ? 關閉列表。 ?開啟列表是下一個可以訪問的點，關閉列表是不會再被訪問的點

路徑消耗 ?: 一張地圖類似于一個網（加權圖），總路徑消耗 ?F = G + H ? ? ?F:總路徑 ? G:當前位置移動到指定位置的消耗 ? ?H: 從指定位置到終點的消耗

算法思路 ?：圍繞著 ?F = G+H ? 和 開啟列表 關閉列表展開。

1.取F值最小的，加入開啟列表，在遍歷開啟列表中的點，把這個點A的所有周圍的點，加入到開啟列表。

2.如果這個點A周圍的點B已經在開啟列表中，計算從開始點經過A 到達B 的G值是不是變小了，變小了就說明從A走，會更近。就把B的父指定為A。并且更新B點的G值和F值。 如果沒有更近，就不指定。

3.如果這個點A周圍的點B不在開啟列表中，就把B的父指定為A。

4.經過步驟2和步驟3，最終B會得到一個到起始點最小的G值。因為每次循環(huán)，都會替換成最近父給B點。當循環(huán)結束，B點的父就是最近的路徑。 【注意】 每次完成一次對B點的循環(huán)，就會對開放列表排序一次，下次循環(huán)只取第一個，F(xiàn)最小的點

5.循環(huán)遍歷F值相對低的點，重復2,3步驟，當開啟列表中有結束點，就停止循環(huán)。 從結束點開始往前找父。最終就得到了最短路徑。

拓展點： ?G值得計算策略 以及H值得計算策略

H值計算 ? Abs 絕對值

G的算法 ?Sqrt 平方根

缺點： 啟發(fā)式的搜索法方法，如果地圖格子多，搜索會變慢，成指數級增長。 ?優(yōu)化策略，用二叉堆優(yōu)化A*。?

耗時的部分主要是每次重新去點之前，要對開啟列表做排序。 二叉堆優(yōu)化其實就是對開放列表的數據結構優(yōu)化，用更優(yōu)的排序方法，其實就是堆排序，快速排序這些基礎算法

?二叉堆優(yōu)化A*算法

http://blog.csdn.net/ymiku/article/details/45957107

二叉堆： 完全二叉樹+堆（最大堆或者最小堆） ? 二叉堆的特性： ?根的位置*2 和根的位置*2+1 是這個根的子。 ? ?子的位置/2 是他的根。

二叉堆并不是完全的順序排列，但是總是滿足根節(jié)點是最大或者最小，這就滿足了我們的需求

維護二叉堆

為了往堆里添加元素，我們把它放在數組的末尾。然后和它在當前位置/2?處的父節(jié)點比較，分數部分被圓整。如果新元素的F值更低，

我們就交換這兩個元素。然后我們比較這個元素和它的新父節(jié)點，在（當前位置）/2，小數部分圓整，的地方。如果它的F值更低，

我們再次交換。我們重復這個過程直到這個元素不再比它的父節(jié)點低，或者這個元素已經到達頂端，處于數組的位置1。

添加元素 ，新元素放到最后，然后不停的跟新元素位置/2的做比較，小了就交換。

元素刪除，刪除第一個最小的元素，然后把最后一個元素放到第一個，然后不停的跟*2 和*2+1 做比較。 如果大于，就跟較小的交換，直到*2 和*2+1 沒有元素位置。表明到底了