1、 毕 业 设 计中文题目 基于随机点集最短路径算法的研究与实现英文题目 The Research and Implementation of the Shortest Path Algorithm Based on the Stochastic Set院 系： 计算机与信息工程学院年级专业： 金融服务 姓 名：学 号：指导教师：职 称： 年 月摘要I摘 要最短路径的研究属于网络优化领域，它也是图论的重要内容，涉及现实生活诸多方面。该算法可应用于交通规划、旅游安排、城市建设等，至今仍然是业界研究热点。本文着重研究的是图网中任意若干顶点之间的最短路径最优规划。本课题通过使用 matlab 实现 4
2、 个经典的 随机最短路径派生算法， 并将其应用在纽约等 6 个城市路网数据集上，进行随机规划最优最短路径的模拟，来研究算法各项性能指标，对比其优劣。案例研究结果表明，本课题所采用的算法，大幅度减少了冗余节点，减轻了复杂度的操作，提高了算法的性能和效率，并且确保课精确度。该算法可以有效应用在多种路径规划类现实应用中，提高工作效率。关键词：最短路径；网络规划ABSTRACTIIABSTRACTShortest patch belongs to network optimization, also the important content in graph theory. It is widely
3、 used in different fields in the real life. At present, these research theories can be used in application fields such as traffic planning, tourism arrangement, urban construction and so on. The shortest path algorithm is still a hot research topic now.The paper will study the randomly processed fou
4、r modern classical derived shortest path algorithms in urban road network dataset respectively. The subject will analyze the impact of these four algorithms on different performance. And applies these algorithms in New York City road network data set, data sets are six such cities. For the simulatio
5、n of stochastic programming optimal shortest path algorithm to research the performance indexes, compared the advantages and disadvantages.Case study results show that this topic by the algorithm, greatly reduces the redundant nodes and reduces the complexity of the operation, Not only the performan
6、ce and efficiency of this algorithm is improved, and to ensure accuracy. The algorithm can be effectively applied in a variety of path planning in the practical application, improve the work efficiency.Key Words: shortest patch; network optimization目录 III目 录第 1 章 引言 .11.1 课题研究背景及意义 .11.2 本文的研究内容 .1第
7、 2 章 最短路径问题与随机概念 .32.1 最短路径概述 .32.1.1 最短路径研究发展历史 .42.1.2 国内外研究现状 .52.2 图的相关定义 .62.2.1 图 .62.2.2 赋权图 .72.2.3 无向图和有向图 .72.2.4 顶点的度数 .72.2.5 路径 .72.2.6 随机定义 .72.3 本章小结 .8第 3 章 求解最短路径的相关算法 .93.1 Dijkstra 算法 .93.2 Floyd 算法 .113.3 SPFA 算法 .113.4 Bellman-Ford 算法 .133.5 本章小结 .16第 4 章 随机最短路径的矩阵算法 .174.1 问题引出
8、 .174.2 相关描述 .174.3 算法原理 .184.4 算法思想 .184.5 实验及性能分析 .194.5.1 单源点最短路径算法实验 .194.5.2 全源最短路径算法实验 .224.6 可行性分析 .234.7 算法实例 .234.8 本章小结 .27第 5 章 随机点的最短路径算法应用 .285.1 真实模型假设 .285.2 问题分析 .295.3 问题求解 .295.4 本章小结 .30第 6 章 总结与展望 .316.1 总结 .316.2 展望 .31参考文献 .33致谢 .35第 1 章 引言1第 1 章 引言1.1 课题研究背景及意义最短路径问题不仅是业界研究的重点
9、在国内外仍然占有重要地位。应用在但不仅限于：地理测绘、图形图像、地质勘探、交通规划、以及一些网络信息系统的规划和信息网络的铺设。不仅如此，许多生产实践类的问题仍可通过建模转换为建立在图网中的问题，每个系统各自特点及性能可通过参数及相关权值的设计来实现。本文主要研究在智能交通领域中的最短路径算法，将先进的计算机处理技术、信息技术、数据通讯传输技术、传感器技术及电子自控科技等有效地综合起来，这样就把人、路、车以及环境有机地结合在一起，实现效果最佳的控制，从而研究出适应于较大范围内、全方位发挥作用的性能最佳的最短路径规划方案 1。最短路径算法是分配社会能源、规划与分析线路等改进问题的理论基础，在道路
10、网络结构的研究、城市交通路线的确定、通信线路的搭建与维护、交通运输的最小耗费分析等均具有直接应用的价值 2。最短路径问题在理论研究还会以及生产实践领域中是长期研究的话题，仅贯穿于基本的计算机科学、运筹学、地理测绘科学等学科领域也是炙手可热。如此这般，即也对大规模网络模型应用行之广泛提出了新的需求，减少时长、提高精确度成为了目前工作者们主要研究的方向 3。最短路径问题不只是地理角度的路径最短，也可引申到其他的权值，例如时间、费用、容量等等，这样，最短路径就可以看作为最快路径、最低花费等问题。其研究便可以延伸开来。1.2 本文的研究内容本文首先介绍了四种比较成熟经典的最短路径算法，然后详述了实际城
11、市路网的交通数据信息的预处理过程，提出了最短路径算法在不同数据集上的运行特点，提出来了在区域搜索策略方面所做的优化与改进之处，最后进行了实验验证。本文的研究目的是对城市交通数据进行预处理后，最大程度地减少最短路径算法的占用空间与时间复杂度。实验分析中对每种算法都给出了数据集分析，时间复杂度分析，可行性分析，以及综合性能分析。实验效果基于是否能够切实可行的应用在社会生产实践，比较了算法在不同环境下的性能和优缺点，最后得出在何种数据集上应使用具有何种指标的最短路径算法，以及总结了在不同的情况下应该使用何种算法提高效率。通过第 1 章 引言2实验，得出结论与目前先进的城市规划算法发展趋势如出一辙。本
12、文分为六个章节：第一章：绪论，先给出了本课题的研究背景与研究意义，之后阐述了最短路径算法的研究历史与研究现状，最后说明了本文的主要研究内容。第二章：本文的理论。介绍自上世纪 60 年代以来最短路径算法的研究和发展历史，主要说明了路网中较为成熟的四种最短路径算法与搜索算法，重点研究了 Dijkstra 算法的思想原理，并说明了传统的 Dijkstra 算法存在的缺陷，在理论方面对经典算法以及衍生最短路径算法原理进行阐述并给出本次课题研究的随机的概念。第三章：本文的方法基础。介绍四种需要研究的最短路径的原理和各自的伪代码示意图，分析每个算法解决的问题领域以及性能指标上的特点，为后续实验做准备。第四
13、章：在真实数据集上进行最短路径算法实验，通过使用不同数据集在同一算法上进行实验观察同一算法在时间复杂度，性能压力以及准确性上的指标变化情况；同样使用相同数据集在不同算法上实验得出最适合某种社会网络模型的最短路径算法。第五章：承上一章对于最短路径算法的实验设计以及实验目的，在本章中主要体现所有实验的详细流程及所有的实验结果，并且在实验结果原始数据的基础上进行各项指标的分析，从数据分析中得出最短路径算法的相关适合领域。详述本次实验的五种最短路径算法适合应用的不同社会生产领域，以及在目前炙手可热的滴滴打车等使用随机点的交通规划类系统中有待提升的最短路径规划算法。第六章：总结与展望。提出了三个创新点，
14、对以后的研究规划了两点展望。基于对上述五个章节所描述以及实验的完备程度做出一个系统客观的总结，基于此指出后续仍然有待改进的地方，为今后继续研究此课题的同学们一个思维上的借鉴，作为以后理论研究位置奋斗的目标。同时我也会在文末公布出本次实验的所有原始数据集，为以后进一步研究的同学留有研究基础。第 2 章 最短路径问题与随机概念3第 2 章 最短路径问题与随机概念在现实世界和自然界中都不乏看到诸如此类现象：问题本身描述使用非语言文字类沟通方式表示，而使用图形图像的方法来表示。这种符号与标识符号的表示方法不仅形象直观，而且用于表述问题更加简单易懂，跨越了语言与文字的障碍，可以很快的达成共识。最短路径问
15、题不仅是图论和算法设计等理论研究中的经典问题，也是许多应用行业中重要的问题。根据求解对象的不同，最短路径一般可以分为：单源最短路径、点到点的最短路径、多源点到多汇点的最短路径和全源最短路径问题。最短路径算法在现实世界的诸多行业领域中有着广泛的应用。例如：在行程规划、物流规划、交通模拟、行车导航、生物医学、社交网络以及基于位置的各类相关服务（Location-Based Service）中，最短路径问题都是一个非常重要的子问题。在这些系统中，都需要大量、快速、实时地计算某些点到其他一些点的最短路径。近年来，在路径规划等应用的驱动下，最短路径算法，特别是点到点的最短路径算法的研究取得了突飞猛进的发
16、展。学术界提出了许多高效的算法，已经大大提高了静态图（图的结构不会发生变化）上的最短路径算法的性能。但是，现在有的最短路径算法仍然面临一些严峻的挑战。2.1 最短路径概述有向图或无向图中一个典型的问题就是最短路径问题（Shortest Path Problem） 。最短路径问题需要求解的是：如果从图中某一顶点（称为源点）到达另一顶点（称为汇点）的路径可能不止一条，如何找到一条路径，使得沿此路径各边上的权值总和（即从源点到汇点的距离）达到最小，这条路径即为最短路径。全源最短路径虽然在近代研究中热度不减，目前已经研究出来的各种基于经典最短路径算法的各种衍生算法能够真正使用在社会生产领域中的很少，故
17、此类问题今后仍有很大的研究空间。一般情况下，最短路径问题可分为以下 4 种情形 4：（1） 求单源最短路径（边的权值非负）Dijkstra 算法，所谓单源最短路径（Single Source Shortest Path）就是固定一个顶点，将此顶点当作源点，求源点到其他各个顶点的最短路径。 （2） 求单源最短路径（边的权值可以为负值，但不存在负权值的回路）Bellman-Ford 算法。同上，求某个顶点到其余各定点的最短路径，不过对边的权值要求放宽，即可为正，也可为负。 第 2 章 最短路径问题与随机概念4（3） Bellman-Ford 算法的改进SPFA 算法，不可求解带负回路的网络的最短路
18、径。 （4） 求所有顶点之间的最短路径（边的权值允许为负值，但不存在负权值的回路）Floyd 算法。所谓所有顶点间的最短路径就是不固定源点，求对网络图中的任意两个顶点之间的最短路径。最短路径问题的求解算法有很多种，不仅仅限于上述四种算法，如早期基于限制条件的深度优先搜索算法，基于有向无环图的动态规划法，基于邻接表的 A*算法，最大相关边算法等，针对不同的网络图特征、具体的软硬件环境以及应用需求、算法复杂度等方面，采用不同的最短路径算法进行实现。接下来主要介绍上述四种算法，同时注意一点，这四种最短路径算法既可以适用于有向网络图，也可以适用于无向网络图。2.1.1 最短路径研究发展历史90 年代中
19、期，随着 Dijkstra 第一次提出了求解最短路径的概念后人们开始继续深入的在各个领域研究该算法。该算法的特点是通过遍历求到最短路径但是在大规模的图网中计算速度却不尽人意。后续海斯在前人基础上针对单源最短路径算法在遍历全部节点的性质，总结出解决含有负权的图的最短路问题。弱化了原有单源最短路径下的条件，在理论阶段有了较大的提升，但是这种情况在现实社会中却很少遇到，所以站在现实社会的角度上还是没有实质性的解决迫切的问题。 上世纪 60 年代，业界创新提出了 算法， 算法近几年被广泛的使用在了人A工智能化领域，在一些现实路径的优化方面通过启发函数进行智能化处理，进而进行评估，评估对已经求到的函数中
20、选择最优的一个作为最短路径。 算法的核心是A使用一个估价函数： 其中等号右部由两个部分组成 1） ：从()()fnghn ()gn起始顶点到达当前顶点的耗费；2） ：代表当前顶点与目标顶点间的耗费估值，这部分内容最为重要，评估函数需要满足 （ ：实际问题的代价值） 。()hn()在使用这个函数之前需要我们事先检查两件事情：(1) 单调递增。(2) f。当 时直接利用数据结构中对二叉树的深度遍历的方法进行遍()hn()0gn历。当 时类似的使用上面研究的对二叉树的广度优先遍历的方法来进行计算。请注意当我们遇到这样的问题： 时上面的式子实际上就可以认为成 ，()0hn()gn然后我们只要对 进行求
21、解就好了，这样就回归到了最初的问题。由之前的论证()可知， 算法在计算时间上比其遍历搜索的速度更快，但准确率无法保证，只能近A似的得出一个大概的结果。根据鲁迅先生说过的一句话：世界上本没有路，走得多了便有路了。同样的道理体现在蚁群算法中，同一条路走的次数多了，那么则该系第 2 章 最短路径问题与随机概念5统处理后续数据也越准确、快速、智能化。我们处理问题时一般都是通过将现实问题抽象为图网问题，将图网中各节点以及边上的权值信息记录在邻接矩阵或者邻接表中来作为算法计算的初始数据集。通过以上的模型转换直接在数据集上进行算法的计算就可以得到目标结果，本次研究的目标是计算过程中的准确度、时间复杂度等各种
22、性能方面的指标。站在现实社会角度判定一个算法的质量。2.1.2 国内外研究现状最短路径问题不仅仅是图论（Graph Theory ）的关键基础，还在交通信息系统、通讯系统、物流系统、计算机技术等方面的研究关键 5。最短路径问题，旨在寻找图中一对结点之间的最短路径。图中一个结点（起始结点）到达另一个结点（目标结点）的路径有可能存在多条，最短路径问题就是确定一条路径使这一条路径上每一条边的权值之和最小。最短路径算法在实际生活中的很多领域范围内应用非常普遍。比如，在车辆路径确定、物流运输优化、车辆导航和在位置相关基础上的服务中，最短路径均是关键的研究重点之一 6。1959 年，著名的荷兰科学家 E.
23、 W. Dijkstra 提出了最为经典的 Dijkstra 算法 7，此算法旨在寻找到从一个确定的起始结点到图中其他结点的最短路径。随后，斯坦福大学教授 R. W. Floyd 提出了应用广泛的 Floyd 算法 8，此算法旨在寻找到图中全部结点对之间的最短路径。现已有非常多的文献对处于情况不相同的前提下的最短路径问题进行研究，常用的路径规划方法有：最短路径搜索算法 9，蚁群智能算法 10，启发式和 Dijkstra 算法等 11。这些算法在空间复杂度、时间复杂度、适用性与可靠性等方面都各具优势 12，通常最受业界学者认可并且最为常用和成熟的是 Dijkstra 算法。随着现代计算机技术的不
24、断进步，最短路径算法在交通道路网络、通讯系统等方面使用非常广泛。从最开始的广度或深度优先搜索算法，到之后发展起来的 Dijkstra 算法、启发算法、贝尔曼算法以及弗洛伊德算法等 17 种。目前，国内外学者对最短路径算法的优化研究主要有以下三个方面：基于数据存储结构的优化传统的最短路径大部分使用的都是邻接矩阵的存储结构，存储空间为 (n 表nN示结点数目) 。但实际道路网络属于稀疏图，虽然路网中的结点数目较大，而与之关联的边的数目较小，这时采用邻接矩阵结构则会产生较大的空间浪费。E. Benjamin 提出使用邻接表、十字链表和邻接多重表的存储结构时，能够达到降低时间和空间复杂度的目的，从而很
25、好地改善了算法的效率 13。第 2 章 最短路径问题与随机概念6优先级队列结构的优化 14：利用堆排序等优先队列可以改进以往算法的优先级数组 15，陆峰等人给出了利用二叉树以及双桶结构来达到优先级队列优化的目的，从而大大改善了算法的效率16。基于搜索策略的优化：搜索范围的减小可以大大减少结点数目 n，从而改善算法的时间和空间复杂度，提升算法的运行效率。目前常用的搜索策略主要有椭圆限制搜索算法、多边形限制搜索算法以及双向搜索算法 17。2.2 图的相关定义2.2.1 图图（Graph）是一种重要的数据结构，通常用来描述某些事物之间的一种特定关系。在线性表中，数据元素之间为线性关系，除第一个和最后
26、一个元素，每个元素都有且仅有唯一的直接前驱和直接后继；在树形结构中，数据元素则是以分支关系定义的层次结构，且每一层的元素和下一层的多个元素（可能为 0 个元素）关联；在图形结构中，数据元素之间的关系是任意的，即图中任意两个元素间都有可能相关联。由于图可对自然科学和社会科学中的许多领域的问题能够进行恰当的描述和建模，所以，在很多领域中图都起到重要的作用 18。图 由顶点集 V 和边集 构成的数据结构 19，其中， 是非空的顶点(,)GVEEV的集合， 是存储顶点之间关系的集合。一般地，第 个顶点使用 表示， 存储的iiE是 中有限顶点偶对的边， 可以是空集，此时表示图 中只存在顶点而不存在边，G
27、为图 的顶点数目， 为图 中边的数目，顶点集可以表示为nm，边集表示为 。01,.nV12,.mE如果图 中的所有边均为有向的，那么图 称作有向图，此时图的边就称为有G向边，有向边的表示方法是有序对 ，其中 为起点， 为终点；如果图 中,jiVijVG的所有边都是无向的，那么图 G 称作无向图，此时图的边就称为无向边，无向的表示方法是无序对 边 和边 表示同一条边。,jiV,ij,ji如果图 中的边均没有权值，那么图 就是无权图；如果图 中的所有边都带权值，那么图 就是有权图 20，使用 w 作为其权值函数，它是 E 边到实数的映射，交通网络中通常釆用两个地点之间道路的长度或者两个地点之间的到达时间作为权值。若图 中边的数目 ，则将此类图称为稀疏图，若有向图(,)GVE2mn=中边的数目 接近于 ，无向图 中边的数目 m 接近于(,) (,)GVE
