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

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

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

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

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