|
|||||
|
|
| 基于不确定图的最可靠最大流的改进算法 | |
| 引用本文： | 张柏礼,杨娟,吕建华,田伟. 基于不确定图的最可靠最大流的改进算法[J]. 东南大学学报(自然科学版), 2015, 45(2): 241-246 |
| 作者姓名： | 张柏礼 杨娟 吕建华 田伟 |
| 作者单位： | 1. 东南大学计算机科学与工程学院,南京211189;东南大学计算机网络和信息集成教育部重点实验室,南京211189 2. 东南大学计算机科学与工程学院,南京,211189 3. 南京弘毅电气自动化有限公司,南京,210039 |
| 基金项目： | 国家自然科学基金资助项目 |
| 摘 要： | 针对网络规模和稠密度的增大最可靠最大流SDBA算法性能下降较快的不足,提出了基于概率和割集双过滤的状态空间划分算法DF-SDBA.首先,在状态空间划分过程中使用概率约束,针对每一个待处理的区间,筛选掉下界分布概率值小于当前最可靠最大流分布的未处理区间,有效地减少了算法迭代的次数;然后,针对不确定的区间使用割集约束,即在区间上界对应的子图中求出最大流,同时求出最小割集,根据最小割集中的边必须都出现在合格子区间上界向量中这一规则,对待划分的子区间进行筛选,从而进一步减少了划分区间的数量.实验结果表明,相对于SDBA算法,DF-SDBA算法有效地减少了需要划分的区间,很大程度上克服了网络规模和稠密度对算法性能的影响,具有显著的性能优势,有效地提高了算法的适用性. |
| 关 键 词： | 不确定图 最大流 流可靠性 最小割 |
Improved algorithm of most reliable maximum flow on uncertain graph |
|
| Zhang Baili , Yang Juan , Lü Jianhua , Tian Wei. Improved algorithm of most reliable maximum flow on uncertain graph[J]. Journal of Southeast University(Natural Science Edition), 2015, 45(2): 241-246 | |
| Authors: | Zhang Baili Yang Juan Lü Jianhua Tian Wei |
| Abstract: | |
| Keywords: | uncertain graph maximum flow flow reliability minimum cut |
| 本文献已被 CNKI 万方数据 等数据库收录！ | |