【作者】 宋青；

【导师】 汪小帆；

【作者基本信息】 上海交通大学 ， 控制理论与控制工程， 2012， 博士

【摘要】 最短路径问题作为图论与网络优化理论经典问题之一，其研究历经了半个多世纪的发展历程，受到了来自运筹学、计算机科学、地理信息科学、交通运输等众多学科领域人员越来越多的关注。道路交通网络中的出行路线的选取是最短路径问题的一个最基本应用。最短路径问题还广泛存在于其它众多实际系统中。例如，计算机网络中的信息流只有在经由最短路由器序列进行传输时其效率才最佳；在社会关系网络中，人们更倾向于通过最少的朋友以及朋友的朋友这种连接关系来建立与陌生人之间的联系。考虑到实际系统的规模通常异常庞大，而经典最短路径算法在处理大规模问题时普遍存在计算复杂度过高、存储消耗过大等问题，因而围绕大规模网络的各类加速技术、加速算法研究成为近年来关注的重点。在这些研究中普遍涉及数据的预先计算环节，并通过预处理生成的辅助数据来加速后续算法的执行。本论文在总结现有研究成果和经验的基础之上，致力于探索更加高效、高精度的启发式路径引导算法，采用分层优化的基本思路实现对问题的降解和抽象。论文主要内容和研究成果如下：1.从复杂网络理论这一新角度出发，将其中有关层次性及社团结构方面的研究成果引入到对大规模网络分层的描述、网络动态分割质量的衡量以及后续最短路径算法的设计之中，取得了良好的效果。2.提出了一种最小化各子网络穿越距离比的网络分割模型，并设计了相应的实现算法，为非平面结构网络的划分及网络动态分割质量的衡量提供了一种新的思路和依据。3.构建了一种网络层次抽象的空间模型。通过提取分割后网络中的边界点、子网络之间边并构造各子网络内部边，以及通过将各子网络及其邻接关系映射为节点和边，进而得到高一级网络分层和抽象网络分层。这两种分层模型在很大程度上减少了原网络中节点和边的数目，从而大大降低了分层网络中搜索算法的复杂度。4.提出了一种基于子图坐标引导的快速分层最短路径算法。针对初始点与目标点位于同一子图的情形，通过重构搜索区域的方式来加快算法的执行；而针对初始点与目标点位于不同子图的情形，定义了子图坐标及子图距离来限制可搜索的子图范围，并通过调节候选子图对数目α、距离系数β和重叠节点基准值γ这三个参数的取值，进而实现算法在计算效率与精度之间的不同折衷。5.提出了一种通用性更为广泛的基于子图终止技术的快速分层最短路径算法。算法通过不断维护和更新初始点s与目标点t之间的距离值的上界d (s,t)，计算s-t间经由当前节点u离开某一子图时的距离估计下限d(s,u,t)来作出判断：一旦距离估计下限值d(s,u,t)超出了上界d (s,t)，那么从u出发的搜索以及此后所有指向节点u邻居子图的搜索即可终止，由此实现对高一级网络搜索区域的保优压缩，达到了加快算法执行的目的。6.针对文中提出的基于子图坐标引导的分层最短路径算法和基于子图终止技术的分层最短路径算法的精度以及复杂度给出了理论分析与证明，并结合仿真实验分析对比了不同网络分割方案下这两种分层最短路径算法相对于现有算法的性能改进，指出了它们各自的优势及不足，验证了本文算法的有效性。更多还原

【Abstract】 Computing the shortest paths in graphs is one of the most fundamental andwell-studied problems in network algorithms. Numerous real-world applications haveattracted research investigations for more than half a century, involving researchersfrom many fields including operational research, computer science, geographicinformation science, and public transportation. Finding routes in road networks is aclassical application motivating the study of the shortest path problem, and thisproblem also arises in many other domains of practical importance. For example, thetransmission of messages in a computer network is most efficient when they are sentby the shortest sequence of routers; In social networks, one would like to establishcontact with a stranger through least connections of friends and their followers.Considering that real systems are usually very large, and conventional shortest pathalgorithms failed to apply to large-scale problems due to their heavy computationalcomplexity and memory consumption; thus, there is a considerable interest in speeduptechniques, which typically invest some time into a preprocessing task in order togenerate auxiliary data that can be used to accelerate the subsequent path queries. Thisthesis investigates the problem of computing shortest paths more efficiently andaccurately based on the current research experiences and achievements, following abasic idea of hierarchical optimization for the original problem decomposition. Themain content and contributions of this thesis are summarized as follows:1. From a new research perspective of complex network theory, we integrate therecent achievements on hierarchical topology and community structure intohierarchical modeling of large-scale networks, measuring of dynamic networkpartition qualities, and also designing of subsequent path computationalgorithms, which yield promising results.2. We propose a graph partition model with the objective of minimizing thetraversing distance ratio of each subgraph, and we develop a partition algorithm for achieving this model, which provides a new way for non-planargraph partitioning and partition quality measuring of dynamic networks.3. We develop a hierarchical graph model, including the high-level graph and theabstraction graph, which are constituted respectively by extracting the bordernodes, the intercommunity edges, and the constructed community edges withineach subgraph of the partitioned network, and by mapping the subgraphs andtheir connections as nodes and edges. The model decreases the number ofnodes and edges substantially compared to the original network, therebygreatly reducing the search complexity of a hierarchical algorithm.4. We propose a fast hierarchical shorest path algorithm based on the heuristics ofsubgraph coordinates. For the source and destination nodes that located in thesame subgraph, the algorithm achieves acceleration by restricting the search toa rebuilding area; While for the source and destination nodes in differentsubgraphs, the algorithm makes use of the definition of subgraph coordinatesand subgraph distances to select the subgraphs for visit, and it can get differenttradeoffs between efficiency and accuracy via the regulation of the followingthree parameters: the number of selected subgraph pairs α, the distancecoefficient β, and the benchmark of overlapping nodes γ.5. We propose another fast hierarchical shortest path algorithm with broaderapplication, which is based on the subgraph pruning technique. The algorithmmaintains a close upper bound d (s,t)on the length of the shortest path fromthe source node s to the destination node t, which is tightened repeatedly duringthe algorithm execution. Whenever the search branch is about to leave asubgraph via the current node u, a lower estimate d(s,u,t) is calculated on thelength of a possible route from s via u to t. If this lower estimate exceeds thecurrent upper bound, then all searches from u together with those grow into theadjacent subgraph of u will be pruned, thereby eliminating unnecessarysearches and thus achieving acceleration.6. We give a theoretical analysis of the accuracy and the computationalcomplexity of the proposed subgraph coordinates based and the subgraphpruning technique based hierarchical shortest path algorithms, and we presentexperimental tests to compare and analyze the performance achievements ofthese two hierarchical algorithms to the existing algorithm under different network partition schemes. We point out the strengths and weaknesses of thetwo algorithms, and demonstrate their effectiveness from both theoretical andexperimental aspects.更多还原