張海亮，張 征

（1.山西工程科技職業(yè)大學(xué)，山西 晉中 030619；2.浙江工業(yè)大學(xué)機(jī)械工程學(xué)院，杭州 310014）

0 引言

隨著計算機(jī)技術(shù)、網(wǎng)絡(luò)技術(shù)的成熟，包括無人駕駛在內(nèi)的道路規(guī)劃［1］與最短路徑算法［2］逐漸成為研究熱點(diǎn)。

A*算法［3-4］作為最短路徑中最成熟的算法之一，在廣度優(yōu)先搜索的基礎(chǔ)上，以啟發(fā)式搜索為基礎(chǔ)，同時具有Dijkstra 算法［5］在搜索速度和效率上的優(yōu)勢。A*算法在啟發(fā)式搜索的過程中，采用了曼哈頓權(quán)值函數(shù)作為最優(yōu)鄰接點(diǎn)的評估標(biāo)準(zhǔn)，相對于廣度優(yōu)先搜索，減少了大量的無效鄰接點(diǎn)的擴(kuò)展驗(yàn)證，有效提高了算法的搜索效率［6-8］。但是對于大數(shù)據(jù)量下的網(wǎng)絡(luò)拓?fù)?，A*算法在進(jìn)行空間搜索時，算法效率呈階梯式下降，且起始點(diǎn)和目標(biāo)點(diǎn)越遠(yuǎn)，中間的間隔越大，A*算法在進(jìn)行最優(yōu)鄰接點(diǎn)選取時的時間就越長。GeoHash 索引［9］以地理經(jīng)緯度信息為基礎(chǔ)，將經(jīng)緯度信息轉(zhuǎn)化為GeoHash 值賦值給柵格節(jié)點(diǎn)，可以在A*算法中作為最優(yōu)鄰接點(diǎn)的權(quán)值評估參考，進(jìn)一步確定最優(yōu)鄰接點(diǎn)。

1 A*算法

A*算法在求解最短路徑時（如圖1a 所示），整體的思路是從起始點(diǎn)A 開始，通過迭代方式查找相鄰方格，不斷擴(kuò)展直至找到目標(biāo)點(diǎn)B。在迭代查找相鄰方格時，采用曼哈頓函數(shù)對相鄰方格進(jìn)行評估，通過對比每個相鄰方格與目標(biāo)終點(diǎn)之間的方格數(shù)，來判斷哪個方格為最優(yōu)鄰接方格，并將其作為下一步選擇的起點(diǎn)，然后再進(jìn)行迭代查找，在迭代的過程中，每次都對當(dāng)前起點(diǎn)的鄰接方格進(jìn)行曼哈頓函數(shù)評估，每次都計算出一個最優(yōu)鄰接點(diǎn)作為下一步的起點(diǎn)，這樣不斷向外擴(kuò)展，一直擴(kuò)展到目標(biāo)終點(diǎn)為止。因?yàn)樵诘倪^程中，是以當(dāng)前點(diǎn)的鄰接點(diǎn)與目標(biāo)終點(diǎn)的網(wǎng)格數(shù)作為評估標(biāo)準(zhǔn)，所以A*算法最終一定會查找到目標(biāo)終點(diǎn)。

A*算法把Dijkstra 算法（靠近初始點(diǎn)的結(jié)點(diǎn)）和BFS 算法（靠近目標(biāo)點(diǎn)的結(jié)點(diǎn)）的信息塊結(jié)合起來。在討論A*的標(biāo)準(zhǔn)術(shù)語中，G（n）表示從初始結(jié)點(diǎn)到任意結(jié)點(diǎn)n 的代價，H（n）表示從結(jié)點(diǎn)n 到目標(biāo)點(diǎn)的啟發(fā)式評估代價（heuristic estimated cost）。在圖1b中，yellow（h）表示遠(yuǎn)離目標(biāo)的結(jié)點(diǎn)，teal（g）表示遠(yuǎn)離初始點(diǎn)的結(jié)點(diǎn)。當(dāng)從初始點(diǎn)向目標(biāo)點(diǎn)移動時，A*權(quán)衡這兩者。每次進(jìn)行主循環(huán)時，它檢查f（n）最小的結(jié)點(diǎn)n，其中，F(xiàn)（n）= G（n）+ H（n）。

圖1 A*算法示意圖

