基于不确定图的最可靠最大流的改进算法

Improved algorithm of most reliable maximum flow on uncertain graph

针对网络规模和稠密度的增大最可靠最大流SDBA算法性能下降较快的不足,提出了基于概率和割集双过滤的状态空间划分算法DF-SDBA.首先,在状态空间划分过程中使用概率约束,针对每一个待处理的区间,筛选掉下界分布概率值小于当前最可靠最大流分布的未处理区间,有效地减少了算法迭代的次数;然后,针对不确定的区间使用割集约束,即在区间上界对应的子图中求出最大流,同时求出最小割集,根据最小割集中的边必须都出现在合格子区间上界向量中这一规则,对待划分的子区间进行筛选,从而进一步减少了划分区间的数量.实验结果表明,相对于SDBA算法,DF-SDBA算法有效地减少了需要划分的区间,很大程度上克服了网络规模和稠密度对算法性能的影响,具有显著的性能优势,有效地提高了算法的适用性.

For the most reliable maximum flow problem（ MRMF）,the performance of the space decomposition-based algorithm（ SDBA） decreases rapidly with the increase in size and density of the graph. The probability filter and the cut-set filter are therefore used to solve this problem and the double filter space decomposition-based algorithm（ DF-SDBA） is proposed. First,the probability constraint is used to filter out all intervals in the process of space decomposition. For each interval to be processed,the DF-SDBA algorithm filters off the intervals of which the probability is smaller than the current maximum flow to effectively reduce the number of iterations. Then the cut-set constraint is applied to the unspecified intervals. It computes the maximum flow in the upper bound of the unspecified interval,meanw hile the minimum cut-sets are obtained. Based on the rule that all the edges in the cut-sets must exist in the upper bound of each interval,the unspecified intervals are filtered out. The experimental results show that the DF-SDBA algorithm can not only effectively reduce the number of the intervals in need of dividing,but also reduce the impact of network size and density compared with the SDBA algorithm. The DF-SDBA algorithm has significant performance advantages and improves the applicability of algorithms.