開篇

這篇文章介紹找最短路徑的一種算法，它的字我比較喜歡:啟發(fā)式搜索。

標(biāo)題上寫的是翻譯，只是覺得原文講解的思路很清晰。這篇文章整體構(gòu)思和原文相差不多，只是有些地方有小的改動(dòng)，

我想的是用更容易理解的方式、更簡潔的把A*算法的思想呈現(xiàn)出來。

文章中出現(xiàn)的詞openlist，closelist我覺得用原文會(huì)更好故沒有翻譯，在文中會(huì)有解釋。

原文地址http://www.gamedev.net/page/resources/_/technical/artificial-intelligence/a-pathfinding-for-beginners-r2003

各位也可以直接參考原文。

網(wǎng)上關(guān)于A*算法的文章還有很多，只是那些都需要有一定的基礎(chǔ)，對(duì)于入門的好文章不多，而這篇文章就是為初學(xué)者而寫的，很適合入門的一篇。文章定位：非專業(yè)性A*文章，很適合入門。

有圖有真相，先給大家看個(gè)效果圖吧：從圖的左下角到右上角尋找最短路徑，灰色部分是障礙物。

這是用一般的搜素方法，類似窮舉的效果

下面的圖是用A*搜素的效果，也就是本文要介紹的算法。

可以看出，用A*算法減少了許多計(jì)算量，它的效率有了顯著的提高。

下面將為你解答上圖中的算法是如何實(shí)現(xiàn)的。

圖片來源：http://en.wikipedia.org/wiki/A*_search_algorithm

正文

搜索區(qū)域介紹

下圖是這篇文章討論的中心：

圖中左邊的綠色點(diǎn)是搜索的起點(diǎn)A，目標(biāo)點(diǎn)是右邊的紅色點(diǎn)B，中間被障礙物擋住（藍(lán)色部分）。

我們的目的是從起點(diǎn)出發(fā)，找到一條到達(dá)目標(biāo)點(diǎn)的最短路徑。

把整個(gè)圖都分為一個(gè)個(gè)小方塊只是為了這樣方便討論，更多的應(yīng)用中，也可以把圖分為其它方塊的組合。

開始搜索

目標(biāo)是找出從A點(diǎn)出發(fā)到B的最短路徑，所以我們從A點(diǎn)開始搜索，直到找到目標(biāo)B。

搜索的步驟是這樣的：

1、從起點(diǎn)A開始把A加入到openlist中。openlist解釋：它是一個(gè)隊(duì)列，里面元素是一些方塊，它們有可能構(gòu)成最短路徑。現(xiàn)在隊(duì)列中只有元 素A，以后會(huì)加入更多的元素。以后會(huì)對(duì)里的元素進(jìn)行檢查，從里面來找到構(gòu)成最短路徑的元素。

2、看起點(diǎn)A周圍的元素是否可達(dá)（是否能從A到達(dá)它們）把從A可到達(dá)的元素加入到openlist中，并且加入到openlist中的節(jié)點(diǎn)維護(hù)一個(gè)指指針，指向他的父親，也即A點(diǎn)。如果A周圍有障礙物就忽略它。從這個(gè)圖看， A周圍把個(gè)元素都可達(dá)，所以把它們都加到openlist中。

3、把起點(diǎn)A放入closelist中，在closelist中的點(diǎn)意味著以后不需要再去考慮它了。對(duì)于A節(jié)點(diǎn)，A可達(dá)的點(diǎn)都加入到了openlist中，以后也就不用考慮A的情況了。

經(jīng)過以上三步操作后的效果圖如下所示

圖中被暗綠色包圍的就是openlist中的點(diǎn)，一共八個(gè)，都是從起點(diǎn)A可達(dá)的點(diǎn)，并且他們中的每個(gè)都有一個(gè)指向他們父節(jié)點(diǎn)的指針（圖中的小針方向）被高亮綠色包圍的表示closelist中的點(diǎn)，可以看出起點(diǎn)A已經(jīng)在closelist中。

路徑選擇

從起點(diǎn)出發(fā) ，下一步可以走的點(diǎn)現(xiàn)在有八個(gè)，選取哪一個(gè)作為下一步的點(diǎn)呢？正常的思維是選取一個(gè)離目標(biāo)值最進(jìn)，且在這些點(diǎn)中離遠(yuǎn)點(diǎn)最近的點(diǎn)。

