交通运输网络的二叉堆索引及路径算法优化

发布时间：2021-04-27 19:37

　　交通运输网络的最短路径分析是地理信息系统网络分析最常见的应用之一.该文在二叉堆索引结构的基础上改进了计算最短路径的Dijkstra算法和A*算法,采用了多种优化策略提高算法的运行效率.首先,应用二叉堆索引提高了交通运输网络存储结构的读取效率;其次,通过数据类型的低精度损耗简化和运算类型的简化,提高了算法的计算效率.另外,优化了A*算法中估计函数的计算方式,有效降低了搜索空间,提高了Dijkstra算法和A*算法的整体计算效率.实验结果表明Dijkstra算法的改进方法可使计算速度提高7倍以上,对A*算法的改进可使计算速度提高200倍以上. 

【文章来源】：应用科学学报. 2020,38(06)北大核心CSCD

【文章页数】：11 页

【文章目录】：
1 交通运输网络的二叉堆数据结构表示和算法改进
    1.1 交通运输网络的最短路径算法分析
        1.1.1 Dijkstra算法
        1.1.2 A*算法
    1.2 交通运输网络的二叉堆索引结构
    1.3 基于二叉堆的Dijkstra改进算法
    1.4 基于二叉堆的A*改进算法
2 实验与分析
    2.1 实验环境及数据
    2.2 实验结果与分析
3 结语


【参考文献】：
期刊论文
[1]基于不同交通工具多约束条件的最短路径算法研究[J]. 范林林,李翔,张晶,张江水,赵婷.  测绘工程. 2016(12)
[2]一种并行模糊神经网络最短路径算法[J]. 闫春望,黄玮,王劲松.  计算机应用研究. 2016(11)
[3]大数据环境下的动态最短路径算法[J]. 徐建闽,王钰,林培群.  华南理工大学学报(自然科学版). 2015(10)
[4]道路网上最短路径算法综述[J]. 张波良,张瑞昌,关佶红.  计算机应用与软件. 2014(10)
[5]基于Dijkstra算法和Floyd算法的物流运输最短路径研究[J]. 李晶,闫军.  科技信息. 2012(34)
[6]改进的Dijkstra最短路径算法及其应用研究[J]. 王树西,吴政学.  计算机科学. 2012(05)
[7]基于Bellman-Ford算法的动态最优路径算法设计[J]. 宫恩超,李鲁群.  测绘通报. 2011(08)
[8]改进的最短路径搜索A*算法的高效实现[J]. 段莉琼,朱建军,王庆社,马玲.  海洋测绘. 2004(05)
[9]最短路径算法:分类体系与研究进展[J]. 陆锋.  测绘学报. 2001(03)
[10]Dijkstra最短路径算法的一种高效率实现[J]. 乐阳,龚健雅.  武汉测绘科技大学学报. 1999(03)



本文编号：3164043