通過曼哈頓函數(shù)進(jìn)行評估選擇最優(yōu)鄰接點(diǎn)也稱為啟發(fā)式搜索。A*算法在進(jìn)行當(dāng)前點(diǎn)的最優(yōu)鄰接點(diǎn)選取時，使用曼哈頓函數(shù)評估，而曼哈頓函數(shù)計算的是起始點(diǎn)和目標(biāo)點(diǎn)之間的網(wǎng)格數(shù)，然后乘以固定系數(shù)，作為每個鄰接點(diǎn)的對比值。圖2 顯示了兩個不同位置的曼哈頓函數(shù)所對應(yīng)的區(qū)別，圖2（a）中，當(dāng)鄰接點(diǎn)在起點(diǎn)A 上方時，鄰接點(diǎn)與目標(biāo)點(diǎn)B之間的曼哈頓距離評估值為4 M（M 為單個網(wǎng)格距離）；圖2（b）中，當(dāng)鄰接點(diǎn)為右下側(cè)時，鄰接點(diǎn)與目標(biāo)點(diǎn)B 之間的曼哈頓距離評估值為5 M（M 為單個網(wǎng)格距離）。所以應(yīng)該選擇上方的鄰接方格作為最優(yōu)鄰接點(diǎn)。在尋找A 點(diǎn)的鄰接點(diǎn)時，上側(cè)的鄰接點(diǎn)到目標(biāo)終點(diǎn)B 的曼哈頓權(quán)值小于右下角鄰接點(diǎn)到目標(biāo)終點(diǎn)B 的曼哈頓權(quán)值，故可對A 方格的8 個鄰接方格中的曼哈頓權(quán)值進(jìn)行比較，選取權(quán)值較小的鄰接點(diǎn)作為前進(jìn)的方向，曼哈頓權(quán)值較大的鄰接方格則直接忽略不進(jìn)行下一步的擴(kuò)展。

圖2 不同位置曼哈頓函數(shù)評估圖

當(dāng)起點(diǎn)和目標(biāo)點(diǎn)離的較遠(yuǎn)時，每個作為起點(diǎn)的方格都要進(jìn)行8 次鄰接點(diǎn)與目標(biāo)終點(diǎn)之間的網(wǎng)格計算，且每次計算時起點(diǎn)都不同，當(dāng)數(shù)據(jù)量較大時，就需要較多的時間來完成計算，從地理信息角度來看，A*算法仍有較大的優(yōu)化空間。

2 GeoHash 函數(shù)評估

地理信息系統(tǒng)（GIS）［10］中，對地理位置信息有一種快速查找索引方式——GeoHash，GeoHash 是將對象所在的經(jīng)緯度位置轉(zhuǎn)化為Base32 字符串值，并將GeoHash 值賦給對象所在的網(wǎng)格。由于GeoHash值是按照一定的規(guī)律來進(jìn)行計算的，所以在使用A*算法求解最短路徑時，可通過對比網(wǎng)格的GeoHash值來替代曼哈頓權(quán)值的計算［11］，省去鄰接網(wǎng)格與目標(biāo)網(wǎng)格進(jìn)行曼哈頓函數(shù)計算的過程，從而在大數(shù)據(jù)量的情況下，能夠優(yōu)化計算時間，大大提高A*算法的計算速度。

2.1 GeoHash 算法

在GIS 中，某一對象所在的位置，均使用經(jīng)緯度來進(jìn)行標(biāo)記，處理網(wǎng)格時，通過采用GeoHash 索引值對一個對象所在的具體位置進(jìn)行描述。例如，需要對經(jīng)緯度數(shù)據(jù)為（121.420 168，31.200 381）進(jìn)行GeoHash 值描述時，可以通過數(shù)值轉(zhuǎn)換獲得GeoHash 值，這個GeoHash 值代表的不是一個點(diǎn)的位置，而是一塊區(qū)域位置，經(jīng)緯度數(shù)值精度越高，則區(qū)域范圍越小；反之，精度越低，所代表的區(qū)域范圍越大。

由于經(jīng)緯度的精度不同，GeoHash 算法得到的值長度也不相同，為了和最短路徑相結(jié)合，使得計算出來的路徑線路符合實(shí)際的道路方向，采用與地圖街道級別相同視野的精度作為討論的標(biāo)準(zhǔn)，故采用經(jīng)緯度精度為小數(shù)點(diǎn)后6 位小數(shù)的道路圖作為討論對象。在最短路徑算法的實(shí)現(xiàn)過程中，均以經(jīng)緯度精度為6 位小數(shù)作為GeoHash 的算法精度進(jìn)行處理，對于經(jīng)緯度為（121.420 168，31.200 381）計算GeoHash 值時，則得到wtw36zz 這樣的GeoHash 值。

在精度為6 的情況下，經(jīng)緯度轉(zhuǎn)換為GeoHash值可分為4 步：

