看完以下概述，即可明白何為A星算法。
關(guān)于什么是A星算法，上網(wǎng)一查便知。在此只簡(jiǎn)要記錄一些有關(guān)A星算法的要點(diǎn)
一：f、g、h值
f值：即：算法的估價(jià)值。是指對(duì)某一點(diǎn)的估價(jià)值。例如：要想從起點(diǎn) S 到達(dá)終點(diǎn) D，則中間可能會(huì)經(jīng)過(guò)n個(gè)點(diǎn)，假如其中經(jīng)過(guò)點(diǎn)：X ，則f(X)，就是對(duì)點(diǎn)x的計(jì)算所得的估價(jià)值。當(dāng)然，對(duì)于估價(jià)值，是越小越好。
g值: 即：從起點(diǎn) S 到達(dá)點(diǎn) X 實(shí)際所花的代價(jià)值。例如：以格子數(shù)為計(jì)量單位。則g值表示，從S到X所經(jīng)過(guò)的格子數(shù)，即為實(shí)際所花費(fèi)的代價(jià)值
h值: 即：從點(diǎn) X 到達(dá)終點(diǎn) D 可能要花費(fèi)的值。也就是所謂的估計(jì)值，猜測(cè)值。這個(gè)值根據(jù)不同的應(yīng)用，實(shí)現(xiàn)策略，將會(huì)有不同的結(jié)果。當(dāng)然值越小是越好的。理由是：f(X) = g(X) + h(X) 。因?yàn)間(X)值是固定的，已知的。所以要想f(X)值越小，則只能h(X)的值越小。
二：節(jié)點(diǎn)與地圖位置點(diǎn)
地圖位置點(diǎn)不言而喻，是指地圖上的某個(gè)具體點(diǎn)，因此，只要地圖的劃分方法確定，則地圖位置點(diǎn)必然確定。
節(jié)點(diǎn)是A星算法中所需要依賴(lài)的數(shù)據(jù)信息存儲(chǔ)相關(guān)的點(diǎn)。與地圖位置點(diǎn)不同。節(jié)點(diǎn)中所存儲(chǔ)的數(shù)據(jù)信息是靈活多變的。同時(shí)，同一個(gè)節(jié)點(diǎn)，可能對(duì)應(yīng)于不同的地圖位置點(diǎn)。一般情況下，節(jié)點(diǎn)中會(huì)存儲(chǔ)地圖位置點(diǎn)信息、當(dāng)前節(jié)點(diǎn)的f、g、h值等等。
!!!note: 在A星算法中，節(jié)點(diǎn)只分為兩類(lèi)。一類(lèi)是：待考察的節(jié)點(diǎn)。一類(lèi)是：已考察的節(jié)點(diǎn)。
已考察節(jié)點(diǎn)是指：當(dāng)所有與節(jié)點(diǎn)X相關(guān)連的節(jié)點(diǎn)的f、g、h值均已被賦值并且這些節(jié)點(diǎn)均已被添加到open表中時(shí)，則節(jié)點(diǎn)X就是已經(jīng)被考察過(guò)了。
三：open表與closed表
open表中所存儲(chǔ)的元素，全部都是需要進(jìn)一步進(jìn)行考察的節(jié)點(diǎn)。
closed表中所存儲(chǔ)的元素，全部都是已經(jīng)被考察過(guò)了的節(jié)點(diǎn)。
四：A星算法的實(shí)現(xiàn)步驟
1) 令 P = 起始節(jié)點(diǎn)
2) 把 f, g, h 值賦給 P
3) 將 P 添加到 Open 表中。此時(shí) P 是 Open 表中唯一的節(jié)點(diǎn)。
4) 令 B = Open 表中的最佳節(jié)點(diǎn)。(提示：所謂最佳節(jié)點(diǎn)是指：該節(jié)點(diǎn)的 f 值最小)
(1) 如果 B 是目標(biāo)節(jié)點(diǎn)，則退出。此時(shí)已找到一條路徑。
(2) 如果 Open 表為空，則退出。此時(shí)沒(méi)有找到路徑。
5) 令 C 等于一個(gè)與 B 相連的有效節(jié)點(diǎn)。
(1) 把 f, g, h 的值賦給 C。
(2) 檢查 C 是在 Open 表里，還是在Closed表里。
2.1: 若在 Closed 表里，則檢查新路徑是否比原先更好，若是則采用新路徑。
2.2: 否則把 C 添加到 Open 表里.
(3) 對(duì)所有 B 的子孫節(jié)點(diǎn)重復(fù)步驟 5).
6) 重復(fù)步驟 4).