【作者】 付强；

【导师】 孙广中；

【作者基本信息】 中国科学技术大学 ， 计算机软件与理论， 2015， 硕士

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

【Abstract】 Finding the shortest path on graph is a classic problem on algorithm design. Also it plays an important role in the fields of route scheduling, GPS navigation and LBS service. Shortest path problem on road networks is specific because of massive nodes, frequent computation request and strong demand for real-time query. Traditional algorithms for shortest path problem cannot meet these requirements above.The model of "pre-processing and query" is a two-phase method for the problem of shortest-path on road networks. On the first phase, original data is pre-processed to get the intermediate data; On the second phase, given the source node and terminal node, every query will be answered quickly using the intermediate data. The thought of two phases comes from the fact that road networks are static. The first phase only needs to be computed once.The main work involved in this paper includes:1, Performance analysis for main algorithms of the shortest-path problem based on the model of "pre-processing and query";In this paper we focus on the two main strategies based on the model of "pre-processing and query":spatial-coherence-based methods and vertex-importance-based approaches. We pick the representative algorithms to compare the pre-processing time, memory consumption and query efficiency.2, Representative nodes picking strategy based on an efficient pre-computation technique for approximation distance query in road networksThe accuracy of the technique is determined by representative nodes picking strategy, so how to divide regions on graph and how to allocate representatives will influent the efficiency a lot. In this paper we propose a new strategy for dividing regions and allocating representatives, then analyze its influence on accuracy of query.3, Estimation strategy for the length of shortest-path by simulating the real-time queries on real road networks.In this paper we simulate the real scene of objects moving in road networks and propose a better strategy for computing the approximated distance between two nodes. Then we compare the distance error and time consumption by using different strategy on the simulation system.更多还原