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

• 作者: 吕建华 张柏礼 杨娟 田伟
• 来源期刊: 东南大学学报（自然科学版）
• 学科: 工学
• 关键词: 不确定图 最大流 流可靠性 最小割
• 年，卷（期）: 2015,（2）
• 页码范围: 241-246
• 页数: 6页
• 分类号: TP311
• 字数: 6274字
• 语种: 中文
• DOI: 10.3969/j.issn.1001-0505.2015.02.008

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	张柏礼	东南大学计算机科学与工程学院	32	326	9.0	17.0
5	吕建华	东南大学计算机科学与工程学院	20	141	7.0	11.0
9	杨娟	东南大学计算机科学与工程学院	9	61	4.0	7.0
10	田伟		7	71	6.0	7.0