A*算法在室內交互式引導中的應用

謝慶+謝攀峰

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

摘 要： Dijkstra算法是公認的求解最短路徑問題的經典算法之一，A*算法是最優的啟發式搜索算法。比較Dijkstra算法和A*算法在求解最短路徑問題上的優點和缺點，結合大型公共場所實際情況，采用A*算法來解決室內交互式引導系統的路徑搜尋，從而減少算法搜索的規模。

關鍵詞： 室內交互式引導； 最短路徑； 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開發較多，而對于人群集中的室內大型公共場所的APP開發較少。

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

1 迪杰斯特拉算法的原理

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

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

4 結束語

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

參考文獻（References）：

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

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

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

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

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

與發展，2003.5：335

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

天地，2009.7：122-123

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

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