隨機(jī)網(wǎng)絡(luò)最短路徑的概率分布.pdf

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

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