陳暄

摘要：從起點(diǎn)繞開障礙物快速達(dá)終點(diǎn)是A*算法的主要研究?jī)?nèi)容，該文針對(duì)該算法存在效率低，不適合面積大的路徑的缺點(diǎn)，提出了改進(jìn)的A*算法措施，主要從優(yōu)化Open表，優(yōu)化估計(jì)函數(shù)等兩個(gè)主要方面進(jìn)行改進(jìn)。仿真實(shí)驗(yàn)將改進(jìn)后的A*算法與基本A*算法在消耗時(shí)間和節(jié)點(diǎn)訪問量方面進(jìn)行了對(duì)比，取得了明顯的效果，說明該文算法具有一定的研究?jī)r(jià)值。

關(guān)鍵詞： A*算法；優(yōu)化函數(shù)；open表

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2017）29-0184-03

A*算法是一種時(shí)間最優(yōu)的啟發(fā)式搜索算法，它能夠高效而且準(zhǔn)確的找到一條可達(dá)的最短路徑，并被廣泛應(yīng)用于GIS系統(tǒng)和尋找路徑的方案中，它與老式的搜索算法諸如深度優(yōu)先搜索算法，廣度優(yōu)先搜索算法，Dijkstra搜索算法[1-2]，在時(shí)間復(fù)雜度和空間復(fù)雜度要好的很多，但由于它的性能消耗伴隨著搜索地圖規(guī)模的擴(kuò)大而成指數(shù)級(jí)增加。一些學(xué)者對(duì)其進(jìn)行了研究，文獻(xiàn)[4]提出一種基于改進(jìn)A*算法的電動(dòng)車能耗最優(yōu)路徑規(guī)劃方法。通過，建立運(yùn)行能耗函數(shù)，設(shè)計(jì)了新的啟發(fā)式能耗預(yù)估代價(jià)對(duì)A*算法進(jìn)行改進(jìn)，證明了所提出的啟發(fā)式能耗預(yù)估代價(jià)滿足可采納性和一致性；文獻(xiàn)[5]使用最小二叉堆和標(biāo)記數(shù)組兩種混合數(shù)據(jù)結(jié)構(gòu)優(yōu)化open表的存儲(chǔ)和遍歷，用夾角余弦值作為新的啟發(fā)信息，減少搜索過程中對(duì)非最有節(jié)點(diǎn)的考察量；文獻(xiàn)[6]提出了一種改進(jìn)的A*算法。首先，采用柵格方法建立環(huán)境模型，使用A*算法進(jìn)行初步的路徑規(guī)劃。其次，針對(duì)A*算法規(guī)劃的路徑冗余點(diǎn)較多以及路徑長(zhǎng)度和轉(zhuǎn)折角度較大的缺陷，提出將A*算法規(guī)劃出的路徑按較小的分割步長(zhǎng)進(jìn)行分割，得到一系列路徑節(jié)點(diǎn)。

本文在文獻(xiàn)[7]研究的基礎(chǔ)上，根據(jù)A*算法出現(xiàn)的問題進(jìn)行改進(jìn)，從優(yōu)化Open表，沿著目標(biāo)方向搜索，沿著目標(biāo)點(diǎn)移動(dòng)，避免“死胡同”等方面進(jìn)行描述，取得了比較好的效果。

1 A*算法

A*算法是一種啟發(fā)式的路徑搜索算法，其本質(zhì)是從起點(diǎn)到終點(diǎn)盡可能地選擇一條最短路徑的算法。與目前經(jīng)典的搜索算法不同，在A*算法中，設(shè)計(jì)了一個(gè)估價(jià)函數(shù)，其表達(dá)如下：

