廢話?

? ? 用瀏覽器在網(wǎng)上搜索A*（A星）算法的實現(xiàn)，第一頁一半是廣告，該死的搜索引擎?。?！剩下的只有幾篇是內(nèi)容互不相同的，其他全是復(fù)制粘貼一氣呵成，半個字都不差?。?！而能看的那幾篇，又扯什么open表，close表，全篇很長，說不到重點上，看得頭疼！??！

????但是我還是自己寫出了A*算法，完成了作業(yè)。

????方法是什么？看書！

原理

????A*算法是一種搜索算法，可以高效地解決這樣的問題：從一個初始狀態(tài)到達(dá)一個目標(biāo)狀態(tài)。接下來就以迷宮尋路來說明A*算法的原理。

????要從入口到達(dá)出口，假設(shè)一次只能向上，下，左，右移動一格。

? ? （一）通常的做法是依次嘗試，比如廣度優(yōu)先搜索，就是一層一層的嘗試：

嘗試到了第6層才找到出口，顯然6層之前的所有格子都會被搜索到。

????（二）深度優(yōu)先搜索，假設(shè)是按左上右下的順序搜索，則它會一直往一個方向前進直到撞墻，然后后退：

看似比較快就找到出口，但是有點巧合。有趣的是，深度優(yōu)先是把一條路走到底的，所以，要是開始的方向是錯的，比如南轅北轍，那么它可能繞地球一圈后才找到出口！

????（三）A星搜索，A星的思想是：給每個可選的格子設(shè)置一個代價值，然后選擇代價最低的格子嘗試。代價 = 起點到那個格子的代價（已知）+ 那個格子到目標(biāo)格子的代價（估計）

怎么估計呢？那要用常識，比如直線距離，或者曼哈頓距離，只需要保證那個估計的代價要比實際代價小就行了。比如上圖入口到出口的直線距離是 根號18格，而根據(jù)規(guī)則，我們至少需要走6格才能到目的，那么這個估計就是好的。證明的話，大家去看書吧，我數(shù)學(xué)證明不太好。順便說一下，考察鄰近的格子稱為擴展。

????怎么估計代價呢？適當(dāng)減輕一下游戲規(guī)則。

????A星搜索過程如下：

?可以看到，A星基本是走直線方向的，而由于規(guī)則，所以實際的路徑是階梯型的。

總結(jié)
????A*的主要思想就是代價估計。

????估計函數(shù)可以根據(jù)適當(dāng)放寬規(guī)則來設(shè)計，具體情況具體分析。大家可以試試把上述用直線距離估計代價改為用曼哈頓距離估計代價，效果應(yīng)該會更好。曼哈頓距離就是水平直線距離加上垂直直線距離。

????A星算法考慮已經(jīng)訪問過了的格子也不會有問題，因為之前訪問時和現(xiàn)在訪問時，該格子的到達(dá)路徑變長了。也就是這樣：

這樣的話，我們用一個哈希表記錄已經(jīng)訪問過了的格子，以便可以不重復(fù)訪問，那么可以極大的加快搜索速度。我作業(yè)里親自體驗了這兩者的區(qū)別，允許重復(fù)的話，搜索次數(shù)1萬左右，不允許重復(fù)則只需要循環(huán)630次。

????需要注意的是：選擇代價最低的格子時，可選的格子并不是當(dāng)前格子的周圍格子，而是所有已經(jīng)擴展過但是不重復(fù)的格子（也就是經(jīng)過的格子的周圍格子）。因為，可能你走了這條路走到一定時候發(fā)現(xiàn)后面格子的代價比之前沒走的格子的代價還要大，那肯定是直接跳到那個格子啦，因為的因為，這只是模擬尋路，而不是真正的走路，所以可以跳躍?？磮D：

????我們位于起點時，估計A比B近，但是我們在A時，B比C近，所以，可選的應(yīng)該時所以已經(jīng)擴展的節(jié)點。

成功與失敗

???? ?要是有路徑可以到達(dá)出口的話，只要代價估計不超過實際代價（可采納），就肯定能找到出口。否則的話，就會搜索失敗，失敗的條件就是沒有可擴展的格子了（無路可走）。

????搜索到了出口格子算是成功了，但是并不能保證路徑最短。要保證路徑最短，就需要估計當(dāng)前情況下目的格子的代價，并使它的代價比其他可擴展格子的估計代價都小。

????所以真正的成功條件是：搜索到的目的格子代價是最低的。

????至于A星的代碼實現(xiàn)，還是另一篇再說吧，因為畫圖真的很花時間，望大家能點個贊。