謝慶+謝攀峰

DOI：10.16644/j.cnki.cn33-1094/tp.2016.09.016

摘 要： Dijkstra算法是公認(rèn)的求解最短路徑問(wèn)題的經(jīng)典算法之一，A*算法是最優(yōu)的啟發(fā)式搜索算法。比較Dijkstra算法和A*算法在求解最短路徑問(wèn)題上的優(yōu)點(diǎn)和缺點(diǎn)，結(jié)合大型公共場(chǎng)所實(shí)際情況，采用A*算法來(lái)解決室內(nèi)交互式引導(dǎo)系統(tǒng)的路徑搜尋，從而減少算法搜索的規(guī)模。

關(guān)鍵詞： 室內(nèi)交互式引導(dǎo)； 最短路徑； Dijkstra算法； A*算法

中圖分類(lèi)號(hào)：TP301.6 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1006-8228（2016）09-59-04

Application of A* algorithm in indoor interactive guidance

Xie Qing， Xie Panfeng

（Hubei University of Arts and Science， School of Mathematics and Computer Science， Xiangyang， Hubei 441053， China）

Abstract： Dijkstra algorithm is recognized as one of the classic algorithm of solving the shortest path problem， and A* algorithm is the best heuristic search algorithm. Comparing Dijkstra algorithm and A* algorithm of advantages and disadvantages in solving the shortest path problem， combining with the actual situation of large public place， A* algorithm is used to solve the path search for indoor interactive guidance system， thereby reducing the scale of the algorithm searching.

Key words： indoor interactive guidance； shortest path； Dijkstra algorithm； A* algorithm

0 引言

隨著手機(jī)的普及，手機(jī)地圖成為不可或缺的APP，目前，它針對(duì)公交等形式的APP開(kāi)發(fā)較多，而對(duì)于人群集中的室內(nèi)大型公共場(chǎng)所的APP開(kāi)發(fā)較少。

從現(xiàn)有的智能導(dǎo)航來(lái)看，GPS導(dǎo)航適用于室外，它的特點(diǎn)是距離較遠(yuǎn)導(dǎo)航空間較大；高德地圖等基于移動(dòng)設(shè)備的導(dǎo)航也適用于廣泛區(qū)域，因此，缺乏對(duì)小距離（室內(nèi)）的搜索定位。室內(nèi)交互式引導(dǎo)APP的主要研究對(duì)象是人群密集的大型公共場(chǎng)所，它是一種小范圍導(dǎo)航，例如機(jī)場(chǎng)，火車(chē)站等，適用于個(gè)人外出尋找最短路徑。室內(nèi)交互式引導(dǎo)APP的最短路徑的研究方面，可以比較Dijkstra算法和A*算法。Dijkstra算法的應(yīng)用是比較廣泛的，如將Dijkstra算法應(yīng)用于地理信息系統(tǒng)的建設(shè)[5]。A*算法的應(yīng)用也存在各個(gè)方面，如將A*算法應(yīng)用于人工智能[3]。此外，A*算法在人工智能，計(jì)算機(jī)網(wǎng)絡(luò)路由算法等方面有著非常廣泛的應(yīng)用[4]。

1 迪杰斯特拉算法的原理

1.1 迪杰斯特拉算法的基本原理

傳統(tǒng)Dijkstra算法，也稱(chēng)為最短路徑算法或正向搜索算法，是一種集中式的靜態(tài)算法[1]，用于求單源點(diǎn)最短路徑問(wèn)題。其基本思想：設(shè)置有向圖G=（V，S），集合S存放已經(jīng)找到最短路徑的頂點(diǎn)，S的初始狀態(tài)只包含源點(diǎn)v，集合V存放未被找到的節(jié)點(diǎn)，vi∈V-S，從源點(diǎn)v到其他每個(gè)頂點(diǎn)vi的有向邊為最短路徑長(zhǎng)度dist[i]。初始狀態(tài)dist[0]=0，選取集合V中距離v最短的路徑的頂點(diǎn)vk，將vk加入集合S中，重新計(jì)算源點(diǎn)v到vk的最短路徑，以vk為重新的中間點(diǎn)，再次選取集合V中的點(diǎn)，取得路徑長(zhǎng)度較小者為當(dāng)前最短路徑，直到將集合V中的點(diǎn)全部放入集合S中，求得最短路徑。

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

就目前來(lái)看，針對(duì)于室內(nèi)交互引導(dǎo)（小范圍）的路徑搜索較少，大多數(shù)路徑搜索算法是基于移動(dòng)設(shè)備的APP，汽車(chē)導(dǎo)航等大范圍的路徑查詢(xún)。將A*算法作為室內(nèi)交互式引導(dǎo)APP設(shè)計(jì)中，最短路徑算法采用啟發(fā)式的A*算法，利用估價(jià)函數(shù)對(duì)最短路徑進(jìn)行估算。A*算法的搜索具有方向性和目的性等特點(diǎn)，因此相比于傳統(tǒng)的Dijkstar算法在室內(nèi)交互式的應(yīng)用可以大大減少搜索的范圍，提高搜索的效率。A*算法也是被游戲開(kāi)發(fā)人員廣泛使用的人工智能尋路算法，并且，通過(guò)引入對(duì)人群密度的檢測(cè)，考慮對(duì)A*算法進(jìn)一步改進(jìn)，以避開(kāi)密集人群為目的，將其應(yīng)用于緊急救災(zāi)等方面。在針對(duì)存在多個(gè)最短路徑時(shí)，A*算法尋找最優(yōu)最短路徑的問(wèn)題還需要進(jìn)一步研究和改進(jìn)。

參考文獻(xiàn)（References）：

[1] 王戰(zhàn)紅，孫明明，姚瑤.Dijkstra算法的分析與改進(jìn)[J].湖北第

二師范學(xué)院學(xué)報(bào)，2008.8：12-14

[2] 李擎，宋頂立，張雙江，李哲，劉建光，王志良.兩種改進(jìn)的最優(yōu)

路徑規(guī)劃算法[J].北京科技大學(xué)學(xué)報(bào)，2005.3：367-370

[3] 樊莉，孫繼銀，王勇.人工智能中的A*算法應(yīng)用及編程[J].微機(jī)

與發(fā)展，2003.5：335

[4] 黃蓉，劉敏.基于A*算法求解最短路徑的實(shí)現(xiàn)原理[J].企業(yè)家

天地，2009.7：122-123

[5] 宋巨川，李軍，張文俊.地理信息系統(tǒng)中建立最短路徑的算法[J].

上海大學(xué)學(xué)報(bào)（自然科學(xué)版），1997.11（3）：67-70