A*（A-Star）算法也是一種在圖中求解最短路徑問(wèn)題的算法。
由狄克斯特拉算法發(fā)展而來(lái)稼病，狄克斯特拉算法會(huì)從離起點(diǎn)近的頂點(diǎn)開(kāi)始选侨，按順序求出起點(diǎn)到各個(gè)頂點(diǎn)的最短路徑。
也就是說(shuō)然走，一些離終點(diǎn)較遠(yuǎn)的頂點(diǎn)的最短路徑也會(huì)被計(jì)算出來(lái)援制，但是這部分其實(shí)是無(wú)用的。
與迪克斯特拉算法不同的是芍瑞，A*就會(huì)預(yù)先估算一個(gè)值晨仑，并利用這個(gè)值省去一些無(wú)用的計(jì)算。
圖示頂點(diǎn)從A-Z拆檬，備注：A2,A3,A4也是頂點(diǎn)洪己，只是字母不夠用了，用數(shù)字區(qū)分竟贯。
設(shè)S為起點(diǎn)码泛，G為終點(diǎn)，嘗試用狄克斯特拉算法來(lái)求該圖中最短路徑澄耍。
在圖中每個(gè)方框?qū)儆谝粋€(gè)頂點(diǎn)噪珊，假設(shè)每個(gè)相鄰兩個(gè)頂點(diǎn)的距離（權(quán)重）都為1晌缘。
以這個(gè)設(shè)定為前提，用狄克斯特拉算法來(lái)求最短路徑：
用狄克斯特拉算法求最短路徑的結(jié)果如下圖所示：
從M搜索到A的最小權(quán)重路徑權(quán)重是8痢站，最短路徑的頂點(diǎn)順序是：
M - L - K - J - H - Z - C - B - A
狄克斯特拉算法只根據(jù)起點(diǎn)到候補(bǔ)頂點(diǎn)的距離來(lái)決定下一個(gè)頂點(diǎn)磷箕。因此無(wú)法發(fā)現(xiàn)M-N -O 方向和H - I - G方向的兩條路徑離終點(diǎn)越來(lái)越遠(yuǎn)，同樣會(huì)繼續(xù)搜索阵难。
而A*算法不僅會(huì)考慮從起點(diǎn)到候補(bǔ)頂點(diǎn)的距離岳枷，還會(huì)考慮從點(diǎn)錢(qián)所在頂點(diǎn)到終點(diǎn)的估算距離。這個(gè)估算距離可以自由設(shè)定呜叫。這里用頂點(diǎn)到終點(diǎn)的直線(xiàn)距離四設(shè)五入后的值空繁。
接下來(lái)就用A*算法來(lái)求解：
現(xiàn)將起點(diǎn)M設(shè)置為已經(jīng)搜索過(guò)的狀態(tài)，分別計(jì)算起點(diǎn)周?chē)總€(gè)頂點(diǎn)的權(quán)重朱庆。
頂點(diǎn)N到終點(diǎn)的估算距離 = √（16 + 25）= 6.4 四舍五入 = 6
頂點(diǎn)N的權(quán)重 = 從起點(diǎn)M到頂點(diǎn)N的頂點(diǎn)距離 加上 頂點(diǎn)N到終點(diǎn)的距離估算距離 = 1 + 6 = 7
頂點(diǎn)Q到終點(diǎn)的估算距離 = √ （9 + 16）= 5
頂點(diǎn)Q的權(quán)重 = 從起點(diǎn)M到頂點(diǎn)Q的距離 加上頂點(diǎn)Q到終點(diǎn)的估算距離 = 1 + 5 = 6
頂點(diǎn)L到終點(diǎn)的估算距離= √ （ 16 + 9 ） = 5
頂點(diǎn)L的權(quán)重 = 從起點(diǎn)M到頂點(diǎn)L的距離 加上 頂點(diǎn)L到終點(diǎn)的估算距離 = 1 + 5 = 6
接下來(lái)選擇權(quán)重最小的頂點(diǎn)來(lái)繼續(xù)搜索盛泡，選擇Q或者L都可以，這里選擇Q娱颊，
選擇Q來(lái)搜索時(shí)候傲诵，這里會(huì)求解R的權(quán)重
頂點(diǎn)R的權(quán)重 = 從起點(diǎn)M到頂點(diǎn)R的距離 加上 頂點(diǎn)R 到終點(diǎn)的估算距離= 2 + 4 = 6
接下來(lái)可以選擇頂點(diǎn)R或者頂點(diǎn)L繼續(xù)搜索，這里選擇頂點(diǎn)R,
選擇頂點(diǎn)R搜索時(shí)候箱硕，這里會(huì)求解S的權(quán)重拴竹，
頂點(diǎn)S的權(quán)重 = 從起點(diǎn)M到頂點(diǎn)S的距離 加上 頂點(diǎn)S到終點(diǎn)的估算距離 = 3 + 4 = 7
接下來(lái)選擇權(quán)重最小的頂點(diǎn)L來(lái)進(jìn)行搜索，求解K的權(quán)重
頂點(diǎn)K的權(quán)重 = 2 + 4 = 6
接下來(lái)選擇權(quán)重最小的頂點(diǎn)K來(lái)進(jìn)行搜索剧罩，求解J的權(quán)重
頂點(diǎn)J的權(quán)重= 3 + 4 = 7
接下來(lái)可以選的起點(diǎn)是N栓拜，S, J，權(quán)重都為7惠昔，這里隨機(jī)選擇N來(lái)搜索菱属，求解頂點(diǎn)O的權(quán)重
頂點(diǎn)O的權(quán)重 = 2 + 7 = 9
接下來(lái)可選擇的起點(diǎn)是S和J，權(quán)重都為7舰罚，這里隨機(jī)選擇S來(lái)搜索纽门，求解T的權(quán)重
頂點(diǎn)T的權(quán)重 = 4 + 4 = 8
接下來(lái)選擇J來(lái)搜索，求解H的權(quán)重
頂點(diǎn)H的權(quán)重 = 4 + 4 = 8
接下來(lái)可選擇的頂點(diǎn)是T 和 H 营罢，這里隨機(jī)選擇T
...
....
搜索完畢結(jié)果如下圖：
求得最終的M - A的最短路徑權(quán)重為8赏陵，順序?yàn)镸 - L - K - J - H - Z - C - B - A 。
在A*算法中顯然少搜索了兩個(gè)遠(yuǎn)離終點(diǎn)方向的路線(xiàn)M-N-O 和J - H - I饲漾。效率比狄克斯特拉算法高蝙搔。
但是如果這個(gè)頂點(diǎn)到終點(diǎn)的估算距離無(wú)法大概估算，那么就不能用A*算法考传。