其中表示是從當(dāng)前結(jié)點(diǎn)展開搜索出來的結(jié)點(diǎn)的估計(jì)函數(shù)，表示從當(dāng)前節(jié)點(diǎn)結(jié)點(diǎn)到預(yù)處理搜索點(diǎn)的實(shí)際函數(shù)，則表示預(yù)處理的結(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的估價(jià)函數(shù)。采用Start表示起點(diǎn)，open表示存儲(chǔ)沒有訪問的節(jié)點(diǎn)，使用End表存儲(chǔ)已經(jīng)訪問過的節(jié)點(diǎn)，其步驟如下：

步驟1：把起點(diǎn)作為第一個(gè)結(jié)點(diǎn)放入Start列表中。

步驟2：處理start的周圍結(jié)點(diǎn)，一般選擇該節(jié)點(diǎn)周圍（上下，左右，左右斜上斜下）中的8個(gè)方位的節(jié)點(diǎn)，且將8個(gè)方位的父節(jié)點(diǎn)設(shè)置為該Start結(jié)點(diǎn)。

步驟3：當(dāng)周圍結(jié)點(diǎn)搜索完畢后，將start節(jié)點(diǎn)從open表的集合列表中刪除，同時(shí)放入end集合列表中。

步驟4：先檢查沒有訪問的這些節(jié)點(diǎn)，當(dāng)確認(rèn)是可用結(jié)點(diǎn)，則計(jì)算那些預(yù)處理結(jié)點(diǎn)的，和值并進(jìn)行比較，將最小的結(jié)點(diǎn)存儲(chǔ)到open集合列表中，以便下一次使用。

步驟5：當(dāng)某個(gè)預(yù)處理結(jié)點(diǎn)已經(jīng)在open集合列表中了，如果此時(shí)使用新的路徑對(duì)應(yīng)的估價(jià)函數(shù)值更低，則使用此條路徑進(jìn)行更新，反之則不更新。

步驟6：判斷該節(jié)點(diǎn)周圍的節(jié)點(diǎn)是否為終點(diǎn)，如果不是則重復(fù)執(zhí)行步驟4和5，反之則結(jié)束并根據(jù)之前每個(gè)結(jié)點(diǎn)存在的父節(jié)點(diǎn)進(jìn)行回溯找到終點(diǎn)，記錄這條路徑，算法結(jié)束。

從A*中算法中發(fā)現(xiàn)最重要的步驟就是啟發(fā)式函數(shù)的選擇，當(dāng)選擇不同的啟發(fā)式函數(shù)就會(huì)造成不同搜索范圍，當(dāng)搜索范圍越小則搜索路徑越精確從而造成的誤差就會(huì)越少。一旦在前進(jìn)路徑中出現(xiàn)多個(gè)障礙的時(shí)候，就會(huì)出現(xiàn)無意義的搜索，因此浪費(fèi)了大量不必要的時(shí)間和空間。

2 改進(jìn)的A*算法

2.1 優(yōu)化Open表

A*算法的運(yùn)行過程中主要是按照移入、排序、移出的步驟來進(jìn)行的，其中所耗費(fèi)的主要代價(jià)在于”排序”，其目的是為了能夠方便的尋找出open表中最小的頂點(diǎn)。當(dāng)移動(dòng)機(jī)器人所處的面積比較大的時(shí)候，出行路線很長(zhǎng)的話，open表中的數(shù)據(jù)量將很大，當(dāng)反復(fù)查詢這張open表的時(shí)候會(huì)導(dǎo)致算法運(yùn)行所需的時(shí)間代價(jià)更高。因此open表的數(shù)據(jù)結(jié)構(gòu)決定了算法效率的高低，在一定程度上能夠有效地提高搜索效率，因此能夠迅速的尋找出值最小的頂點(diǎn)。

在A*算法運(yùn)行過程中，需要重復(fù)搜索open表中值最小的頂點(diǎn)，當(dāng)采用最小二叉堆的存儲(chǔ)方式保存open表，則最小二叉堆的堆頂點(diǎn)的值就是需要搜索的數(shù)值。在最小二叉堆的存儲(chǔ)方法過程中使用堆排序的方法就能迅速地找到值。

2.2 優(yōu)化估計(jì)函數(shù)

A*算法中的估價(jià)函數(shù)中整個(gè)算法的核心部分，這是因?yàn)楣纼r(jià)函數(shù)的效果直接影響到算法在運(yùn)行過程中遍歷的頂點(diǎn)數(shù)，從而減少了open表中的數(shù)據(jù)量，因此可以提高算法的尋徑效率，從而搜索出更優(yōu)的路徑。從A*算法中的表達(dá)式來看，作為既定值，其改進(jìn)空間不大，啟發(fā)函數(shù)才是估價(jià)函數(shù)的重要組成部分。本文使用向量空間中的方向識(shí)別模型，對(duì)的計(jì)算量進(jìn)行優(yōu)化。其優(yōu)化主要集中在決策階段和行動(dòng)階段，也就是下一個(gè)行動(dòng)點(diǎn)和向下一個(gè)行動(dòng)點(diǎn)移動(dòng)的兩個(gè)階段。傳統(tǒng)的算法中在決定下一個(gè)移動(dòng)點(diǎn)的時(shí)候，只有依靠的最小值，從open列表中選擇出估值函數(shù)最小的節(jié)點(diǎn)。本文對(duì)open列表中的節(jié)點(diǎn)進(jìn)行雙層排序，也就是說估值函數(shù)大小的排序和是否在當(dāng)前節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)方向上的排序。當(dāng)存在可以到達(dá)路徑的情況下，優(yōu)化選擇在目標(biāo)方向上移動(dòng)的節(jié)點(diǎn)，會(huì)更快地完成尋優(yōu)的路徑。在行動(dòng)過程中，根據(jù)決策階段的選擇進(jìn)行尋路的過程中會(huì)存在這樣的問題，在可能出現(xiàn)的目標(biāo)方向上，選擇的路徑可能無法走通，即“死胡同”路徑，為了避免這種情況的發(fā)生，就需要記錄途中被舍棄的鄰居節(jié)點(diǎn)，這樣當(dāng)路徑進(jìn)入死胡同的時(shí)候，還可以從已經(jīng)被記錄下的舍棄的鄰居節(jié)點(diǎn)中選擇最優(yōu)的方案。因此本文算法的優(yōu)化策略如下。