第1 步：對經(jīng)緯度范圍以（-90，90）和（-180，180）進(jìn)行對半取值，以經(jīng)度為例，value=113.918 646，大于中間值為1，小于中間值為0。這個區(qū)間如何得來的呢？要知道經(jīng)度的范圍是［180，-180］，那么中間值就是0，判斷是在［180，0］還是［0，-180］，如果在［180，0］，就是1，然后縮小區(qū)間。查看當(dāng)前經(jīng)緯度所在區(qū)間，前半?yún)^(qū)間為負(fù)區(qū)間，值為0，后半?yún)^(qū)間為正區(qū)間，值為1，遞歸計算。記錄經(jīng)緯度所在區(qū)間值，經(jīng)度獲取的二進(jìn)制數(shù)值為110101100101011111，緯度獲取的二進(jìn)制數(shù)值為10101100010111111。

第2 步：將經(jīng)緯度對半劃分區(qū)間得到的二進(jìn)制數(shù)進(jìn)行組合，以奇數(shù)為緯度，偶數(shù)為經(jīng)度進(jìn)行組合，得到一長串二進(jìn)制字符串。圖3 計算出的二進(jìn)制字符串為：111001100111100000110011011111 11111。

圖3 經(jīng)緯度二進(jìn)制編碼轉(zhuǎn)換圖

第3 步：將獲取到的二進(jìn)制字符串以每5 個數(shù)為一組，將每一組轉(zhuǎn)換成十進(jìn)制數(shù)字。

第4 步：將取得的十進(jìn)制數(shù)字參照Base32 編碼轉(zhuǎn)為對應(yīng)的字符，將得到的字符連起來即為wtw36zz。

按照Base32 的字符集取值，最終的GeoHash 的結(jié)果為wtw36zz。

圖4 十進(jìn)制數(shù)字與Base32 編碼對應(yīng)關(guān)系圖

圖5 二進(jìn)制編碼轉(zhuǎn)換為Base32 編碼

2.2 GeoHash 對比原理

每個方格的GeoHash 值是根據(jù)方格所在位置的經(jīng)緯度進(jìn)行計算的，隨著經(jīng)緯度的變化，方格的GeoHash 值也呈規(guī)律性變化，由于GeoHash 值使用Base32 值的字符串來表示，所以方格之間的距離遠(yuǎn)近可以通過方格的GeoHash 值來進(jìn)行判斷。圖6 為上海的一塊區(qū)域，可以通過對比方格的GeoHash 值來查看方格之間的距離關(guān)系。

圖6 GeoHash 索引

為方便查看，首先取第2 行來進(jìn)行對比，（2，1）方格區(qū)域的GeoHash 值為wtw36zz，當(dāng)經(jīng)度增加時，（2，2）方格區(qū)域的GeoHash 值為wtw37pb，（2，3）方格區(qū)域的GeoHash 值為wtw37pc，（2，4）方格區(qū)域的GeoHash 值為wtw37pf，（2，5）方格區(qū)域的GeoHash值為wtw37pg。第2 行左側(cè)依次到右側(cè)，第1 個方格與第2 個方格比較，去除前面相同的wtw3 部分，經(jīng)度越大，則其不同部分的第1 位數(shù)值越大，也就是7＞6；第2 個方格與第3 個方格比較，去除前面相同的wtw37p 部分，后面的c＞b，第4 個方格的f＞c，第5個方格的g＞f；然后選取整個區(qū)域第3 列來比較緯度變化情況，（3，3） 方格區(qū)域的GeoHash 值為wtw37p9，當(dāng)緯度增加時，（2，3）方格區(qū)域?qū)?yīng)的GeoHash 值為wtw37pc，c＞9，（1，3）方格區(qū)域所對應(yīng)的GeoHash 對應(yīng)的值為wtw3e01，去除前面相同的wtw3，第4 位的e＞7。遍歷圖中所有方格，GeoHash值都遵循一個相同的變化規(guī)律，那就是：隨著經(jīng)緯度的增加，其對應(yīng)的方格所在的GeoHash 值，是隨著Base32 的字符順序逐級增加的，而且當(dāng)個位數(shù)不夠增加時，則在更高一位進(jìn)行遞增。圖6 中，從經(jīng)緯度最小的左下角wtw36zx（121.420 034，31.199 44）逐位遞增到右上角wtw3e05（121.425 318，31.201 909），由此可以得出，在經(jīng)緯度的精度確定的情況下，經(jīng)緯度所對應(yīng)的方格的GeoHash 值的規(guī)律是隨著經(jīng)緯度的增加，其GeoHash 值越大。因此，在進(jìn)行A*算法時，可以通過GeoHash 值對比來確定最優(yōu)鄰接點(diǎn)。

