算法解析

• 這是一個(gè)非常典型的搜索問(wèn)題。
• 人物的起點(diǎn)就是他當(dāng)下所在的位置，終點(diǎn)就是鼠標(biāo)點(diǎn)擊的位置。
• 我們需要在地圖中，找一條從起點(diǎn)到終點(diǎn)的路徑。
• 這條路徑要繞過(guò)地圖中所有障礙物，并且看起來(lái)要是一種非常聰明的走法。所謂“聰明”，籠統(tǒng)地解釋就是，走的路不能太繞。理論上講，最短路徑顯然是最聰明的走法，是這個(gè)問(wèn)題的最優(yōu)解。

實(shí)際上，像出行路線規(guī)劃、游戲?qū)ぢ罚@些真實(shí)軟件開(kāi)發(fā)中的問(wèn)題，一般情況下都不需要非得求最優(yōu)解（也就是最短路徑）。
在權(quán)衡路線規(guī)劃質(zhì)量和執(zhí)行效率的情況下，我們只需要尋求一個(gè)次優(yōu)解就足夠了。
如何快速找出一條接近于最短路線的次優(yōu)路線呢？
A* 算法：A* 算法是對(duì) Dijkstra 算法的優(yōu)化和改造。最優(yōu)出行路線規(guī)劃問(wèn)題中，如果圖非常大，Dijkstra 最短路徑算法的執(zhí)行耗時(shí)會(huì)很多
Dijkstra 算法有點(diǎn)兒類似 BFS 算法，它每次找到跟起點(diǎn)最近的頂點(diǎn)，往外擴(kuò)展。這種往外擴(kuò)展的思路，其實(shí)有些盲目。

可以避免“跑偏”嗎？
當(dāng)遍歷到某個(gè)頂點(diǎn)時(shí)，從起點(diǎn)到這個(gè)頂點(diǎn)的路徑長(zhǎng)度是確定的，記作 g(i)（i 表示頂點(diǎn)編號(hào)）

• 雖然從這個(gè)頂點(diǎn)到終點(diǎn)的路徑長(zhǎng)度是未知的，但可以用其他估計(jì)值來(lái)代替。
• 可以通過(guò)這個(gè)頂點(diǎn)跟終點(diǎn)之間的直線距離(歐幾里得距離)，近似估算這個(gè)頂點(diǎn)跟終點(diǎn)的路徑長(zhǎng)度（注意：路徑長(zhǎng)度跟直線距離是兩個(gè)概念）
• 把這個(gè)距離記作 h(i)（i 表示這個(gè)頂點(diǎn)的編號(hào)），專業(yè)的叫法是啟發(fā)函數(shù)（heuristic function）。
• 因?yàn)闅W幾里得距離的計(jì)算公式，會(huì)涉及比較耗時(shí)的開(kāi)根號(hào)計(jì)算，所以一般通過(guò)另外一個(gè)更加簡(jiǎn)單的距離計(jì)算公式，那就是曼哈頓距離（Manhattan distance）。
• 曼哈頓距離是兩點(diǎn)之間橫縱坐標(biāo)的距離之和。計(jì)算的過(guò)程只涉及加減法、符號(hào)位反轉(zhuǎn)，所以比歐幾里得距離更加高效。

原來(lái)只是單純地通過(guò)頂點(diǎn)與起點(diǎn)之間的路徑長(zhǎng)度 g(i)，來(lái)判斷誰(shuí)先出隊(duì)列，現(xiàn)在有了頂點(diǎn)到終點(diǎn)的路徑長(zhǎng)度估計(jì)值，通過(guò)兩者之和 f(i)=g(i)+h(i)，來(lái)判斷哪個(gè)頂點(diǎn)該最先出隊(duì)列。
綜合兩部分，就能有效避免“跑偏”。f(i) 的專業(yè)叫法是估價(jià)函數(shù)（evaluation function）

A* 算法就是對(duì) Dijkstra 算法的簡(jiǎn)單改造
在 A* 算法的代碼實(shí)現(xiàn)中，頂點(diǎn) Vertex 類的定義，跟 Dijkstra 算法中的定義，稍微有點(diǎn)兒區(qū)別，多了 x，y 坐標(biāo)，以及剛剛提到的 f(i) 值。圖 Graph 類的定義跟 Dijkstra 算法中的定義一樣。

A* 算法的代碼主要有 3 點(diǎn)區(qū)別：

• 優(yōu)先級(jí)隊(duì)列構(gòu)建的方式不同，
  A* 算法是根據(jù) f 值（ f(i)=g(i)+h(i)）來(lái)構(gòu)建優(yōu)先級(jí)隊(duì)列，
  Dijkstra 算法是根據(jù) dist 值（g(i)）來(lái)構(gòu)建優(yōu)先級(jí)隊(duì)列；

• A* 算法在更新頂點(diǎn) dist 值的時(shí)候，會(huì)同步更新 f 值；

• 循環(huán)結(jié)束的條件也不一樣。Dijkstra 算法是在終點(diǎn)出隊(duì)列的時(shí)候才結(jié)束，A* 算法是一旦遍歷到終點(diǎn)就結(jié)束。

A* 這是為什么不能找到最短路線呢？
要找出起點(diǎn) s 到終點(diǎn) t 的最短路徑，最簡(jiǎn)單的方法是，通過(guò)回溯窮舉所有從 s 到達(dá) t 的不同路徑，然后對(duì)比找出最短的那個(gè)。但回溯算法的執(zhí)行效率非常低，是指數(shù)級(jí)的。

Dijkstra 算法在此基礎(chǔ)之上，利用動(dòng)態(tài)規(guī)劃的思想，對(duì)回溯搜索進(jìn)行了剪枝，只保留起點(diǎn)到某個(gè)頂點(diǎn)的最短路徑，繼續(xù)往外擴(kuò)展搜索。動(dòng)態(tài)規(guī)劃相較于回溯搜索，只是換了一個(gè)實(shí)現(xiàn)思路，但它實(shí)際上也考察到了所有從起點(diǎn)到終點(diǎn)的路線，所以才能得到最優(yōu)解。

• A* 算法之所以不能像 Dijkstra 算法那樣，找到最短路徑，主要原因是兩者的 while 循環(huán)結(jié)束條件不一樣
• Dijkstra 算法是在終點(diǎn)出隊(duì)列的時(shí)候才結(jié)束，A* 算法是一旦遍歷到終點(diǎn)就結(jié)束
• 對(duì)于 Dijkstra 算法，當(dāng)終點(diǎn)出隊(duì)列時(shí)，終點(diǎn)的 dist 值是優(yōu)先級(jí)隊(duì)列中所有頂點(diǎn)的最小值，即便再運(yùn)行下去，終點(diǎn)的 dist 值也不會(huì)再被更新了。
• 對(duì)于 A* 算法，一旦遍歷到終點(diǎn)，我們就結(jié)束 while 循環(huán)，這個(gè)時(shí)候，終點(diǎn)的 dist 值未必是最小值。
• A* 算法利用貪心算法的思路，每次都找 f 值最小的頂點(diǎn)出隊(duì)列，一旦搜索到終點(diǎn)就不在繼續(xù)考察其他頂點(diǎn)和路線了。