2.2.1 沿著目標(biāo)方向搜索endprint

規(guī)則1：在已知節(jié)點(diǎn)S，起始節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)G，設(shè)節(jié)點(diǎn)S和鄰居節(jié)點(diǎn)構(gòu)成集合NS，節(jié)點(diǎn)S和集合NS中的每個(gè)節(jié)點(diǎn)對(duì)應(yīng)的向量SG構(gòu)成集合W。當(dāng)集合W中的元索與起始節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)所構(gòu)成向量的點(diǎn)積大于0，或者節(jié)點(diǎn)S有且僅有一個(gè)鄰居節(jié)點(diǎn)，稱集合W中元索對(duì)應(yīng)的鄰居節(jié)點(diǎn)在目標(biāo)方向上。

在圖1中當(dāng)節(jié)點(diǎn)G在節(jié)點(diǎn)S的水平位置或者豎直向上位置的時(shí)候，根據(jù)規(guī)則1，可以得到S-up，S-left和S-down這些節(jié)點(diǎn)不滿足規(guī)則1.因此，可以去掉S-up，S-left和S-down這三個(gè)節(jié)點(diǎn)的計(jì)算。同理，如圖2所示，節(jié)點(diǎn)S-left和節(jié)點(diǎn)S-down這兩個(gè)節(jié)點(diǎn)也不滿足規(guī)則1，因此需要去除這兩個(gè)節(jié)點(diǎn)的計(jì)算，當(dāng)沿著目標(biāo)方向進(jìn)行搜索的時(shí)候，當(dāng)沿著SG方向走入“死胡同”的時(shí)候，為了能夠返回被去除的節(jié)點(diǎn)，需要將這些節(jié)點(diǎn)存儲(chǔ)到RightList中。

