大规模道路网最短路径算法的研究

发布时间：2021-03-03 23:09

　　随着人口往城市的快速迁移,全球道路网的规模在不断地扩大,高效、快速的从庞大的道路网数据中计算两点之间的最短路径,成为了学术界和工业界众多研发人员的研究课题。经过多年的研究,学者们已经提出了诸多相关算法,例如Dijkstra算法、CH算法（Construction Hierarchies Algorithm）、Arc-Flag算法、Highway Hierarchies算法,以及一些结合智能算法的最短路径算法。但是如何通过减少数据搜索空间,从而达到有效降低查询时间这一问题仍然未能得到良好的解决。本文针对从大规模道路网数据中查询两点之间最短路径存在时间消耗较大的问题,分析研究了实际道路之间的限制关系,提出了一种基于节点度的大规模道路网数据划分方法,在此基础上,给出有效可行的解决方案,同时也保证了算法的性能。论文的主要工作如下:（1）提出了一种基于节点度的道路划分算法,以解决划分道路网数据时容易将节点分布密集的区域划分在不同的子网内的问题。首先,该算法根据实际道路之间的限制关系处理并存储道路网数据;其次,设置划分后的子网内最大节点数量,然后利用Kd-tree划分道路网数据,并标记划分后的子网... 

【文章来源】：四川师范大学四川省

【文章页数】：73 页

【学位级别】：硕士

【部分图文】：

网格划分德克萨斯州的道路网

图 2.5 Quad-tree 划分德克萨斯州道路网-dimensional tree)划分算法是一种根据图中节点在多的算法，其主要思想是：K-D 树每一个非叶子节点都

Kd-tree划分德克萨斯州道路网


本文编号：3062099