隨機網絡最短路徑的概率分布.pdf

1、本文研究了隨機網絡的最短路徑問題，給出了一種基于馬爾可夫骨架過程理論的最短路徑算法。作為網絡分析中的一個經典問題，隨機網絡最短路徑問題引起了許多學者的興趣，提出了一些算法，用以求解隨機網絡最短路徑長度的概率分布。但這些算法都對隨機網絡弧長的分布加以限制，如要求其為連續(xù)分布或假定其為負指數(shù)分布等。當弧長的分布不滿足這些條件時，這些算法就不再有效了，因此有必要對弧長服從一般分布的隨機網絡最短路徑問題進行研究，給出其最短路徑算法，這正是本文要

2、解決的問題。本文假設網絡弧長為服從一般分布的隨機變量，利用馬爾可夫骨架過程理論求解網絡最短路徑長度的概率分布。文中構造了一個馬爾可夫骨架過程，使得從該骨架過程的初始狀態(tài)首次轉移到吸收狀態(tài)的時間正好等于隨機網絡最短路徑的長度，從而可以利用向后方程求解網絡最短路徑長度的概率分布。 本文第一章介紹了問題的歷史背景及研究現(xiàn)狀。第二章介紹了馬爾可夫骨架過程的定義和一些基本性質。第三章構造馬爾可夫骨架過程，并給出其狀態(tài)集。第四部分給出最短路