随机网络最短路径的概率分布

摘要

本文研究了随机网络的最短路径问题，给出了一种基于马尔可夫骨架过程理论的最短路径算法。作为网络分析中的一个经典问题，随机网络最短路径问题引起了许多学者的兴趣，提出了一些算法，用以求解随机网络最短路径长度的概率分布。但这些算法都对随机网络弧长的分布加以限制，如要求其为连续分布或假定其为负指数分布等。当弧长的分布不满足这些条件时，这些算法就不再有效了，因此有必要对弧长服从一般分布的随机网络最短路径问题进行研究，给出其最短路径算法，这正是本文要解决的问题。本文假设网络弧长为服从一般分布的随机变量，利用马尔可夫骨架过程理论求解网络最短路径长度的概率分布。文中构造了一个马尔可夫骨架过程，使得从该骨架过程的初始状态首次转移到吸收状态的时间正好等于随机网络最短路径的长度，从而可以利用向后方程求解网络最短路径长度的概率分布。 本文第一章介绍了问题的历史背景及研究现状。第二章介绍了马尔可夫骨架过程的定义和一些基本性质。第三章构造马尔可夫骨架过程，并给出其状态集。第四部分给出最短路径算法。第五部分给出两个具体的例子。

目录

文摘

英文文摘

声明

第一章绪论

1.1随机网络最短路问题的研究概况

1.1.1问题的背景及研究现状

1.1.2串并联简化法

1.1.3 Kulkarni的马氏链方法

1.2本文算法的基本思想

1.3论文主要内容和结构

第二章预备知识

2.1马尔可夫骨架过程的概念

2.2向前和向后方程

2.3 正则性准则

2.4有限维分布

2.5非负线性方程组的最小非负解理论

第三章构造马尔可夫骨架过程

3.1网络基本知识

3.2马尔可夫骨架过程的建立

3.3举例构造

3.4关于马尔可夫骨架过程状态的说明

3.5网络图的简化处理

第四章最短路径长度的瞬时分布

4.1弧长服从一般分布的随机网络

4.2弧长服从连续分布的随机网络

第五章数值计算

5.1例1

5.2例2

第六章小结

参考文献

致谢

攻读学位期间主要研究成果