并行k最短路径搜索算法研究

《并行k最短路径搜索算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号:U49110710-2012124019硕士学位论文并行K最短路径搜索算法研究李莹导师姓名职称段宗涛教授申请学位级别工学硕士学科专业名称信息与通信工程论文提交日期2015年5月26日论文答辩日期2015年6月6日学位授予单位长安大学ResearchonParallelKShortestPathsSearchAlgorithmAThesisSubmittedfortheDegreeofMasterCandidate：LiYingSupervisor：Prof.DuanZongtaoChang’anUniversity,Xi’an,China论文独创性声明本人声明：本人所呈交的

2、学位论文是在导师的指导下，独立进行研究工作所取得的成果。除论文中已经注明引用的内容外，对论文的研究做出重要贡献的个人和集体，均己在文中以明确方式标明。本论文中不包含任何未加明确注明的其他个人或集体已经公开发表的成果。本声明的法律责任由本人承担。论文作者签名：香f•7WS年《月0曰论文知识产权权属声明本人在导师指导下所完成的论文及相关的职务作品，知识产权归属学校。学校享有以任何方式发表、复制、公开阅览、借阅以及申请专利等权利。本人离校后发表或使用学位论文或与该论文直接相关的学术论文或成果时，署名单位仍然为长安大学。(保密的论文在解密后应遵守此规定）论文作者签名：Ii>/!：年（月/阳

3、导师签名：备年Z月/D曰摘要最短路径搜索不仅在城市交通路网规划和人工智能等领域被广泛应用，而且是现阶段智能交通行业研究的焦点。城市的发展使得城市规模不断扩大，城市路网变得越来越复杂，路网节点数目也迅速增加，从时间代价和计算量等多方面因素考虑，传统串行算法无法达到期望的求解结果。因此，伴随着并行技术发展，并行算法出现能够有效减少最短路径搜索时间，方便我们在大规模路网中求解最短路径。一般求解最短路径的算法存在一些问题，例如，采用Dijkstra算法在大规模城市交通路网中搜索最短路径，面对用户并发的出行请求，容易造成交通拥堵，降低了城市交通的运行效率。K最短路径(KShortestPat

4、hs，KSP)算法是路径搜索算法的另一个应用形式，区别于其他算法的是它可以搜索出路网中两点间的最短路径集合，能够尽可能的满足出行者的需求。实际中，路网规模越复杂，KSP算法需要计算的数据量就越大，占2用计算机存储空间也就越多。文中提到的KSP算法具有O(n+n+m)的时间复杂度，程序执行消耗时间较长，导致算法效率和实时性不高。本文从最短路径问题入手，结合城市路网交通流状况，分析了城市交通网络中最短路径算法发展现状，重点描述了KSP算法。针对传统算法存在的问题，本文提出将KSP算法并行化的思想来搜索最短路径。首先，分析城市道路网络的拓扑结构，根据路网的网络结构特点，确定网络分解的基本

5、要求、网络划分方法以及交通网络分割算法。其次，本文以方格式路网模型为基础进行研究，按照网络分割原则划分网络，选择路径的源点和终点，运用并行K最短路径(ParallelKShortestPaths，PKSP)算法搜索路径，能够得到一个最短路径集合。最后，对PKSP算法的指标体系进行了评估，运用PKSP算法既降低了搜索路径的时间，提高了算法的搜索效率，又能获得较好的加速比。同时，将PKSP算法在城市路网交通流分配方面做了应用，结果证明：在大规模路网中，如果同时出现多个出行请求，PKSP算法能够搜索出多条符合K最短路径集合选择要求的最短路径，扩大了路段交通流的分布范围，降低了发生交通堵塞

6、的频率。关键词：智能交通，路径搜索，并行技术，K最短路径算法iAbstractShortestpathsearchingiswidelyusedinthefieldofurbantrafficnetworkplanningandartificialintelligence,whichisthefocusoftheresearchofintelligenttransportationindustryatpresentstage.Thedevelopmentofthecitymakesthecityscaleexpandsunceasingly,theurbanroadnetworkh

7、asbecamemoreandmorecomplex,thenumberofnetworknodesisalsoincreasingrapidly.Consideringtimecost,calculationandotherfactors,thetraditionalserialalgorithmcan’tobtaintheexpectedresults.Withthedevelopmentofparalleltechnology,theparallelalgori