呂博 都美曄 李璐君

摘 要 由于A*算法在進(jìn)行啟發(fā)式搜索時(shí)具有較高的算法效率，并且可以基于評(píng)估函數(shù)找到最優(yōu)路徑，本文針對(duì)在大型停車場(chǎng)中尋車?yán)щy的問(wèn)題提出采用A*算法進(jìn)行路線規(guī)劃。文章闡述了A*算法的原理及實(shí)現(xiàn)過(guò)程，并對(duì)停車場(chǎng)進(jìn)行建模，通過(guò)仿真實(shí)驗(yàn)驗(yàn)證了算法應(yīng)用于停車場(chǎng)尋車路徑規(guī)劃的可行性。

關(guān)鍵詞 A*算法；路徑規(guī)劃；停車場(chǎng)

引言

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

1 A*算法原理與實(shí)現(xiàn)

A*算法的原理是借助于開(kāi)啟列表（OpenList）和關(guān)閉列表（ClosedList）兩個(gè)列表，通過(guò)估值函數(shù)來(lái)引導(dǎo)整個(gè)路徑搜索的過(guò)程，快速尋找到一條最短的路徑。其中，開(kāi)啟列表和關(guān)閉列表是 A*算法在尋路搜索的過(guò)程中必須維護(hù)的兩張表。開(kāi)啟列表中存放著即將被訪問(wèn)但未被訪問(wèn)的節(jié)點(diǎn)，同時(shí)這些節(jié)點(diǎn)所對(duì)應(yīng)著的估值值也被存放在該表中；而關(guān)閉列表中則存放著已經(jīng)訪問(wèn)完成的節(jié)點(diǎn)。估值函數(shù)用來(lái)引導(dǎo)尋路，其數(shù)學(xué)表達(dá)式為：

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

其中F（n）為估值函數(shù)；G（n）是已經(jīng)計(jì)算出的從起始點(diǎn)到當(dāng)前路點(diǎn)的實(shí)際路徑長(zhǎng)度；H（n）是估測(cè)從當(dāng)前點(diǎn)到目標(biāo)點(diǎn)路徑長(zhǎng)度的曼哈頓距離。

使用標(biāo)準(zhǔn) A*算法進(jìn)行尋找路徑的流程見(jiàn)圖1。

A*算法需要設(shè)置起始節(jié)點(diǎn)S和目標(biāo)節(jié)點(diǎn)E，并建立兩個(gè)空的List：OpenList 和ClosedList。如圖1所示，在第一次循環(huán)時(shí)，將起始節(jié)點(diǎn)S和相鄰節(jié)點(diǎn)放入 OpenList 中。從第二次循環(huán)開(kāi)始，每次選取OpenList中估值最小的節(jié)點(diǎn)a作為路徑選取的點(diǎn)，把a(bǔ)設(shè)置為父節(jié)點(diǎn)，放入CloseList中并把a(bǔ)的相鄰點(diǎn)加入OpenList中。直到OPenList為空，或a沒(méi)有不在CloseList里的相鄰點(diǎn)，或a為目標(biāo)節(jié)點(diǎn)E時(shí)，循環(huán)結(jié)束。當(dāng)a就是目標(biāo)節(jié)點(diǎn)E時(shí)，路徑規(guī)劃成功，按照父節(jié)點(diǎn)回溯即可得到最短路徑。

2 停車場(chǎng)尋車應(yīng)用

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

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

3 結(jié)束語(yǔ)

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

參考文獻(xiàn)

[1] 陸鋒.最短路徑算法：分類體系與研究進(jìn)展[J].測(cè)繪學(xué)報(bào)，2001，30（3）：269-275.

[2] 付夢(mèng)印，李杰，鄧志紅.限制搜索區(qū)域的距離最短路徑規(guī)劃算法[J].北京理工大學(xué)學(xué)報(bào)，2004，24（10）：881-884.

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