基于MDD的多状态网络二端可靠性算法

An MDD-based algorithm for computing multi-state two-terminal reliability

为解决多状态网络二端可靠性问题,提出了多值离散概率模型MDD_WS2TR,基于该模型给出了MFMC_MDD算法。该算法基于最大流最小割思想,对最小割中的边进行合并,过滤掉稠密网络中无关紧要的边,降低了计算量。在构建网络MDD的过程中,定义了操作算子TBoolean,该算子对MDD进行剪枝,压缩了最大流的状态组合空间,降低了MDD之间进行合并操作的复杂度。在一组随机流网络图上对MFMC_MDD算法进行测试,验证了MFMC_MDD算法的有效性。

In order to compute the multi-state two-terminal reliability,a multi-valued discrete probability model MDD_WS2TR is defined.MFMC_MDD algorithm based on max-flow min-cut theorem is proposed,which combines the edges in the minimal cuts without considering the insignificant edge in the dense network.Especially,in the process of building MDD of the network,the operator TBoolean is defined to prune the MDD.Then the state space is compressed and the complexity of merging MDD is reduced.Finally MFMC_MDD algorithm is tested on a group of stochastic flow networks.The experimental results show that the proposed algorithm is effective.