2.2.2 沿著目標(biāo)點(diǎn)移動(dòng)

根據(jù)規(guī)則1中去掉的那些不在目標(biāo)方向上的節(jié)點(diǎn)，因此減少了計(jì)算量。根據(jù)一般的尋路原理，不會(huì)往遠(yuǎn)離目標(biāo)方向的節(jié)點(diǎn)移動(dòng)。因此如圖3所示，在一次尋路過程中某個(gè)中間位置，節(jié)點(diǎn)S1的四個(gè)鄰居節(jié)點(diǎn)都在目標(biāo)方向上，會(huì)選擇從節(jié)點(diǎn)S-right和節(jié)點(diǎn)S-down中選擇最優(yōu)節(jié)點(diǎn)作為下一個(gè)前進(jìn)節(jié)點(diǎn)，因此定義如下規(guī)則

規(guī)則2：當(dāng)已經(jīng)目標(biāo)節(jié)點(diǎn)G，節(jié)點(diǎn)S1在目標(biāo)方向上，節(jié)點(diǎn)S1與它所有鄰居節(jié)點(diǎn)構(gòu)成集合NS1，節(jié)點(diǎn)S與集合NS1中的每一個(gè)節(jié)點(diǎn)對(duì)應(yīng)的向量構(gòu)成集合W1。當(dāng)集合W1中元索與節(jié)點(diǎn)S1和目標(biāo)節(jié)點(diǎn)構(gòu)成了向量S1G的點(diǎn)面積大于0，或者S1有且僅有一個(gè)鄰居節(jié)點(diǎn)，因此集合W1中的元索對(duì)應(yīng)的鄰居節(jié)點(diǎn)在移動(dòng)方向上。 當(dāng)向目標(biāo)方向移動(dòng)的過程中，所有滿足規(guī)則2的節(jié)點(diǎn)都放入OpenList表中，這樣能夠保證節(jié)點(diǎn)在走入“死胡同”的時(shí)候，能夠返回到被去除的節(jié)點(diǎn)，將規(guī)則2中的去除的節(jié)點(diǎn)存入ReverseList，如圖4所示，圖中的節(jié)點(diǎn)S-down和節(jié)點(diǎn)S-right滿足規(guī)則2，因此放入Openlist中，節(jié)點(diǎn)S-up與節(jié)點(diǎn)S-light不滿足規(guī)則2，將他們放入ReverseMovelist中，這樣能夠有效的減少節(jié)點(diǎn)S1-up和節(jié)點(diǎn)S1-left的計(jì)算，能夠減少對(duì)這2個(gè)節(jié)點(diǎn)的的計(jì)算。

2.2.3 采用回溯法避免“死胡同”

根據(jù)規(guī)則1和規(guī)則2，當(dāng)向著目標(biāo)節(jié)點(diǎn)移動(dòng)的過程中，進(jìn)入“死胡同”的情況時(shí)候，先將ReverseMoveList中的元索移入到OpenList中，然后繼續(xù)查詢，如果還沒有移動(dòng)到目標(biāo)節(jié)點(diǎn)，則表示前進(jìn)的方向是錯(cuò)誤的，需要將RightList表移動(dòng)到OpenList中，繼續(xù)尋找路徑，這樣可以使得使得計(jì)算效率上明顯優(yōu)于傳統(tǒng)的A*算法。

3 改進(jìn)的A*算法代碼描述