2.3 GeoHash 作為評估函數(shù)的A＊算法

從下頁圖7 可以看到，（a）中起點(diǎn)A 的GeoHash值為wtw37pb，目標(biāo)點(diǎn)B 的GeoHash 值為wtw3e05，當(dāng)選擇起點(diǎn)A 的上方鄰接點(diǎn)時，其GeoHash 值為wtw3e00，與目標(biāo)點(diǎn)相同的部分有wtw3e0，共有6 位相同數(shù)；而（b）中選擇下方的鄰接點(diǎn)時，其GeoHash值為wtw37p8，與目標(biāo)點(diǎn)B 的GeoHash 值wtw3e05只有4 位相同數(shù)，而且wtw3e00 與wtw37p8 相比較，第5 位的e 從Base32 上的編碼上更接近于B 點(diǎn)GeoHash 值wtw3e05，所以（a）中上方的鄰接點(diǎn)更接近于目標(biāo)點(diǎn)B，由此可判斷上方鄰接點(diǎn)相對于下方鄰接點(diǎn)為最優(yōu)鄰接點(diǎn)。右側(cè)的鄰接點(diǎn)（wtw37pc），與上方的鄰接點(diǎn)在最短路徑的距離上是相同的，求解最短路徑的目的是找到最短路徑，故上述任一點(diǎn)均可選擇。

圖7 不同位置曼哈頓函數(shù)評估圖

由于經(jīng)緯度是固定存在的位置信息，且不會發(fā)生改變，所以在查找最短路徑時，可根據(jù)起始點(diǎn)的位置和目標(biāo)點(diǎn)的位置，確定這兩點(diǎn)的GeoHash 值，比較其GeoHash 值相同的部分以及不同的部分，確定其大小關(guān)系，進(jìn)行查找最優(yōu)鄰接點(diǎn)時，對比鄰接點(diǎn)的GeoHash 值與目標(biāo)點(diǎn)的GeoHash 值，越接近（Base32 編碼為順序）目標(biāo)點(diǎn)的GeoHash 的方格，則作為最優(yōu)鄰接點(diǎn)的候選點(diǎn)。GeoHash 是固定字符值，可直接進(jìn)行字符比較，無需像曼哈頓評估函數(shù)那樣計算當(dāng)前鄰接點(diǎn)和目標(biāo)節(jié)點(diǎn)之間的方格數(shù)，可大大提升計算效率。

以下為使用GeoHash 值作為最優(yōu)鄰接點(diǎn)評估函數(shù)的A*算法過程，如圖8 所示。

圖8 GeoHash 值作為最優(yōu)鄰接點(diǎn)評估函數(shù)的A*算法過程

1）首先將A 點(diǎn)作為待處理節(jié)點(diǎn)存入FrontList集合中，F(xiàn)rontList 包含所有需要進(jìn)行擴(kuò)展但是還沒有進(jìn)行擴(kuò)展的節(jié)點(diǎn)集合。

2）以FrontList 作為鏈表，將里面的每個節(jié)點(diǎn)作為新的起點(diǎn)L，尋找起點(diǎn)所有可到達(dá)的鄰接方格，并將查詢到的最優(yōu)鄰接點(diǎn)存在FrontList 中，最優(yōu)鄰接點(diǎn)根據(jù)鄰接方格的GeoHash 值與目標(biāo)點(diǎn)的GeoHash值對比進(jìn)行判斷，與目標(biāo)點(diǎn)的GeoHash 值相同部分最多的方格即為最優(yōu)鄰接點(diǎn)方格。將L 點(diǎn)從FrontList 中刪除，并將L 點(diǎn)存入到StepList 列表中。

3）循環(huán)執(zhí)行步驟2。當(dāng)然，有一種特殊情況需要處理，就是當(dāng)使用L點(diǎn)作為起點(diǎn)查找鄰接點(diǎn)K，再以鄰接點(diǎn)K 查找鄰接點(diǎn)時，L 點(diǎn)也會作為K 點(diǎn)的鄰接點(diǎn)被查找到，這種情況下，需要把L 點(diǎn)排除，也就是說已經(jīng)保存在StepList 或者FrontList 的點(diǎn)不能再次作為鄰接點(diǎn)進(jìn)入FrontList，否則會形成一個死循環(huán)。

4）當(dāng)查找到的鄰接點(diǎn)為目標(biāo)點(diǎn)B 時，跳出循環(huán)，逆向查找起始點(diǎn)序列，得到最短路徑。

