论文部分内容阅读
最短路径问题作为图论与网络优化理论经典问题之一,其研究历经了半个多世纪的发展历程,受到了来自运筹学、计算机科学、地理信息科学、交通运输等众多学科领域人员越来越多的关注。道路交通网络中的出行路线的选取是最短路径问题的一个最基本应用。最短路径问题还广泛存在于其它众多实际系统中。例如,计算机网络中的信息流只有在经由最短路由器序列进行传输时其效率才最佳;在社会关系网络中,人们更倾向于通过最少的朋友以及朋友的朋友这种连接关系来建立与陌生人之间的联系。考虑到实际系统的规模通常异常庞大,而经典最短路径算法在处理大规模问题时普遍存在计算复杂度过高、存储消耗过大等问题,因而围绕大规模网络的各类加速技术、加速算法研究成为近年来关注的重点。在这些研究中普遍涉及数据的预先计算环节,并通过预处理生成的辅助数据来加速后续算法的执行。本论文在总结现有研究成果和经验的基础之上,致力于探索更加高效、高精度的启发式路径引导算法,采用分层优化的基本思路实现对问题的降解和抽象。论文主要内容和研究成果如下: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.针对文中提出的基于子图坐标引导的分层最短路径算法和基于子图终止技术的分层最短路径算法的精度以及复杂度给出了理论分析与证明,并结合仿真实验分析对比了不同网络分割方案下这两种分层最短路径算法相对于现有算法的性能改进,指出了它们各自的优势及不足,验证了本文算法的有效性。