计算机科学
計算機科學
계산궤과학
COMPUTER SCIENCE
2012年
8期
104-110
,共7页
多状态网络%随机流量网络%可靠度界%边状态枚举
多狀態網絡%隨機流量網絡%可靠度界%邊狀態枚舉
다상태망락%수궤류량망락%가고도계%변상태매거
为降低计算多状态网络可靠度的复杂性,综合考虑网络中具有多态性的边处于各中间状态的概率及从某中间状态转换到相邻状态对网络性能的影响,提出了一种基于边状态枚举计算多状态网络可靠度上下界的算法.该算法首先令网络中各边仅取完全工作和完全失效两种状态,将处于中间状态的概率分别叠加到完全工作和完全失效状态的概率上,得到可靠度上下界的初始值;而后按照对可靠度影响递减的顺序迭代枚举边的中间状态,通过集合间的比较,计算可靠度上下界的改变值,同时获得不断减小的可靠度上界和不断增加的可靠度下界,使其最终收敛于可靠度精确值.该算法不需提前求取网络d-最小割(路)集,且枚举较少的网络状态即可得到紧凑的可靠度上下界.相关引理的证明及算例分析验证了该算法的正确性和有效性.
為降低計算多狀態網絡可靠度的複雜性,綜閤攷慮網絡中具有多態性的邊處于各中間狀態的概率及從某中間狀態轉換到相鄰狀態對網絡性能的影響,提齣瞭一種基于邊狀態枚舉計算多狀態網絡可靠度上下界的算法.該算法首先令網絡中各邊僅取完全工作和完全失效兩種狀態,將處于中間狀態的概率分彆疊加到完全工作和完全失效狀態的概率上,得到可靠度上下界的初始值;而後按照對可靠度影響遞減的順序迭代枚舉邊的中間狀態,通過集閤間的比較,計算可靠度上下界的改變值,同時穫得不斷減小的可靠度上界和不斷增加的可靠度下界,使其最終收斂于可靠度精確值.該算法不需提前求取網絡d-最小割(路)集,且枚舉較少的網絡狀態即可得到緊湊的可靠度上下界.相關引理的證明及算例分析驗證瞭該算法的正確性和有效性.
위강저계산다상태망락가고도적복잡성,종합고필망락중구유다태성적변처우각중간상태적개솔급종모중간상태전환도상린상태대망락성능적영향,제출료일충기우변상태매거계산다상태망락가고도상하계적산법.해산법수선령망락중각변부취완전공작화완전실효량충상태,장처우중간상태적개솔분별첩가도완전공작화완전실효상태적개솔상,득도가고도상하계적초시치;이후안조대가고도영향체감적순서질대매거변적중간상태,통과집합간적비교,계산가고도상하계적개변치,동시획득불단감소적가고도상계화불단증가적가고도하계,사기최종수렴우가고도정학치.해산법불수제전구취망락d-최소할(로)집,차매거교소적망락상태즉가득도긴주적가고도상하계.상관인리적증명급산례분석험증료해산법적정학성화유효성.