摘要
为寻求计算多状态网络系统可靠度更为简明的方法,提出了一种d-最小割、路集转换算法。该算法在已知d-最小割(路)集的基础上,基于逻辑代数理论,通过展开和之积表达式获得d-最小路(割)集,再基于两者中数量较少的一个运用容斥原理,得到网络可靠度。同时,分别利用容量未取最大和不为0的边及对应取值组成的集合对表示d-最小割(路),基于集合之间的隶属关系及将集合运算中正常的先取逆再合并的运算顺序变为先合并再取逆的思想,提出相关引理,简化算法。通过复杂度分析,证明算法有效。算例证明了算法的有效性和适用性。
This paper proposed a transition algorithm of d-mincuts and d-minpaths in order to effectively compute multi-state network reliability.Based on Boolean algebra theory,the algorithm generated all d-minpaths（d-mincuts） through expanding product-of-sum expression,with knowing all d-mincuts（d-minpaths） in advance,then calculated network reliability by app-lying inclusion-exclusion principle to d-minpaths or d-mincuts,whose amount was fewer.Furthermore,denoting a d-mincut or d-minpath through a set pair composed of unsaturated or nonzero edges and corresponding value,respectively,based on membership relationship between assembles and changing the assemble operation sequence from inverse-merging to merging inverse,proposed several lemmas to simplify algorithm.The proposed algorithm was efficient and effective,followed by the analysis of associated computational complexities.The provided example shows correctness and applicability of the algorithm.
出处
《计算机应用研究》
CSCD
北大核心
2011年第11期4270-4273,共4页
Application Research of Computers
基金
第二炮兵工程学院创新性探索研究项目(XY2010JJB23)
