一種改進的A*算法在路徑規(guī)劃中的研究

陳暄

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

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

中圖分類號：TP393 文獻標識碼：A 文章編號：1009-3044（2017）29-0184-03

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

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

1 A*算法

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

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

步驟1：把起點作為第一個結點放入Start列表中。

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

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

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

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

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

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

2 改進的A*算法

2.1 優(yōu)化Open表

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

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

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

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

2.2.1 沿著目標方向搜索endprint

規(guī)則1：在已知節(jié)點S，起始節(jié)點和目標節(jié)點G，設節(jié)點S和鄰居節(jié)點構成集合NS，節(jié)點S和集合NS中的每個節(jié)點對應的向量SG構成集合W。當集合W中的元索與起始節(jié)點和目標節(jié)點所構成向量的點積大于0，或者節(jié)點S有且僅有一個鄰居節(jié)點，稱集合W中元索對應的鄰居節(jié)點在目標方向上。

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

2.2.2 沿著目標點移動

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

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

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

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

3 改進的A*算法代碼描述

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

部分偽代碼如下：

[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 實驗分析

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

結束語

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

參考文獻：

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

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

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

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

[5] 陳素瓊.基于改進A*算法的地圖游戲尋徑研究[J].重慶師范大學學報：自然科學版，2017，34（4）：75-78.

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

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