基于随机点集最短路径算法的研究与实现——毕业论文

《基于随机点集最短路径算法的研究与实现——毕业论文》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、毕业设计中文题目基于随机点集最短路径算法的研究与实现英文题目TheResearchandImplementationoftheShortestPathAlgorithmBasedontheStochasticSet院系：计算机与信息工程学院年级专业：金融服务姓名：学号：指导教师：职称：年月摘要摘要最短路径的研究属于网络优化领域，它也是图论的重要内容，涉及现实生活诸多方面。该算法可应用于交通规划、旅游安排、城市建设等，至今仍然是业界研究热点。本文着重研究的是图网中任意若干顶点之间的最短路径最优规划。本课题通过使用matlab实现4个经典的随机最短路径派生算法，并将其应用在纽约

2、等6个城市路网数据集上，进行随机规划最优最短路径的模拟，来研究算法各项性能指标，对比其优劣。案例研究结果表明，本课题所采用的算法，大幅度减少了冗余节点，减轻了复杂度的操作，提高了算法的性能和效率，并且确保课精确度。该算法可以有效应用在多种路径规划类现实应用中，提高工作效率。关键词：最短路径；网络规划36ABSTRACTABSTRACTShortestpatchbelongstonetworkoptimization,alsotheimportantcontentingraphtheory.Itiswidelyusedindifferentfieldsinthereallif

3、e.Atpresent,theseresearchtheoriescanbeusedinapplicationfieldssuchastrafficplanning,tourismarrangement,urbanconstructionandsoon.Theshortestpathalgorithmisstillahotresearchtopicnow.Thepaperwillstudytherandomlyprocessedfourmodernclassicalderivedshortestpathalgorithmsinurbanroadnetworkdatasetr

4、espectively.Thesubjectwillanalyzetheimpactofthesefouralgorithmsondifferentperformance.AndappliesthesealgorithmsinNewYorkCityroadnetworkdataset,datasetsaresixsuchcities.Forthesimulationofstochasticprogrammingoptimalshortestpathalgorithmtoresearchtheperformanceindexes,comparedtheadvantagesan

5、ddisadvantages.Casestudyresultsshowthatthistopicbythealgorithm,greatlyreducestheredundantnodesandreducesthecomplexityoftheoperation,Notonlytheperformanceandefficiencyofthisalgorithmisimproved,andtoensureaccuracy.Thealgorithmcanbeeffectivelyappliedinavarietyofpathplanninginthepracticalappli

6、cation,improvetheworkefficiency.KeyWords:shortestpatch;networkoptimization36目录目录第1章引言11.1课题研究背景及意义11.2本文的研究内容1第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.1Dijkstra算法93.2Floyd算法113.3SPFA算法

7、113.4Bellman-Ford算法133.5本章小结16第4章随机最短路径的矩阵算法174.1问题引出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致谢3536第1章引言第1章引言1.