计算机应用研究
計算機應用研究
계산궤응용연구
APPLICATION RESEARCH OF COMPUTERS
2014年
10期
2969-2973
,共5页
江锦成%吴立新%杨宜舟%李志锋
江錦成%吳立新%楊宜舟%李誌鋒
강금성%오립신%양의주%리지봉
最大流%自适应%预流推进%网络分析%H_PRF算法%动态
最大流%自適應%預流推進%網絡分析%H_PRF算法%動態
최대류%자괄응%예류추진%망락분석%H_PRF산법%동태
maximum flow%self-adaptive%push-relabel%network analysis%H_PRF algorithm%dynamic
为提升对大规模不同拓扑结构网络的求解速度,通过评估基本操作的执行效率、动态调整活跃顶点的选择方式及盈余流的推进方式,提出了一种可高效求解多类拓扑网络的自适应预流推进算法——SAPR(self-adaptive push-relabel)算法.在The First DIMACS implementation Challenge提供的七类不同拓扑结构网络上,对SAPR算法及四种适用于特定拓扑网络的算法进行了对比实验,结果表明:SAPR算法在一半的数据上能持平高效的H_PRF算法,而另一半能超越H_PRF算法.SAPR算法的高效性和强稳定性解决了传统算法在多类拓扑网络中不能都取得高效率的问题.
為提升對大規模不同拓撲結構網絡的求解速度,通過評估基本操作的執行效率、動態調整活躍頂點的選擇方式及盈餘流的推進方式,提齣瞭一種可高效求解多類拓撲網絡的自適應預流推進算法——SAPR(self-adaptive push-relabel)算法.在The First DIMACS implementation Challenge提供的七類不同拓撲結構網絡上,對SAPR算法及四種適用于特定拓撲網絡的算法進行瞭對比實驗,結果錶明:SAPR算法在一半的數據上能持平高效的H_PRF算法,而另一半能超越H_PRF算法.SAPR算法的高效性和彊穩定性解決瞭傳統算法在多類拓撲網絡中不能都取得高效率的問題.
위제승대대규모불동탁복결구망락적구해속도,통과평고기본조작적집행효솔、동태조정활약정점적선택방식급영여류적추진방식,제출료일충가고효구해다류탁복망락적자괄응예류추진산법——SAPR(self-adaptive push-relabel)산법.재The First DIMACS implementation Challenge제공적칠류불동탁복결구망락상,대SAPR산법급사충괄용우특정탁복망락적산법진행료대비실험,결과표명:SAPR산법재일반적수거상능지평고효적H_PRF산법,이령일반능초월H_PRF산법.SAPR산법적고효성화강은정성해결료전통산법재다류탁복망락중불능도취득고효솔적문제.
