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

针对多状态网络可靠度的计算问题,给出一种求解多状态网络d-最小路集的改进算法.引入可行流向量,并将网络中的双向边等效为单向边,使算法对网络中边的容量取值无特殊要求,且可用于含双向边的网络,适用性更强.通过引入边的容量下确界,并将网络中的反向边等效为单向边,减少求取d-最小路集可行解时需枚举的解数目,降低算法复杂度.以多状态网络为例,进行分析验证.结果表明:该算法可以准确得到多状态网络所有d-最小路集.

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

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.