东南大学学报（自然科学版）
東南大學學報（自然科學版）
동남대학학보（자연과학판）
JOURNAL OF SOUTHEAST UNIVERSITY
2015年
2期
241-246
,共6页
张柏礼%杨娟%吕建华%田伟
張柏禮%楊娟%呂建華%田偉
장백례%양연%려건화%전위
不确定图%最大流%流可靠性%最小割
不確定圖%最大流%流可靠性%最小割
불학정도%최대류%류가고성%최소할
uncertain graph%maximum flow%flow reliability%minimum cut
针对网络规模和稠密度的增大最可靠最大流SDBA算法性能下降较快的不足,提出了基于概率和割集双过滤的状态空间划分算法DF-SDBA.首先,在状态空间划分过程中使用概率约束,针对每一个待处理的区间,筛选掉下界分布概率值小于当前最可靠最大流分布的未处理区间,有效地减少了算法迭代的次数;然后,针对不确定的区间使用割集约束,即在区间上界对应的子图中求出最大流,同时求出最小割集,根据最小割集中的边必须都出现在合格子区间上界向量中这一规则,对待划分的子区间进行筛选,从而进一步减少了划分区间的数量.实验结果表明,相对于SDBA算法,DF-SDBA算法有效地减少了需要划分的区间,很大程度上克服了网络规模和稠密度对算法性能的影响,具有显著的性能优势,有效地提高了算法的适用性.
針對網絡規模和稠密度的增大最可靠最大流SDBA算法性能下降較快的不足,提齣瞭基于概率和割集雙過濾的狀態空間劃分算法DF-SDBA.首先,在狀態空間劃分過程中使用概率約束,針對每一箇待處理的區間,篩選掉下界分佈概率值小于噹前最可靠最大流分佈的未處理區間,有效地減少瞭算法迭代的次數;然後,針對不確定的區間使用割集約束,即在區間上界對應的子圖中求齣最大流,同時求齣最小割集,根據最小割集中的邊必鬚都齣現在閤格子區間上界嚮量中這一規則,對待劃分的子區間進行篩選,從而進一步減少瞭劃分區間的數量.實驗結果錶明,相對于SDBA算法,DF-SDBA算法有效地減少瞭需要劃分的區間,很大程度上剋服瞭網絡規模和稠密度對算法性能的影響,具有顯著的性能優勢,有效地提高瞭算法的適用性.
침대망락규모화주밀도적증대최가고최대류SDBA산법성능하강교쾌적불족,제출료기우개솔화할집쌍과려적상태공간화분산법DF-SDBA.수선,재상태공간화분과정중사용개솔약속,침대매일개대처리적구간,사선도하계분포개솔치소우당전최가고최대류분포적미처리구간,유효지감소료산법질대적차수;연후,침대불학정적구간사용할집약속,즉재구간상계대응적자도중구출최대류,동시구출최소할집,근거최소할집중적변필수도출현재합격자구간상계향량중저일규칙,대대화분적자구간진행사선,종이진일보감소료화분구간적수량.실험결과표명,상대우SDBA산법,DF-SDBA산법유효지감소료수요화분적구간,흔대정도상극복료망락규모화주밀도대산법성능적영향,구유현저적성능우세,유효지제고료산법적괄용성.
