基本函數(shù)F(n)=G(n) + H(n);

其中G(n)是從起始點(diǎn)到當(dāng)前點(diǎn)的距離，H(n)是從當(dāng)前點(diǎn)到目標(biāo)點(diǎn)的估計(jì)距離。

例如對(duì)于一個(gè)網(wǎng)格狀的路網(wǎng)可以橫走和豎走，H(n)就是標(biāo)準(zhǔn)Manhattan距離：

h(n) = D * (abs(n.x-goal.x) + abs(n.y-goal.y))

D是走一步的代價(jià)。

對(duì)于不同的情況H(n)的選取很關(guān)鍵，H越大運(yùn)算時(shí)間越短但得到最優(yōu)解的可能性越低

H越小運(yùn)算時(shí)間越長(zhǎng)得到最優(yōu)解的可能性越高。當(dāng)H為0時(shí)就是dijkstra算法。

1)         創(chuàng)建OPEN和CLOSE表。其中OPEN為待評(píng)估的點(diǎn)，CLOSE為已經(jīng)運(yùn)算評(píng)估過(guò)的點(diǎn)。其中OPEN使用二叉堆便于排序。

2)         初始化將起始點(diǎn)計(jì)算F(n)并加入到OPEN表。

3)         取當(dāng)前OPEN中的最小F(n)點(diǎn)為當(dāng)前點(diǎn)，將他從OPEN表中刪除,加入到CLOSE表。

4)         計(jì)算當(dāng)前點(diǎn)的所有附近點(diǎn)(即一步能達(dá)到的點(diǎn))

4.1   對(duì)于附近點(diǎn)計(jì)算cost=當(dāng)前點(diǎn)的G(n)+當(dāng)前點(diǎn)到附近點(diǎn)的開(kāi)銷。

4.2   如果附近點(diǎn)已經(jīng)在OPEN中則比較附近點(diǎn)的G(n)和cost，如果cost小于附近點(diǎn)的G(n)則更新OPEN表中的附近點(diǎn)的G(n)為cost和F(n)，并把它的父節(jié)點(diǎn)設(shè)為當(dāng)前點(diǎn)。反之不做操作。

4.3   如果附近點(diǎn)在CLOSE表中則比較附近點(diǎn)的G(n)和cost，如果cost小于附近點(diǎn)的G(n)，則將附近點(diǎn)從CLOSE表中刪除并更新該附近點(diǎn)的G(n)和F(n)并加入到OPEN表，并把它的父節(jié)點(diǎn)設(shè)為當(dāng)前點(diǎn)。反之不操作。

4.4   如果附近點(diǎn)既不在OPEN表也不在CLOSE表，則計(jì)算附近點(diǎn)的G(n),H(n)和F(n)并加入到OPEN表，并把它的父節(jié)點(diǎn)設(shè)為當(dāng)前點(diǎn)。

5)         從3步驟開(kāi)始重新計(jì)算直到當(dāng)前點(diǎn)為目標(biāo)點(diǎn)。

6)         從目標(biāo)點(diǎn)開(kāi)始按父節(jié)點(diǎn)給出到起始點(diǎn)的最短路徑。

其中的關(guān)鍵是對(duì)OPEN表、CLOSE表的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)。由于OPEN表中存在排序和查找的基本操作，CLOSE表也存在查找的基本操作。

當(dāng)數(shù)據(jù)量大時(shí)，數(shù)據(jù)結(jié)構(gòu)的優(yōu)勢(shì)體現(xiàn)的非常明顯。OPEN表一般都使用二叉堆的形式，CLOSE表則使用簡(jiǎn)單的數(shù)組即可。

實(shí)際測(cè)試產(chǎn)生一個(gè)1366*768 像素通路點(diǎn)和障礙點(diǎn)為1:2的隨機(jī)網(wǎng)格地圖從坐標(biāo)(100, 100)到(1000, 300)的算路時(shí)間(h取Manhattan距離)在5400雙核cpu，2g內(nèi)存下大概為120秒左右。

遺傳算法

網(wǎng)上建模實(shí)現(xiàn)的方法很多
 第一種 針對(duì)網(wǎng)格狀地圖的遺傳算法

1.       將地圖抽象成網(wǎng)格，對(duì)于不同地形賦不同值，例如高速路標(biāo)的值可以比輔路低3到4倍。

2.       旋轉(zhuǎn)地圖使起點(diǎn)和終點(diǎn)調(diào)節(jié)成位于同一個(gè)縱坐標(biāo)。

3.       將起點(diǎn)到終點(diǎn)將的像素點(diǎn)劃分成幾個(gè)塊。

4.       對(duì)于每個(gè)塊產(chǎn)生隨機(jī)的基因(即變異的過(guò)程)，保證每個(gè)塊的當(dāng)前基因位置與前一個(gè)基因位置相差小于2個(gè)像素點(diǎn)(即2個(gè)基因連通)。如圖紅藍(lán)為2個(gè)獨(dú)立的染色體：

5.       計(jì)算所有染色體的適應(yīng)度。選擇最小的2個(gè)染色體作為雙親。

6.       對(duì)雙親進(jìn)行隨機(jī)交配產(chǎn)生子代。當(dāng)產(chǎn)生的子代形成一條通路時(shí)停止。否則返回到第五步。

他人的運(yùn)行結(jié)果：

以上算法存在的最大缺陷是當(dāng)存在的路徑垂直于起點(diǎn)和終點(diǎn)的連接線時(shí)，無(wú)法產(chǎn)生適合的基因，因?yàn)樵撍惴óa(chǎn)生的基因?qū)τ诿恳粋€(gè)縱坐標(biāo)是唯一的。

l第二種 針對(duì)路網(wǎng)結(jié)構(gòu)的遺傳算法

大致思想如下：

1． 針對(duì)起點(diǎn)和終點(diǎn)先產(chǎn)生n條連通路徑作為原始的種群。

2． 計(jì)算每條路徑的適應(yīng)度(一般都以路徑的長(zhǎng)度為基礎(chǔ)作為適應(yīng)度)。

3． 進(jìn)行隨機(jī)交配(前提是雙親必須有交叉點(diǎn))。這個(gè)變化最大隨機(jī)的好壞決定了整個(gè)算法的優(yōu)劣。

4． 淘汰掉適應(yīng)度最低的m條道路。

5． 重復(fù)2-4步驟。設(shè)定結(jié)束條件為連續(xù)k次遺傳的最優(yōu)解都是同一個(gè)或者設(shè)定遺傳的次數(shù)(到例如50次自動(dòng)結(jié)束)。

6． 將適應(yīng)度最高的作為最終解。

以上算法的難點(diǎn)在于原始種群的產(chǎn)生有一定難度，取小了無(wú)法滿足交叉條件，取大了耗費(fèi)運(yùn)算時(shí)間且復(fù)雜度提高