基于改进Dijkstra算法的自驾游最优路径规划研究

发布时间：2021-02-25 08:12

　　自驾游时,由于时间有限且旅游景点较多,因此游客要想在最短的时间内游览更多的景点,就需要预先规划好外出旅游的最优路径。目前常用的地图导航软件一般只提供从游客位置到单个旅游景点之间的最优路径,并不能规划多个旅游景点间的最优路径。针对上述问题,该文对Dijkstra最短路径算法进行了改进,在算法中加入了指导函数h,实现了多个景点间最优路径的计算。最后该文以河南省部分代表性景点为例,采用改进后的Dijkstra算法,成功实现了多景点间最优路径的规划,验证了该算法的科学性和实用性。 

【文章来源】：科学技术创新. 2020,(17)

【文章页数】：3 页

【部分图文】：

采用贪婪思想的Dijkstra算法

1.4.3 在计算s到C中每个约束点的距离时，会生成以s为根的最短路树，从这棵树中，可直接取到Dijkstra(s,x,G）的结果。如果想取到Dijkstra(s,x,G-C+x）的结果，可修改生成最短路树的过程，使其遇到约束点时不再生长，即约束点必须是最短路树的叶节点[10]。加入贪婪思想的Dijkstra算法虽能提高算法效率，但在很多情况下计算效果并不理想，如图1所示，在计算s到t的路径过程中，加入贪婪思想的Dijkstra算法会按照黑线顺序来穷举约束节点，这样很容易计算失败。相反，如果按红线顺序穷举约束节点，成功率就会提高很多。图3 河南自驾游最优路线

河南自驾游最优路线

【参考文献】：
期刊论文
[1]具有交通规则约束的改进Dijkstra算法[J]. 任鹏飞,秦贵和,董劲男,李滨,郑啸天.  计算机应用. 2015(09)
[2]西安秦岭自驾游旅游服务质量评价研究[J]. 刘军胜,马耀峰.  干旱区资源与环境. 2014(12)
[3]自驾游:兴起、演化与产业机会探析[J]. 马聪玲.  贵州社会科学. 2014(11)
[4]基于结构方程模型的自驾游客满意度研究[J]. 史春云,孙勇,张宏磊,刘泽华,林杰.  地理研究. 2014(04)
[5]Dijkstra算法与旅游路径优化[J]. 樊守伟,严艳,张少杰,田泽民.  西安邮电大学学报. 2014(01)
[6]Dijkstra算法优化及在GIS系统中求最佳路径的应用[J]. 苏宝莉,李宁.  遥感技术与应用. 2013(05)
[7]旅游体验与个人变化:一个分析的框架[J]. 余志远.  旅游科学. 2012(05)
[8]改进Dijkstra算法在GIS导航应用中最短路径搜索研究[J]. 董俊,黄传河.  计算机科学. 2012(10)
[9]基于Dijkstra算法改进的海量数据最优路径计算方法研究与实现[J]. 王兆南.  测绘通报. 2012(09)

硕士论文
[1]基于智慧旅游的昆明市自驾游游客决策过程研究[D]. 张冬.云南大学 2015



本文编号：3050700