摘要
为提升对大规模不同拓扑结构网络的求解速度,通过评估基本操作的执行效率、动态调整活跃顶点的选择方式及盈余流的推进方式,提出了一种可高效求解多类拓扑网络的自适应预流推进算法——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.
出处
《计算机应用研究》
CSCD
北大核心
2014年第10期2969-2973,共5页
Application Research of Computers
基金
国家"863"计划资助项目(2011AA120302)
