基于大数据分析的城市交通网最短路径算法设计

发布时间：2020-08-09 07:12

【摘要】：最短路径问题是图论中较为经典也是相对基础的问题,其经过了大半个世纪的研究,受到许多领域研究人员的关注,最短路径算法的研究成果十分丰富。最短路径算法广泛运用在各种现实场景中,其中交通网中选取最优出行路径就是最短路径算法的一项具体应用。随着城市的发展,城市交通网的规模逐渐扩大,网络节点数量庞大且网络结构复杂多元,使得经典最短路径算法无法使用,因此,应用于大规模网络中最短路径的优化技术和优化算法成为近几年最短路径算法研究的重点。在这些研究中,并行计算成为大规模网络最短路径算法的主要研究方向。近几年,国内外学者针对大规模网络和动态网络提出了一系列最短路径算法,其中部分算法使用了启发式路径搜索方式、并行计算方式或使用网络分层模型进行最短路径计算。本文在现有的研究成果中总结出相关经验,综合了并行计算思想和启发式搜索方式,提出了一个适合于城市交通网任意节点间最短路径计算的层次最短路径算法。本算法主要由三个子算法组成,分别是大图分解过程、PFloyd算法和SPS算法。由于最短路径计算的时间复杂度与图中节点个数相关,因此,在图分解过程中,我们设计了一个两层网络模型,即将原始网络分割为若干个子网,再将子网抽象为节点并构造二层网络。当路径查询的起点与终点同属于一个子图时,本文设计了并行的任意节点间最短路径算法PFloyd算法,该算法根据任意节点间最短路径计算迭代公式与矩阵乘法运算公式之间的映射关系,将任意节点间最短路径计算移植至MapReduce上,通过MapReduce的′?次矩阵迭代相乘,计算出最短路径的权值矩阵和路径矩阵,算法通过对权值矩阵和路径矩阵的查询得到所求的最短路径。当路径查询的起点与终点属于不同的子图时,本文设计了一个跨子图的路径搜索算法SPS算法。SPS算法采用了启发式的搜索模式以构建路径,它定义了子图间的距离计算方式,并将子图间距离信息作为启发式的引导信息,在当前访问子图的邻接子图中,递归选取若干个与当前子图相近的子图作为下一次访问的子图对象。SPS算法采用双向搜索模式,前向搜索与后向搜索同步进行,使得前向搜索与后向搜索的对象快速逼近,从而实现搜索算法的加速。通过对参数的调整,可以提升路径搜索的精确度,减少路径搜索的时间。当路径构建完成后,只需挑选出所有路径中最短的那条即为SPS算法所求。文中选取美国旧金山港湾区交通网路径数据作为本文实验数据,对层次最短路径算法进行实验分析,验证了算法的可用性。本文的层次最短路径算法在层次网络模型中进行,三个子算法共同配合,完成了算法在子图层与二层网络中的路径搜索与路径拼接。二层网络中的路径搜索采用双向的启发式路径搜索模式,加快了算法的搜索效率。针对交通网路段的权值根据时间动态变化的问题,算法在图分解过程中将原始网络进行切分,使得路段权值以子图为单位动态更新,减少了权值更新带来的额外消耗。通过实验结果,证明了本文算法在大规模交通网最短路径计算中有良好表现。
【学位授予单位】：江西财经大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：TP301.6
【图文】：

最短路径算法,图分解,大规模网络,算法

图 1-1 本文组织架构一章为绪论。介绍了本文研究背景及研究意义，首先详细介绍经典以及其改进方法；其次讨论经典算法不适合处理大规模网络的原因大规模网络中最短路径算法的国内外研究现状，列举出算法的研究介绍国内外在并行计算方面的研究成果；最后概括了本文的主要研文的结构安排。二章为预备知识分析。在提出本文算法前，将读者需要了解的预备。首先介绍本算法中图的存储结构以及 HDFS 的基础架构；其educe 计算模型，并使用它计算两个二维矩阵相乘；最后介绍动态数以及动态数据获取所用到的工具。三章为层次最短路径算法设计。介绍了一个层次最短路径算法，该子算法，分别是图分解过程、PFloyd 算法和 SPS 算法。图分解过进行切分、分层，并抽象得到二层网络。根据路径查询的起点与终

无向图,无向图,最短路径算法,交通网

和边的数量庞大，存储交通网数据直接关系到最短路径算法的执行效目前，常见的简单图存储结构主要分组成，存储图中节点数据的一二维数组二维（n 为图中节，以图 2-1 中的无向图为例（图中，0 11 01 10 10 0Arcs

无向图,邻接表,存储结构

据分析的城市交通网最短路径算法设计接矩阵存储结构可以看出，邻接矩阵存储可以快速查找两个节点之其最大的缺点是无关联的节点也需要占用存储空间，这会消耗大量]。表的存储逻辑是将每个节点的邻接节点串联，并以单链表的形式-1 中无向图，邻接表的存储结构如图 2-2 所示。

【参考文献】