基于決策圖的多狀態(tài)流網(wǎng)絡(luò)可靠性算法研究.pdf

1、近年來，多狀態(tài)網(wǎng)絡(luò)的可靠性研究成為可靠性研究領(lǐng)域的熱點(diǎn)。本文引入具有隱式表達(dá)、易操作等特點(diǎn)的決策圖技術(shù)，對更接近現(xiàn)實(shí)的多狀態(tài)流網(wǎng)絡(luò)可靠性進(jìn)行了研究。主要研究內(nèi)容及研究成果如下：
　　(1)給出了基于現(xiàn)實(shí)假設(shè)下多狀態(tài)流網(wǎng)絡(luò)的形式化模型，該模型適用于節(jié)點(diǎn)可靠，邊上存在隨機(jī)獨(dú)立分布的多個容量狀態(tài)的多狀態(tài)流網(wǎng)絡(luò)的可靠性分析。在此模型上提出了基于有序二叉決策圖（OBDD）的MFN_OBDD算法來計(jì)算多狀態(tài)流網(wǎng)絡(luò)可靠度。算法從網(wǎng)絡(luò)的可滿足界值

2、流向量 flow(d)出發(fā)，引入決策圖技術(shù)構(gòu)造能夠表示滿足需求的所有狀態(tài)向量的決策圖；然后通過遍歷決策圖得到網(wǎng)絡(luò)的可靠度。在構(gòu)造決策圖的過程中，給出了生成并簡化狀態(tài)決策圖、邊決策圖、流決策圖、目標(biāo)決策圖的操作函數(shù)，壓縮了狀態(tài)空間，有效地降低了決策圖的操作復(fù)雜性。理論上證明了算法的正確性，分析了算法復(fù)雜度。實(shí)驗(yàn)結(jié)果及實(shí)驗(yàn)分析表明：與J&L的空間分解算法相比，MFN_OBDD算法能夠有效地降低空間復(fù)雜度和循環(huán)次數(shù)。
　　(2)在MFN

3、_OBDD算法基礎(chǔ)上，提出了基于多值決策圖（MDD）的MFN_MDD算法。相比 MFN_OBDD算法，減少了變量數(shù)，降低了算法復(fù)雜度。實(shí)驗(yàn)表明：MFN_MDD算法中得到的 MDD的層次和節(jié)點(diǎn)數(shù)遠(yuǎn)少于 MFN_OBDD算法中得到的OBDD的層次和節(jié)點(diǎn)數(shù)；MFN_MDD算法比MFN_OBDD算法高效。
　　(3)提出了基于最小割集和代數(shù)決策圖（ADD）的MFN_MCADD算法來評估多狀態(tài)流網(wǎng)絡(luò)可靠性。算法從網(wǎng)絡(luò)的最小割集出發(fā)，首先構(gòu)造

4、在需求d約束下每個最小割集的決策圖，為此，創(chuàng)建了生成邊決策圖、割決策圖的操作函數(shù)。然后利用最大流最小割定理合并所有割決策圖，生成了能夠表示可滿足狀態(tài)空間的目標(biāo)決策圖。在此基礎(chǔ)上，提出了基于多值決策圖的MFN_MCMDD算法。理論上證明了算法的正確性并分析了算法復(fù)雜度。通過實(shí)例分析驗(yàn)證了MFN_MCADD算法和MFN_MCMDD算法的正確性和可行性，且MFN_MCMDD算法中得到的MDD的層次和節(jié)點(diǎn)數(shù)遠(yuǎn)少于MFN_MCADD算法中得到的A