基于GeoHash 索引的A*算法優(yōu)化*

張海亮，張 征

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

0 引言

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

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

1 A*算法

A*算法在求解最短路徑時(shí)（如圖1a 所示），整體的思路是從起始點(diǎn)A 開始，通過迭代方式查找相鄰方格，不斷擴(kuò)展直至找到目標(biāo)點(diǎn)B。在迭代查找相鄰方格時(shí)，采用曼哈頓函數(shù)對(duì)相鄰方格進(jìn)行評(píng)估，通過對(duì)比每個(gè)相鄰方格與目標(biāo)終點(diǎn)之間的方格數(shù)，來判斷哪個(gè)方格為最優(yōu)鄰接方格，并將其作為下一步選擇的起點(diǎn)，然后再進(jìn)行迭代查找，在迭代的過程中，每次都對(duì)當(dāng)前起點(diǎn)的鄰接方格進(jìn)行曼哈頓函數(shù)評(píng)估，每次都計(jì)算出一個(gè)最優(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ù)作為評(píng)估標(biāo)準(zhǔn)，所以A*算法最終一定會(huì)查找到目標(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 的代價(jià)，H（n）表示從結(jié)點(diǎn)n 到目標(biāo)點(diǎn)的啟發(fā)式評(píng)估代價(jià)（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)移動(dòng)時(shí)，A*權(quán)衡這兩者。每次進(jìn)行主循環(huán)時(shí)，它檢查f（n）最小的結(jié)點(diǎn)n，其中，F(xiàn)（n）= G（n）+ H（n）。

圖1 A*算法示意圖

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

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

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

2 GeoHash 函數(shù)評(píng)估

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

2.1 GeoHash 算法

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

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

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

第1 步：對(duì)經(jīng)緯度范圍以（-90，90）和（-180，180）進(jìn)行對(duì)半取值，以經(jīng)度為例，value=113.918 646，大于中間值為1，小于中間值為0。這個(gè)區(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ì)算。記錄經(jīng)緯度所在區(qū)間值，經(jīng)度獲取的二進(jìn)制數(shù)值為110101100101011111，緯度獲取的二進(jìn)制數(shù)值為10101100010111111。

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

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

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

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

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

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

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

2.2 GeoHash 對(duì)比原理

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

圖6 GeoHash 索引

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

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

從下頁圖7 可以看到，（a）中起點(diǎn)A 的GeoHash值為wtw37pb，目標(biāo)點(diǎn)B 的GeoHash 值為wtw3e05，當(dāng)選擇起點(diǎn)A 的上方鄰接點(diǎn)時(shí)，其GeoHash 值為wtw3e00，與目標(biāo)點(diǎn)相同的部分有wtw3e0，共有6 位相同數(shù)；而（b）中選擇下方的鄰接點(diǎn)時(shí)，其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)相對(duì)于下方鄰接點(diǎn)為最優(yōu)鄰接點(diǎn)。右側(cè)的鄰接點(diǎn)（wtw37pc），與上方的鄰接點(diǎn)在最短路徑的距離上是相同的，求解最短路徑的目的是找到最短路徑，故上述任一點(diǎn)均可選擇。

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

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

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

圖8 GeoHash 值作為最優(yōu)鄰接點(diǎn)評(píng)估函數(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 作為鏈表，將里面的每個(gè)節(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值對(duì)比進(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)時(shí)，L 點(diǎn)也會(huì)作為K 點(diǎn)的鄰接點(diǎn)被查找到，這種情況下，需要把L 點(diǎn)排除，也就是說已經(jīng)保存在StepList 或者FrontList 的點(diǎn)不能再次作為鄰接點(diǎn)進(jìn)入FrontList，否則會(huì)形成一個(gè)死循環(huán)。

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

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

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

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

［2］胡恩祥，汪春雨，潘美芹.基于密度峰值剪枝后的最短路徑聚類算法［J］.應(yīng)用科學(xué)學(xué)報(bào)，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］.自動(dòng)化儀表，2017，38（11）：51-54.

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

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

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

［8］王中玉，曾國(guó)輝，黃勃.基于改進(jìn)雙向A*的移動(dòng)機(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.