网络最大流的自适应求解算法——SAPR算法  

Self-adaptive algorithm for network maximum flow problem: SAPR algorithm

作　　者：江锦成[1] 吴立新[2,3] 杨宜舟[3] 李志锋[1] 

机构地区：[1]北京师范大学民政部/教育部减灾与应急管理研究院,北京100875 [2]中国矿业大学物联网中心,江苏徐州221116 [3]东北大学测绘遥感与数字矿山研究所,沈阳110819

出　　处：《计算机应用研究》2014年第10期2969-2973,共5页Application Research of Computers

基　　金：国家"863"计划资助项目(2011AA120302)

摘　　要：为提升对大规模不同拓扑结构网络的求解速度,通过评估基本操作的执行效率、动态调整活跃顶点的选择方式及盈余流的推进方式,提出了一种可高效求解多类拓扑网络的自适应预流推进算法——SAPR(self-adaptive push-relabel)算法。在The First DIMACS implementation Challenge提供的七类不同拓扑结构网络上,对SAPR算法及四种适用于特定拓扑网络的算法进行了对比实验,结果表明:SAPR算法在一半的数据上能持平高效的H_PRF算法,而另一半能超越H_PRF算法。SAPR算法的高效性和强稳定性解决了传统算法在多类拓扑网络中不能都取得高效率的问题。In order to improve the calculating speed for different topological networks, this paper proposed an adaptive algo- rithm, named SAPR algorithm, by the way of changing the choices of active nodes and the treatment of excess flow dynamical- ly. It compared with four typical algorithms which were suitable for special topological networks, it tested SAPR algorithm on seven kinds of network provided by the first dimacs implementation challenge. The experimental results demonstrate that the SAPR algorithm performances well for all tested networks with good applicability, and better than H_PRF algorithm on half of networks.

关 键 词：最大流 自适应 预流推进 网络分析 H_PRF算法 动态 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]