立体空间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— ），男，江西临川，本科，中级职称；研究方向：计算机软件及应用。