多狀態(tài)網(wǎng)絡可靠度的d-最小割(路)集轉(zhuǎn)換算法
2011-12-31 00:00:00李振孫新利姬國勛劉好杰劉志勇
計算機應用研究 2011年11期
摘要：為尋求計算多狀態(tài)網(wǎng)絡系統(tǒng)可靠度更為簡明的方法，提出了一種d－最小割、路集轉(zhuǎn)換算法。該算法在已知d－最小割(路)集的基礎(chǔ)上，基于邏輯代數(shù)理論，通過展開和之積表達式獲得d一最小路(割)集，再基于兩者中數(shù)量較少的一個運用容斥原理，得到網(wǎng)絡可靠度。同時，分別利用容量未取最大和不為0的邊及對應取值組成的集合對表示d－最小割(路)，基于集合之間的隸屬關(guān)系及將集合運算中正常的先取逆再合并的運算順序變?yōu)橄群喜⒃偃∧娴乃枷耄岢鱿嚓P(guān)引理，簡化算法。通過復雜度分析，證明算法有效。算例證明了算法的有效性和適用性。
關(guān)鍵詞：多狀態(tài)網(wǎng)絡；隨機流量網(wǎng)絡；d－最小割集；d－最小路集；可靠度
中圖分類號：TP202.1；TP301.6 文獻標志碼：A 文章編號：1001—3695(2011)11—4270—04
