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