动态环境下路径计算问题的研究与模拟实现

论文摘要

动态环境下的路径计算问题是近年来路径算法研究的热门话题。动态环境下的最短路径算法在物流配送,网络架构,城市规划等领域被广泛的运用。同时,作为解决最优化问题的基础,在动态环境下对最短路径算法进行研究与模拟实现也具有很高的理论价值。目前被研究最多的动态算法是DSP（Dynamic Shortest Path）算法,即在动态环境下,当边权值发生改变后重新求出最短路径树的算法,本文在已有算法的基础上设计出改进和扩展的DSP算法,并通过实验来模拟实现,具体做了以下工作:首先,总结已有的DSP算法,分析和归纳这些算法的优缺点,并重点对球线模型（Ball-and-String Model）算法进行了深层次的研究。其次,设计出新DSP算法,包括针对动态环境下边权值增大的算法:SDI算法和BSI算法;针对动态环境下边权值减小的算法:SDD算法;以及针对边权值既有增大又有减小的算法:ISF算法。前三种算法称为半动态算法,第四种称为全动态算法。此外,本文还结合实际应用的需要设计了一种带权值比较的静态最短路径算法:CWPT算法。最后,通过实验模拟动态环境,对所设计的算法进行测试,分析算法的性能,证明本文设计的算法在计算复杂度和最大程度保持原有最短路径树拓扑结构不变两个方面较已有算法有一定程度的改进。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 选题背景
• 1.2 论文研究的意义
• 1.2.1 论文研究的实用价值
• 1.2.2 论文研究的理论价值
• 1.3 动态环境下路径问题的发展概况及现状
• 1.4 论文所要解决的问题
• 1.5 本文的结构
• 第二章 图的定义及最短路径问题相关概念
• 2.1 图的基本定义
• 2.2 图的存储结构
• 2.3 图的遍历
• 2.4 最短路径问题及相关算法
• 2.4.1 最小生成树算法
• 2.4.2 最短路径算法
• 第三章 动态环境下的路径计算问题
• 3.1 DSP 问题中的符号及基本定义
• 3.2 已有的动态算法
• 3.2.1 FMN 算法
• 3.2.2 Dynamic SWSF-FP
• 3.2.3 基于球线模型的动态SPT 算法
• 3.3 本章小结
• 第四章 改进的动态最短路径算法的设计与实现
• 4.1 半动态最短路径算法
• 4.1.1 SDI（semi-dynamic-increase）算法
• 4.1.2 BSI（Ball-and-string increase）算法
• 4.1.3 SDD（semi-dynamic-decrease）算法
• 4.2 全动态最短路径算法
• 4.2.1 ISF 算法基本思想
• 4.2.2 ISF 算法设计
• 4.3 带权值比较的SPT 算法
• 4.3.1 CWPT 算法基本思想
• 4.3.2 CWPT 算法设计
• 4.4 本章小结
• 第五章 动态环境下最短路径算法的模拟实验
• 5.1 实验环境
• 5.2 算法评价标准
• 5.3 影响算法的因素
• 5.4 实验结果及分析
• 5.4.1 权值改变数目对各算法的影响
• 5.4.2 权值变化率对各算法的影响
• 第六章 总结与展望
• 6.1 本文工作的总结
• 6.2 未来工作的展望
• 致谢
• 参考文献