立體空間A*算法在尋找商場室內導航最優路徑中的應用

畢小順

（禾麥科技開發（深圳）有限公司，廣東　深圳　518001）

立體空間A*算法在尋找商場室內導航最優路徑中的應用

畢小順

（禾麥科技開發（深圳）有限公司，廣東深圳518001）

文章研究了用于商場室內路徑規劃導航的算法，對比了各種算法的優缺點，提出了一種優化的A*算法。該算法結合了Dijkstra算法以及廣度優先搜索（Breadth First Search，BFS）算法的優點，同時充分考慮了商場的立體空間結構，并結合了商場通行的大數據，可以給出最有效的商場室內路徑規劃。

室內；路徑規劃；導航；A*算法

1　概述

室內定位技術［1］可以為用戶提供精準的商場定位、導航、導購服務，有利于提高商場的服務質量，提升購物者的購物體驗。通過商場購物引導、線上線下結合，其應用的市場潛力十分巨大。

室內導航服務作為室內定位技術的重要應用，可以為用戶展示其感興趣的商品、門店、停車位等位置的方向、距離，方便用戶抵達目的地，效用明顯。但是在室內導航服務中，單純地提供目的地位置，由用戶自行考慮抵達的路徑，仍不是最佳的服務，有必要通過算法，基于室內定位和商場地圖進行快速的智能路徑規劃導航，為用戶提供更滿意的服務。

2　路徑規劃算法

路徑規劃有很多算法，在導航中，主流的算法就是廣度優先搜索（Breadth First Search，BFS）算法，Dijkstra算法和A*算法。

Dijkstra算法［2］以物體所在的出發點為中心開始訪問地圖中的結點。它迭代檢查待檢查結點集中的結點，并把和該結點最靠近的尚未檢查的結點加入待檢查結點集。該結點集從初始結點向外擴展，直到到達目標結點，是一種擴張式的遍歷方法。Dijkstra算法的優點是一定能獲得最短的路徑，缺點在于其是一種窮舉式算法，對于復雜地圖系統，運算量很大。

BFS算法與Dijkstra算法類似［3］，不同的是它引入了啟發式算法（heuristic algorithm）對每一個搜索位置進行評估，得到最好的位置，再從這個位置進行搜索直到目標。BFS不能保證找到的一定是一條最短路徑。然而，它可以省略大部分無意義的搜索路徑，相比Dijkstra算法運行速度快很多。BFS算法的缺點在于它向目標移動僅僅考慮到達目標的代價，而忽略了當前已消耗的代價，這使得其在復雜情況下會得出錯誤的路徑。

A*算法是BFS和Dijsktra算法的結合，吸取了兩者的優點。和Dijkstra一樣，A*能用于搜索最短路徑，和BFS一樣，A*能用啟發式函數引導它自己，給出當下的最佳解。同時，由于引入了Dijsktra算法的思想，A*算法會也會評估已經走過路徑的代價，以保證找到一條最短路徑。A*算法的估價函數如下式：

f（n）=g（n）+ h（n）

其中g（n）表示從初始結點到任意結點n的代價，h（n）表示應用啟發函數從結點n到目標結點的評估代價。

因此A*算法是進行商場導購路徑規劃的最佳選擇。但是大型商場，均為立體多層空間，其地圖信息更加復雜，需要對A*算法進一步優化以適應多層空間的路徑搜索。

3　立體空間A*算法優化

本文認為，在商場這種多層級的立體空間，應用A*算法，有必要分層開展，逐層尋優，最后匯總評估，來獲得最終的最優路徑。其軟件框圖如圖1所示。首先評估目標地址是否在本層，對于本層的地址，直接應用A*搜索算法即可尋找到最優路徑。對于其他層的地址，首先采用A*搜索算法計算由出發點到不同樓梯口的最優路徑，再繼續采用A*搜索算法計算由目標地址反推到該層各個樓梯口的最優路徑。然后各個對應的樓梯口的路徑對接合成，即形成了經過不同樓梯口抵達目標層目標地址的最優路徑集。

經過不同樓梯口的最優路徑集不能簡單對比路徑長度進行評估。而應該結合其跨越的樓層數，上樓的方式（扶梯式電梯，轎箱式電梯，步行樓梯）以及結合商場的大數據分析評估不同上樓方式占用的時間，以便給出精確可靠的評估結果，包括：最短路徑，最省時間路徑，最輕松路徑等，給用戶提供最精確可靠的評估結果。

4　結語

大型商場結構復雜，路徑繁多，面積龐大。傳統的導購圖，指示牌等由于傳播能力有限，導航效果不佳，有必要借助現代信息技術和手機等智能終端的結合為大型商場的客人提供更高效的路徑規劃導航。本文提出了采用優化的A*算法在商場等大型多樓層立體空間的路徑規劃算法。為大型商場或建筑物提供路徑規劃導航算法提供了可行的方案。

圖1　算法框圖

［1］汪苑，林錦國.幾種常用室內定位技術的探討［J］.中國儀器儀表，2011（2）：54-57.

［2］楊劉翔.Dijkstra算法在物流配送中的應用研究［J］.電子世界，2014（12）：209-209.

［3］李辰寅，徐健，張淑梅，等.立體停車庫調度算法的研究與實現［J］.蘇州科技學院學報（工程技術版），2008（1）：63-66.

Application of three-dimensional space A* algorithm for fnding the optimal path in shopping mall indoor navigation

Bi Xiaoshun
（Roy Mark Technology Development（Shen Zhen）Co.， Ltd.， Shenzhen 518001， China）

This paper studied the algorithm of indoor path planning and navigation in shopping mall and compared with the advantages and disadvantages of various navigation algorithms. This paper proposed an optimized A* algorithm which combined with the advantage of both Dijkstra algorithm and breadth frst search（BFS）algorithm， and fully considered the three-dimensional structures and the big data of shopping mall. It can give the most effective indoor path planning for shopping malls.

indoor； path planning； navigation； A* algorithm

畢小順（1979— ），男，江西臨川，本科，中級職稱；研究方向：計算機軟件及應用。