原文传递
基于预处理的交通网最短路径实时查询研究
| 论文题名： | 基于预处理的交通网最短路径实时查询研究 |
| 关键词： | 最短路径算法;交通网;实时查询;预处理;距离估算策略 |
| 摘要： | 最短路径问题是图论与算法设计中的经典问题，同时也在路径规划、物流规划、GPS导航、社交网络、基于位置的服务(LBS)等现实世界的应用中扮演着重要的角色。交通路网上最短路径问题由最短路径问题衍生而来，特点为交通网数据规模大（如北京市主干路网就包含了10万个顶点与10万条边），计算请求频繁且实时性要求很高，传统的最短路径算法并不能满足计算需求。 “预处理——查询”模型是一种交通路网上最短路径问题的两阶段方法。在第一阶段对数据进行预处理，包括获得待使用的中间数据，以降低问题的求解难度;第二阶段被称为查询阶段，给定查询请求的源点与目标点，每个请求须在极短时间内进行响应。两阶段的想法源自路网是静态的，因此预处理阶段可以仅执行一次，其结果可以应对相同路网上大规模的查询请求。 本文主要工作有: 1，基于预处理——查询模型的几种点到点最短路径算法性能分析 本文针对“预处理——查询”模型上的两类算法——空间相干为基础的方法和顶点重要性为基础的方法，选出两类方法中具有代表性的算法，就预处理时间、空间消耗、查询效率进行分析比较。 2，针对一种基于代表元的有效最短路径近似算法，对代表元选取策略进行研究 由于代表元的选取策略直接影响近似算法的求解精度，因此如何对路网进行区域划分、如何在区域中分配代表元成为了算法是否高效的关键点。本文将结合已提出的高效划分方案，提出一种适合最短路径近似算法的划分策略，并分析其与求解精度之间的联系。 3，通过模拟真实环境下路网上的实时查询请求，对最短路径长度的估算策略进行研究 本文通过结合可视化的路网动态查询演示，说明近似算法对于最短路径中源点与目标结点的近似距离可做进一步优化，并提出一种基于代表元的两点间距离估算策略，对估算误差进行分析。 |
| 作者： | 付强 |
| 专业： | 计算机软件与理论 |
| 导师： | 孙广中 |
| 授予学位： | 硕士 |
| 授予学位单位： | 中国科学技术大学 |
| 学位年度： | 2015 |
| 正文语种： | 中文 |
检索历史
应用推荐
