论文部分内容阅读
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
摘 要： 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