一. 概述
A算法是游戲中路徑搜索的常見算法扁凛。Dijkstra是最短路徑的經(jīng)典算法，A算法的思路基本上和Dijkstra算法一致谬运，在Dijkstra算法的基礎(chǔ)上增加了啟發(fā)函數(shù)，也就是：
f(n) = g(n) + h(n)
其中爬骤，n是路徑上某一點骡湖，g(n)是從出發(fā)點到該點的cost贱纠，h(n)是關(guān)于該點的啟發(fā)函數(shù)，通常是對從該點到目標花費的一個估計响蕴，例如到目標的直線距離或者曼哈頓距離并巍。 A算法每次選擇f(n)最小的點，然后更新所有g(shù)(n)换途。
如果你明白Dijkstra算法懊渡，那么在這里h(n) = 0 的話，A算法就和Dijkstra算法一樣了军拟。
本文不詳細講解A算法剃执，需要詳細了解A算法的具體過程的，參見以下兩篇文章：
二. A*算法的優(yōu)化思路
A*算法優(yōu)化的關(guān)鍵在于h(n)的選擇懈息。 一個啟發(fā)函數(shù)h(n)被稱為admissible的肾档，是指h(n)的估計，不會超過節(jié)點N到目標的實際花費辫继。
如果h(x)滿足以下條件怒见，h(x)被稱為單調(diào)的(monotone, or consistent)。 對于任意一條邊(x,y),
h(x) <= d(x,y) + h(y)
其中d(x,y)是（x,y）的長度
如果滿足這個條件姑宽，就意味著沒有任何節(jié)點需要被處理多次遣耍，也就是說，在Dijkstra算法中炮车，新加入一個節(jié)點會導(dǎo)致已添加節(jié)點中cost降低的情況不會存在舵变，也就不需要去更新已添加節(jié)點(稱為close set)。
如果一個啟發(fā)函數(shù)是單調(diào)的瘦穆，那么該啟發(fā)函數(shù)一定是admissible的纪隙。如果該啟發(fā)函數(shù)是admissible的，那么可以證明A*在同類算法中搜尋到最短的路徑扛或。
問題出在這里：如果我們更在意的是搜索的時間空間花費绵咱，而不是最優(yōu)結(jié)果，那么A*算法就有優(yōu)化空間熙兔。所以我們放松要求悲伶，修改我們的啟發(fā)函數(shù)，使得我們搜尋到的路徑不會比最佳路徑差太多黔姜，就是優(yōu)化算法拢切，稱為ε-admissible算法。
有多種ε-admissible算法秆吵，在此只舉例最簡單直接的一種： 加權(quán)A*(靜態(tài)加權(quán))算法淮椰。
假如ha(n)是一個admissible的啟發(fā)函數(shù)，我們選取新的啟發(fā)函數(shù)hw(n) = ε ha(n)，其中ε>1 作為啟發(fā)函數(shù)主穗。就可以在某種程度上進行優(yōu)化泻拦。 下圖1是使用ha(n)作為啟發(fā)式算法，下圖2是使用hw(n)作為啟發(fā)式算法忽媒，其中ε取5.
圖1：ha(x)作為啟發(fā)算法
圖2：hn(x)作為啟發(fā)算法
可以看出争拐，ha(n)可以找到最小路徑，但是多了許多無用的搜索晦雨；而hw(n)找到的不是最優(yōu)路徑架曹，但是減少了大量無用搜索。
其他的優(yōu)化算法思路類似都是在于啟發(fā)函數(shù)的選擇闹瞧。詳見參考文獻绑雄。
參考文獻：
https://en.wikipedia.org/wiki/A*_search_algorithm#Admissibility_and_optimality https://en.wikipedia.org/wiki/Consistent_heuristic
