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

摘要：

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

关键词：不确定图、最大流、流可靠性、最小割

所属期刊栏目：45

分类号：TP311(计算技术、计算机技术)

资助基金：国家自然科学基金资助项目61300200,61232007,61073059

在线出版日期：2015-05-29（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：241-246