学位论文 > 优秀研究生学位论文题录展示

随机时间依赖网络中的自适应K期望最短路径

作　者: 张勇
导　师: 谭国真
学　校: 大连理工大学
专　业: 计算机应用技术
关键词: 自适应随机时间依赖网络 K期望路径最短路径
分类号: TP301
类　型: 硕士论文
年　份: 2006年
下　载: 239次
引　用: 3次
阅　读: 论文下载

内容摘要

在交通网络和数据网络中,网络特征(如弧的权值、结点耗费等)既具有随机性又具有时间依赖性,这样的网络称之为随机时间依赖网络,简记为STD网络。在实践中,STD网络模型比传统网络模型具有更广泛的应用。由于随机性和时间依赖性引入到网络模型中,使得最短路径问题变得复杂化和多样化,传统的最短路径算法已不再适应这样复杂的网络环境,这就迫使人们寻求新的解决方法。在随机时间依赖的交通网络中,对于一组给定的起始点和目的点,通常要选择一条期望时间最短的路径行走。但在现实的网络中,由于其它原因最短路径走不通时,可以选择第二最短路经,第三最短路径直到第K最短路径,因此需要一个K最短路径集。本文在基于自适应路径和K期望最短路径的基础上提出了求解随机时间依赖网络中自适应K期望最短路径的算法(A_KESP算法),算法得出的结果是一组策略集,这样就可以根据到达的具体时刻的不同而选择不同的路径,具有自适应性。A_KESP算法不仅适用于先进先出的网络而且适用于非先进先出的网络。首先,本文给出了STD网络模型,提出了STD网络中的路径优化条件和求解K期望最短路径的相关理论;其次设计并实现了STD网络中的A_KESP算法;然后,文章从理论上分析证明了A_KESP算法的正确性和算法的时间复杂度;最后设计试验对A_KESP算法的性能进行测试,并且给出了一个实例测试。理论证明和试验测试都表明,A_KESP算法对于解决STD网络中的自适应K期望最短路径问题有重要意义。

全文目录

摘要  4-5
Abstract  5-8
1 绪论  8-17
  1.1 最短路径问题的研究背景及意义  8-14
    1.1.1 最短路径问题的提出  8
    1.1.2 最短路径算法的分类体系  8-11
    1.1.3 随机时间依赖网络中的最短路径问题  11-14
  1.2 本文的主要工作  14-15
  1.3 本文的组织结构  15-17
2 传统网络模型与K最短路径问题  17-25
  2.1 传统网络模型定义  17-18
  2.2 K最短路径算法  18-25
    2.2.1 K最短路径标号算法的一般形式  18-21
    2.2.2 K最短路径标号修正算法  21-22
    2.2.3 K最短路径标号设置算法  22-25
3 STD网络模型  25-32
  3.1 模型定义  25
  3.2 理论基础  25-32
    3.2.1 自适应路径问题描述  25-27
    3.2.2 随机时间依赖网络的路径优化条件  27-29
    3.2.3 K期望最短路径  29-31
    3.2.4 K期望最短路径列表  31-32
4 A_KESP算法  32-35
  4.1 算法描述  32-33
  4.2 A_KESP算法的正确性  33-35
5 A_KESP算法复杂性分析  35-42
  5.1 算法迭代  35-37
  5.2 K-期望最短路径树  37-39
  5.3 时间复杂度  39-42
6 试验测试  42-51
  6.1 试验测试结果  42-44
    6.1.1 不同网络规模下的算法性能分析  42-43
    6.1.2 K值对算法性能的影响  43-44
  6.2 一个简单的应用实例  44-51
    6.2.1 具体迭代过程  44-51
结论  51-53
参考文献  53-56
攻读硕士学位期间发表学术论文情况  56-57
致谢  57-58
大连理工大学学位论文版权使用授权书  58

随机时间依赖网络中的自适应K期望最短路径

内容摘要

全文目录

相似论文