带二次参数赋权多阶段网络的最短路问题研究

摘要

网络最短路径问题一直是计算机科学、运筹学、地理信息科学等学科的一个研究热点。目前，静态网络最短路算法已经研究得十分完善，而动态网络最短路算法的研究比较薄弱。静态算法只能处理固定网络拓扑结构和固定权值的网络最短路径问题。但是，在实际中遇到的网络大多是动态的、不确定的，即网络拓扑结构或权值可能会随时间变化，静态算法对此类动态问题不一定有效。随着计算机通信网络、移动通信网络、分布式处理和智能交通系统等诸多领域的蓬勃发展，出现了大量的非静态网络，就迫使人们不得不去深入地研究这种动态的、不确定的更为复杂的赋权网络最短路问题。因此，建立动态网络中的最短路算法已经成为当今网络优化的研究热点之一。 当网络中的权值不是常数而是带参数的函数时，它便是一种动态网络，用传统的算法求解这类网络的最短路径变得十分困难，甚至无法求解。如果网络中的权值是带二次参数的函数，这样的网络称之为带二次参数赋权网络。 本文采用从特殊到一般的方式循序渐进地研究了带二次参数赋权多阶段网络的最短路问题。首先研究了带特殊二次参数赋权多阶段网络的最短路问题，其次研究了带一般二次参数赋权多阶段网络的最短路问题，最后研究了带线性、二次参数混合赋权多阶段网络的最短路问题。本文采用Dijkstra算法思想和隐枚举方法，在理论分析的基础上，得到了如下主要结果： 1．给出了带特殊二次参数赋权多阶段网络的最短路问题的一些隐枚举规则(3.1.3节中的引理3-1-1至引理3-1-4)，并以这些规则为支撑给出了带特殊二次参数赋权多阶段网络的最短路算法(3.1.4节中的算法3-1)，以及带特殊二次参数赋权多阶段网络的求临界点算法(3.1.5节中的算法3-2)； 2．给出了带一般二次参数赋权多阶段网络的最短路问题的一些隐枚举规则(3.2.3节中的引理3-2-1至引理3-2-4)，并以这些规则为支撑给出了带一般二次参数赋权多阶段网络的最短路算法(3.2.4节中的算法3-3)，以及带一般二次参数赋权多阶段网络的求临界点算法(3.2.5节中的算法3-4)； 3．给出了对于带线性、二次参数混合赋权多阶段网络的最短路问题的一些隐枚举规则(4.3 节中的引理 4-3-1 至引理 4-3-4)，并以这些规则为支撑给出了带线性、二次参数混合赋权多阶段网络的最短路算法(4.4 节中的算法 4-1)，以及带线性、二次参数混合赋权多阶段网络的求临界点算法(4.5 节中的算法 4-3)。论文还对带线性、二次参数混合赋权多阶段网络的最短路算法进行了算法复杂性分析，分析结果表明，尽管文中给出的最短路算法不是多项式的，但对于一定规模的该类网络，算法还是十分有效的。

目录

文摘

英文文摘

声明

第一章 引言

1.1研究背景及意义

1.2国内外研究现状

1.2.1静态网络最短路径算法的研究

1.2.2动态网络最短路径算法的研究

1.2.3最短路径并行算法的研究

1.2.4大规模网络模型与最优路径算法

1.3本文的主要工作

1.4论文的组织结构

第二章 预备知识

2.1相关概念

2.2Dijkstra算法基本思想

2.3带线性参数赋权多阶段网络的最短路算法

2.3.1带线性参数赋权多阶段网络

2.3.2带线性参数赋权多阶段网络的临界点

2.3.3带线性参数赋权多阶段网络的最短路算法

2.3.4带线性参数赋权多阶段网络的求临界点算法

2.4带参数赋权多阶段网络的最短路问题

2.4.1带参数赋权多阶段网络

2.4.2带参数赋权多阶段网络的临界点

2.4.3带参数赋权多阶段网络最短路算法的基本步骤

2.5本章小结

第三章 带二次参数赋权多阶段网络的最短路算法

3.1带特殊二次参数赋权多阶段网络的最短路算法

3.1.1带特殊二次参数赋权多阶段网络

3.1.2带特殊二次参数赋权多阶段网络的临界点

3.1.3引理

3.1.4带特殊二次参数赋权多阶段网络的最短路算法

3.1.5带特殊二次参数赋权多阶段网络的求临界点算法

3.1.6实例

3.2带一般二次参数赋权多阶段网络的最短路算法

3.2.1带一般二次参数赋权多阶段网络

3.2.2带一般二次参数赋权多阶段网络的临界点

3.2.3引理

3.2.4带一般二次参数赋权多阶段网络的最短路算法

3.2.5带一般二次参数赋权多阶段网络的求临界点算法

3.2.6实例

3.3本章小结

第四章 带线性、二次参数混合赋权多阶段网络的最短路算法

4.1带线性、二次参数混合赋权多阶段网络

4.2带线性、二次参数混合赋权多阶段网络的临界点

4.3引理

4.4带线性、二次参数混合赋权多阶段网络的最短路算法

4.5带线性、二次参数混合赋权多阶段网络的求临界点算法

4.6实例

4.7算法复杂性分析

4.8本章小结

第五章 结论及进一步研究问题

5.1结论

5.2进一步研究问题

参考文献

致谢

附录A 在读硕士期间发表论文情况

附录B 个人简况及联系方式