A*算法在室內(nèi)交互式引導中的應用

謝慶+謝攀峰

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

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

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

中圖分類號：TP301.6 文獻標志碼：A 文章編號：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 引言

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

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

1 迪杰斯特拉算法的原理

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

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

4 結(jié)束語

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

參考文獻（References）：

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

二師范學院學報，2008.8：12-14

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

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

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

與發(fā)展，2003.5：335

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

天地，2009.7：122-123

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

上海大學學報（自然科學版），1997.11（3）：67-70