本文的思路也是這樣的，文中用

F = G + H

表示，其中：

對(duì)于每個(gè)點(diǎn)，都有自己的G、H、F。

其中G表示從特定的點(diǎn)到起點(diǎn)的距離，H表示從該點(diǎn)到目標(biāo)的估值，那么F就是經(jīng)過該點(diǎn)路徑的估值。

下面詳細(xì)介紹

G:從起點(diǎn)到特定節(jié)點(diǎn)的距離，也就是G的父節(jié)點(diǎn)加上從G的父節(jié)點(diǎn)到起點(diǎn)A的距離g。圖中是邊長為10的正方形塊，所以就是G的父節(jié)點(diǎn)的值g

加上10（上下左右相鄰）或者加上14（斜塊相鄰、也就是對(duì)角線的長度，本來是14.14、、為了方便計(jì)算這里取近似值）

H：H能用很多方法得到估計(jì)值.這里用到的方法稱為Manhattan method，H的值就是從考慮的點(diǎn)通過水平和垂直移動(dòng)達(dá)到目標(biāo)點(diǎn)的移動(dòng)步數(shù)乘10（正方形塊的邊長為10）.注意只是水平和垂直移動(dòng)，不走斜線。并且忽略圖中的障礙物。

插一句：

看了對(duì)H的描述，你可能會(huì)懷疑這種估計(jì)的精確性，有一點(diǎn)是可以肯定的：估計(jì)值越接近真實(shí)值，算法就能更塊的找出最短路徑。我們用的這種方法確實(shí)是做了估計(jì)，只是這種估計(jì)準(zhǔn)確性不高，就是說只是粗略的估計(jì)，因?yàn)檫@種方法容易理解，所以才采用這種方法。可以想到，太過接近的估值最后不一定能得到想要的結(jié)果。關(guān)于估值函數(shù)想了解更多請(qǐng)參見：http://www.policyalmanac.org/games/heuristics.htm

為了從openlist中選取一個(gè)點(diǎn)繼續(xù)搜索，就要計(jì)算出openlist中的每個(gè)點(diǎn)的F、H、G的值然后選取F小的一個(gè)點(diǎn)，進(jìn)行下一步的探索。

對(duì)于上圖中的點(diǎn)，他們的F、G、H的值在圖中都有標(biāo)明。

F、H、G的位置在起點(diǎn)右邊的點(diǎn)中已經(jīng)有標(biāo)注，其他點(diǎn)的位置同理。

現(xiàn)在看起點(diǎn)右邊的點(diǎn)（也就是標(biāo)有字母的點(diǎn)）G=10，因?yàn)樵谄瘘c(diǎn)正左邊。H=30，水平移動(dòng)三個(gè)格子可以到目標(biāo)點(diǎn)B。F=G+H=40

繼續(xù)搜索

由于我們的目的是找最短路徑 ，下一步就從openlist中選取F最小的點(diǎn)做進(jìn)一步的搜索，按如下步驟進(jìn)行：

（為了方便描述，把選取的點(diǎn)成為點(diǎn)M）

1、檢查M周圍的點(diǎn)，在closelist中則忽略它，如果可達(dá)且不在openlist中，則加入openlist中，同理的維護(hù)一個(gè)指向父節(jié)點(diǎn)的指正，同時(shí)計(jì)算加入點(diǎn)的F H G 值。

2、如果M周圍的點(diǎn)在openlist中，則看從起點(diǎn)A通過M到這類點(diǎn)的路徑是不是小于他們的G值，如果是則更新他們的G、F值（更新為小的）。如果不是則不做任何操作。

3、把M從openlist中移除，加入closelist中。

對(duì)openlist中F最小的點(diǎn)（也就是起點(diǎn)左邊的點(diǎn)）的處理效果如下圖所示：

M的右邊、右上、右下是障礙物，所以忽略他們。M的左邊點(diǎn)在closelist中，也不去管他，剩下的是M的上、下、左上、左下的點(diǎn)。他們已經(jīng)在openlist中，所以看從起點(diǎn)通過M到他們的距離是不是小于他們的G值。通過判斷，都比他們的G值大，所以做任何操作。

可以看出，現(xiàn)在的closelist已有兩個(gè)元素了（高亮綠色包圍的塊）

