A算法在停車場尋車路徑規劃中的應用研究

呂博 都美曄 李璐君

摘 要 由于A*算法在進行啟發式搜索時具有較高的算法效率，并且可以基于評估函數找到最優路徑，本文針對在大型停車場中尋車困難的問題提出采用A*算法進行路線規劃。文章闡述了A*算法的原理及實現過程，并對停車場進行建模，通過仿真實驗驗證了算法應用于停車場尋車路徑規劃的可行性。

關鍵詞 A*算法；路徑規劃；停車場

引言

隨著經濟的發展，中國汽車保有量及市場規模逐年增長。為滿足人們停車的需求，住宅區及大型商場的停車場面積增大、層數增加，提供大量車位的同時對用戶尋車也造成了一定困難。僅靠車位編號尋找車輛的方法效率較低，因此建立停車場尋車系統幫助用戶尋找車輛位置，規劃尋車路線十分重要。最短路徑算法是計算機科學、人工智能科學等研究的熱點問題[1]。兩點間的所有路徑中，一定有一條最佳的路徑使時間和效率均為最優，這時就需要使用限制搜索區域內的最短路徑算法[2]。其中，A*算法由于其性能和準確性被廣泛使用[3]。

1 A*算法原理與實現

A*算法的原理是借助于開啟列表（OpenList）和關閉列表（ClosedList）兩個列表，通過估值函數來引導整個路徑搜索的過程，快速尋找到一條最短的路徑。其中，開啟列表和關閉列表是 A*算法在尋路搜索的過程中必須維護的兩張表。開啟列表中存放著即將被訪問但未被訪問的節點，同時這些節點所對應著的估值值也被存放在該表中；而關閉列表中則存放著已經訪問完成的節點。估值函數用來引導尋路，其數學表達式為：

F（n）=G（n） +H（n） （1）

其中F（n）為估值函數；G（n）是已經計算出的從起始點到當前路點的實際路徑長度；H（n）是估測從當前點到目標點路徑長度的曼哈頓距離。

使用標準 A*算法進行尋找路徑的流程見圖1。

A*算法需要設置起始節點S和目標節點E，并建立兩個空的List：OpenList 和ClosedList。如圖1所示，在第一次循環時，將起始節點S和相鄰節點放入 OpenList 中。從第二次循環開始，每次選取OpenList中估值最小的節點a作為路徑選取的點，把a設置為父節點，放入CloseList中并把a的相鄰點加入OpenList中。直到OPenList為空，或a沒有不在CloseList里的相鄰點，或a為目標節點E時，循環結束。當a就是目標節點E時，路徑規劃成功，按照父節點回溯即可得到最短路徑。

2 停車場尋車應用

在停車場尋車場景下，使用A*算法進行路徑規劃，在人員和車輛之間規劃一條最短路徑，首先需要建立停車場模型，如圖2所示。其中B表示停車場的邊界，O表示停車位，*表示停車場中的道路，S表示起始點即人員所在的位置，E表示終點即車輛所在位置。

使用A*算法尋找從S點到E點的最短路徑，并將最終的路徑用P表示。最終結果如圖3所示。

3 結束語

本文介紹了A*算法并將其應用在停車場尋車路徑規劃中，能夠幫助停車場為車主提供更便捷的服務。

參考文獻

[1] 陸鋒.最短路徑算法：分類體系與研究進展[J].測繪學報，2001，30（3）：269-275.

[2] 付夢印，李杰，鄧志紅.限制搜索區域的距離最短路徑規劃算法[J].北京理工大學學報，2004，24（10）：881-884.

[3] 郝振國，王玉玫.雙向A*算法在軍事路徑規劃中的應用[J].計算機工程與應用，2011，47（29）：246-248.