從GeoHash 的編碼規(guī)則來看，GeoHash 算法和曼哈頓函數(shù)的原理是一樣的，曼哈頓函數(shù)以當(dāng)前點(diǎn)與目標(biāo)點(diǎn)之間的方形區(qū)域網(wǎng)格數(shù)作為評估標(biāo)準(zhǔn)，網(wǎng)格數(shù)越少的鄰接方格作為最優(yōu)鄰接點(diǎn)；而GeoHash算法以當(dāng)前點(diǎn)GeoHash 編碼值與目標(biāo)點(diǎn)GeoHash值作為評估標(biāo)準(zhǔn)，相同位數(shù)越多的鄰接方格作為最優(yōu)節(jié)點(diǎn)。在具有GeoHash 值的網(wǎng)格進(jìn)行最短路徑分析過程中，兩個網(wǎng)格GeoHash 值字符相同的位數(shù)越多，則兩者之間的方形區(qū)域網(wǎng)格數(shù)越少，也就代表兩者距離越近。GeoHash 是以索引值的形式對坐標(biāo)位置定義，是已經(jīng)存在的數(shù)據(jù)，其優(yōu)勢在于節(jié)省了以曼哈頓距離函數(shù)作為評估標(biāo)準(zhǔn)時，對每次的最優(yōu)鄰接點(diǎn)求解時，依次計算鄰接點(diǎn)與目標(biāo)點(diǎn)之間的網(wǎng)格計算過程。

因?yàn)镚eoHash 算法是針對于地理信息系統(tǒng)中經(jīng)緯度的索引算法，使用GeoHash 算法對A*最短路徑算法進(jìn)行鄰接點(diǎn)評估，適合存在實(shí)際地理位置也就是有經(jīng)緯度的情況下，對于只存在網(wǎng)絡(luò)節(jié)點(diǎn)和權(quán)值的拓?fù)渚W(wǎng)絡(luò)，沒有實(shí)際的評估意義，當(dāng)然也可以將拓?fù)渚W(wǎng)絡(luò)根據(jù)其權(quán)重進(jìn)行地理位置模擬以及GeoHash 值計算，從實(shí)際工作復(fù)雜度和工作效率上來說意義不大。

［1］蘇浩，李欽富，蔡俊.A*算法在基于道路網(wǎng)的路徑規(guī)劃中的應(yīng)用［J］. 中國電子科學(xué)研究院學(xué)報，2010，5（4）：419-422.

［2］胡恩祥，汪春雨，潘美芹.基于密度峰值剪枝后的最短路徑聚類算法［J］.應(yīng)用科學(xué)學(xué)報，2020，38（5）：792-802.

［3］肖自兵，屈耀紅，袁冬莉.基于障礙信息的高效A-Star 航路規(guī)劃算法［J］.火力與指揮控制，2018，43（9）：71-75.

［4］衛(wèi)珊，王凌，王斌銳，等.A*算法的改進(jìn)及其在AGV 路徑規(guī)劃中的應(yīng)用［J］.自動化儀表，2017，38（11）：51-54.

［5］賀麗娜，樓佩煌，錢曉明，等.基于時間窗的自動導(dǎo)引車無碰撞路徑規(guī)劃［J］.計算機(jī)集成制造系統(tǒng)，2010，16（12）：2630-2634.

［6］羅子涵，彭曠，戴銘酉，等.基于改進(jìn)分層A*算法的雨天車輛導(dǎo)航方法［J］.計算機(jī)應(yīng)用，2020，40（s2）：210-214.

［7］岳秀，張超峰，張偉，等.基于A-Star 和改進(jìn)模擬退火算法的航跡規(guī)劃［J］.控制工程，2020，27（8）：1365-1371.

［8］王中玉，曾國輝，黃勃.基于改進(jìn)雙向A*的移動機(jī)器人路徑 規(guī) 劃 算 法［J］. 傳 感 器 與 微 系 統(tǒng)，2020，39（11）：141-143，147.

［9］YU K，QU C Y.Prediction and optimization of sharing bikes queuing model in grid of Geohash coding［J］.Measurement&Control，2020，53（7-8）：1250-1266.

［10］SHAO Z F，HUQ M E，CAI B W，et al.Integrated remote sensing and GIS approach using Fuzzy-AHP to delineate and identify groundwater potential zones in semi-arid ShanxI Province，China ［J］.Environmental Modelling &Software，2020：134.

［11］WANG C B，WANG L，QIN J，et al.Path planning of automated guided vehicles based on improved A-Star algorithm ［C］//2015 IEEE International Conference on Information and Automation：2015 IEEE International Conference on Information and Automation（ICIA），in conjunction with 2015 IEEE International Conference on Automation and Logistics，Lijiang，Yunnan，China，2015.