采用节点流守恒求取多状态网络d-最小路集的改进算法  

Improved Algorithm for d-Minimal Path Set of Multistate Network Using Node Flow Conservation

作　　者：褚洪彦[1] 

机构地区：[1]南京信息职业技术学院计算机与软件学院,江苏南京210023

出　　处：《华侨大学学报（自然科学版）》2016年第4期511-514,共4页Journal of Huaqiao University(Natural Science)

基　　金：国家自然科学基金资助项目(61300122)

摘　　要：针对多状态网络可靠度的计算问题,给出一种求解多状态网络d-最小路集的改进算法.引入可行流向量,并将网络中的双向边等效为单向边,使算法对网络中边的容量取值无特殊要求,且可用于含双向边的网络,适用性更强.通过引入边的容量下确界,并将网络中的反向边等效为单向边,减少求取d-最小路集可行解时需枚举的解数目,降低算法复杂度.以多状态网络为例,进行分析验证.结果表明:该算法可以准确得到多状态网络所有d-最小路集.To consider the calculation problem of the multistate network reliability,an improved algorithm for multistate network d-minimal path set was proposed.The two-way side of the network is equivalent to one side by introducing feasible flow vector.The capacity of the edge of the network is not special required.And it can be used for a network with two sides.The algorithm is more applicable.By the introduction the capacity of the edge.The reverse side of the network is equivalent to one side.Therefore,it educe the the viable solution enumerated number of the d-minimal path set,and the complexity of the algorithm.To verify the results,it shows that the proposed algorithm can acuurately obtain all d-minimal path set of the multistate network.

关 键 词：网络可靠度 多状态网络 最小路集 可行流向量 

分 类 号：O213.2[理学—概率论与数理统计]