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

摘要

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

目录

文摘

英文文摘

独创性说明及大连理工大学学位论文版权使用授权书

1绪论

1.1最短路径问题的研究背景及意义

1.1.1最短路径问题的提出

1.1.2最短路径算法的分类体系

1.1.3随机时间依赖网络中的最短路径问题

1.2本文的主要工作

1.3本文的组织结构

2传统网络模型与K最短路径问题

2.1传统网络模型定义

2.2 K最短路径算法

2.2.1 K最短路径标号算法的一般形式

2.2.2 K最短路径标号修正算法

2.2.3 K最短路径标号设置算法

3 STD网络模型

3.1模型定义

3.2理论基础

3.2.1自适应路径问题描述

3.2.2随机时间依赖网络的路径优化条件

3.2.3 K期望最短路径

3.2.4 K期望最短路径列表

4 A KESP算法

4.1算法描述

4.2 A KESP算法的正确性

5 A KESP算法复杂性分析

5.1算法迭代

5.2 K-期望最短路径树

5.3时间复杂度

6试验测试

6.1试验测试结果

6.1.1不同网络规模下的算法性能分析

6.1.2 K值对算法性能的影响

6.2一个简单的应用实例

6.2.1具体迭代过程

结论

参考文献

攻读硕士学位期间发表学术论文情况

致射