下一步的操作和上面敘述的一樣，從openlist中找出F最小的，重復(fù)上的操作。從圖中可以看出，現(xiàn)在的openlist中F最小的有兩個(gè)，就是剛剛考慮的點(diǎn)的正上方和正下方，其實(shí)這里選哪個(gè)都無所謂，只是人們習(xí)慣于選擇較晚加入到openlist中的元素，這里選擇下方的點(diǎn)。

同理，處理效果如下圖所示：

下面簡單的說下處理過程：

暫且稱現(xiàn)在處理的點(diǎn)為N吧。

N上方  在closelist中，不考慮。

N左方 在openlist中，看從原點(diǎn)通過N到它的距離為14+10大于10，不做操作，跳到下一步

N的左下方，下方 加入openlist中，同時(shí)記錄F、G 、H的值還有指向父節(jié)點(diǎn)的指針。

N的右下方這里看做“不可達(dá)的點(diǎn)”原因是這兩個(gè)點(diǎn)都處于障礙物的對(duì)角上，當(dāng)然這只是一種人為的規(guī)定。也可以取消這條規(guī)定就把它加入到openlist中。這只是一種規(guī)定，不必深究。

處理的結(jié)果是closelist中現(xiàn)在有三個(gè)元素，用高亮的藍(lán)色標(biāo)記，同樣的，openlist中的元素用暗綠色標(biāo)記出。

 

重復(fù)上的步驟，每次從openlist中選取F最小的點(diǎn)加入closelist中，同時(shí)處理這個(gè)點(diǎn)周圍的元素。。

直到目標(biāo)節(jié)點(diǎn)也被加入到closelist中停止。

處理的效果如下圖所示：

如果用心看、你也許已經(jīng)發(fā)現(xiàn)了，在起點(diǎn)正下方兩個(gè)點(diǎn)的G值，沒錯(cuò)，就是圖中用橢圓圈起來的點(diǎn)，之前的G=28，現(xiàn)在是20。這是在算法進(jìn)行的時(shí)候更新的，可能 是這其中的某一步，處理這個(gè)點(diǎn)的時(shí)候，發(fā)現(xiàn)了一條更短的路徑20，替換了原來的28。

到這里，問題已經(jīng)基本解決了，最后的任務(wù)就是得到這條路徑。

只要從目標(biāo)點(diǎn)出發(fā)，沿著他們的父節(jié)點(diǎn)遍歷，直到起點(diǎn)。就得到了一條最短路徑。

如下圖所示

總結(jié)

 現(xiàn)在你應(yīng)該對(duì)A*算法有一個(gè)初步的認(rèn)識(shí)了吧，總結(jié)下算法的實(shí)現(xiàn)過程：

1、把起點(diǎn)加入到openlist中

2、重復(fù)以下步驟

　　a、從openlist中找出F最小的節(jié)點(diǎn)，并把它當(dāng)做當(dāng)前的操作節(jié)點(diǎn)

　　b、檢查當(dāng)前點(diǎn)周圍的點(diǎn)，如果已經(jīng)在openlist中看是否能通過當(dāng)前點(diǎn)得到更小的G，如果能就更新那個(gè)點(diǎn)的G，F(xiàn)的值，如果在closelist中或者是障礙物（不可達(dá)）則忽略他們

　　c、把當(dāng)前點(diǎn)從openlist中移除 ，加入closelist中

　　d、當(dāng)目標(biāo)點(diǎn)加入closelist中時(shí)停止

3、保存路徑，從目標(biāo)點(diǎn)出發(fā)，按照父節(jié)點(diǎn)指針遍歷，直到找到起點(diǎn)。

后記

 其實(shí)啟發(fā)式搜索就是對(duì)窮舉的一種優(yōu)化，讓每次搜索都更接近目標(biāo)。這就要通過估值函數(shù)實(shí)現(xiàn)，對(duì)于這類問題，找到一個(gè)估值函數(shù)是關(guān)鍵。

估值函數(shù)：從當(dāng)前點(diǎn)出發(fā)到目標(biāo)點(diǎn)的花費(fèi)。其實(shí)從這個(gè)理念上說，好像和分支界限法有些類似，都是在窮舉的基礎(chǔ)上對(duì)搜素優(yōu)化。

 

 

如有轉(zhuǎn)載請(qǐng)注明出處：

http://www.rzrgm.cn/yanlingyin/

一條魚~

尹雁鈴@博客園

尹雁鈴@博客園