選擇一個(gè)N*N的網(wǎng)格地圖；其中設(shè)置Open列表和Close列表分別用來存放將要訪問的節(jié)點(diǎn)和己經(jīng)訪問過并且被排除掉的節(jié)點(diǎn)，兩個(gè)集合中的節(jié)點(diǎn)按估值函數(shù)大小升序排序；使用Temp棧用來存放在方向引導(dǎo)過程中刪除的節(jié)點(diǎn)；設(shè)置起始點(diǎn)節(jié)點(diǎn)S和目標(biāo)節(jié)點(diǎn)E。如果從始點(diǎn)節(jié)點(diǎn)S到目標(biāo)節(jié)點(diǎn)E存在可以到達(dá)的最短路徑，則利用函數(shù)reconstruc_path輸出該路徑上所有節(jié)點(diǎn)集合；否則，輸出不存在路徑，即節(jié)點(diǎn)集合為空。

部分偽代碼如下：

[Open ={S}， Close={}， Temp={}

while Open has Node do

if tempNode equal E then output path with tempNode

else do

Set NList={neighbours of tempNode}

for each node in N1List do

if Close not contains node then

if N1ist.Count >1 and node is not in direction from S to E then

push node into Temp

else do

if node is in direction from tempNode to E then

calculate the value of heuristic function for node

push node into Open

set tempNode as node's parrent node

else do

push node into Temp

push tempNode into Close

remove tempNode from Open

if Open. Count =0 and tempNode is not E

Popup the first node in Temp，and push it into Open

if tempNode is not E

There is no way from S to E ]

4 實(shí)驗(yàn)分析

創(chuàng)建一個(gè)地圖，如圖5所示。并在網(wǎng)格地圖中進(jìn)行以下說明，設(shè)置起始節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)；在網(wǎng)格地圖中設(shè)置障礙物；調(diào)用A*優(yōu)化算法；得出最短路徑。同時(shí)對(duì)地圖進(jìn)行相關(guān)參數(shù)方面的設(shè)置。按照上述模擬實(shí)驗(yàn)步驟，設(shè)置網(wǎng)格面積分別為20*20， 30*30， 40*40，50*50，進(jìn)行多次模擬實(shí)驗(yàn)，最終得出了A*優(yōu)化算法和傳統(tǒng)A*算法的消耗時(shí)間和節(jié)點(diǎn)訪問數(shù)量對(duì)應(yīng)的數(shù)據(jù)，如表1和表2所示。

結(jié)束語

本文首先對(duì)A*算法存在的問題進(jìn)行了描述，提出了優(yōu)化A*算法的相關(guān)步驟，并通過實(shí)驗(yàn)的對(duì)比來說明了優(yōu)化后的算法的性能優(yōu)于基本算法，取得了比較好的效果。

參考文獻(xiàn)：

[1] 田翠華，許衛(wèi)平，陳玉明.深度優(yōu)先遍歷算法、隨機(jī)布點(diǎn)法及回溯法在迷宮游戲中的應(yīng)用[J].河北北方學(xué)院學(xué)報(bào)：自然科學(xué)版，2013， 29（3）；19-24.

[2] 盧啟衡，馮曉紅.基于寬度優(yōu)先搜索的路徑生成算法[J].現(xiàn)代計(jì)算機(jī)：專業(yè)版，2006（12）；87-89.

[3] 蔚潔，楊懷雷，成汝震.基于Dijkstra算法的最優(yōu)路徑搜索方法[J].河北師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2008，32（5）； 590-593.

[4] 顧青.基于改進(jìn)A*算法的電動(dòng)車能耗最優(yōu)路徑規(guī)劃[J].農(nóng)業(yè)機(jī)械學(xué)報(bào)，2015，46（12）：316-322.

[5] 陳素瓊.基于改進(jìn)A*算法的地圖游戲?qū)窖芯縖J].重慶師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2017，34（4）：75-78.

[6] 孫煒.基于一種改進(jìn)A*算法的移動(dòng)機(jī)器人路徑規(guī)劃[J].湖南大學(xué)學(xué)報(bào)：自然科學(xué)版，2017，44（4）：94-101.

[7] 趙振國.向量空間中A*算法的優(yōu)化及應(yīng)用[D].哈爾濱理工大學(xué)，2016，3.endprint