基于预处理的交通网最短路径实时查询研究

《基于预处理的交通网最短路径实时查询研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、?齒料冷我本大逢硕士学位论文论文题目于预处理的文通网最短路径卖对去询研尧作者姓名学科专业讨鼻机救件与理办导师姓名孙厂躲缓完成时间二—月肀函科嗲敉术大嗲硕士学位论文基于预处理的交通网最短路径实时查询研究作者姓名：付强学科专业：计算机软件与理论导师姓名：孙广中副教授完成时间：二一五年四月UniversityofScienceandTechnologyofChinaAdissertationformaster'sdegreeStudyofPre-computationandQueryTechniqueforShortestPathProblemonRoadNetworkAuthor'sName：：：

2、中国科学技术大学学位论文原创性声明本人声明所呈交的学位论文是本人在导师指导下进行研究工作所取得的成果。除已特别加以标注和致谢的地方外，论文中不包含任何他人己经发表或撰写过的研究成果。与我一同工作的同志对本研宄所做的贡献均己在论文中作了明确的说明。作者签名：抓签字日期：工中国科学技术大学学位论文授权使用声明作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学拥有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入《中国学位论文全文数据库》等有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位

3、论文。本人提交的电子文档的内容和纸质论文的内容相一致。保密的学位论文在解密后也遵守此规定。口保密（年）作者签名咏导师签名：签字日期：签字日期：摘要摘要最短路径问题是图论与算法设计中的经典问题，同时也在路径规划、物流规划、导航、社交网络、基于位置的服务（等现实世界的应用中扮演着重要的角色。交通路网上最短路径问题由最短路径问题衍生而来，特点为交通网数据规模大（如北京市主干路网就包含了万个顶点与万条边，计算请求频繁且实时性要求很高，传统的最短路径算法并不能满足计算需求。“预处理—查询”模型是一种交通路网上最短路径问题的两阶段方法。在第一阶段对数据进行预处理，包括获得待使用的中间数据，以降低问题的求解

4、难度；第二阶段被称为查询阶段，给定查询请求的源点与目标点，每个请求须在极短时间内进行响应。两阶段的想法源自路网是静态的，因此预处理阶段可以仅执行一次，其结果可以应对相同路网上大规模的查询请求。本文主要工作有：，基于预处理—查询模型的几种点到点最短路径算法性能分析本文针对“预处理一一查询”模型上的两类算法—空间相干为基础的方法和顶点重要性为基础的方法，选出两类方法中具有代表性的算法，就预处理时间、空间消耗、查询效率进行分析比较。，针对一种基于代表元的有效最短路径近似算法，对代表元选取策略进行研究由于代表元的选取策略直接影响近似算法的求解精度，因此如何对路网进行区域划分、如何在区域中分配代表元成为

5、了算法是否高效的关键点。本文将结合已提出的高效划分方案，提出一种适合最短路径近似算法的划分策略，并分析其与求解精度之间的联系。，通过模拟真实环境下路网上的实时查询请求，对最短路径长度的估算策略进行研宄本文通过结合可视化的路网动态查询演示，说明近似算法对于最短路径中源点与目标结点的近似距离可做进一步优化，并提出一种基于代表元的两点间距离估算策略，对估算误差进行分析。关键词：最短路径；路网；预处理；代表元。ABSTRACTABSTRACTFindingtheshortestpathongraphisaclassicproblemonalgorithmdesign.Alsoitplaysanimpo

6、rtantroleinthefieldsofroutescheduling,GPSnavigationandLBSservice.Shortestpathproblemonroadnetworksisspecificbecauseofmassivenodes,frequentcomputationrequestandstrongdemandforreal-timequery.Traditionalalgorithmsforshortestpathproblemcannotmeettheserequirementsabove.Themodelof"pre-processingandquery"i

7、satwo-phasemethodfortheproblemofshortest-pathonroadnetworks.Onthefirstphase,originaldataispre-processedtogettheintermediatedata;Onthesecondphase,giventhesourcenodeandterminalnode,everyquerywillbeanswe