-
题名基于预流推进的最小标号最大流算法
被引量:4
- 1
-
-
作者
赵礼峰
严子恒
-
机构
南京邮电大学理学院
-
出处
《计算机应用》
CSCD
北大核心
2015年第12期3398-3402,3407,共6页
-
文摘
针对原始最高标号预流推进算法中的回溯现象导致其在部分网络中执行效率低下的问题,提出了基于预流推进的最小标号算法。该算法仍以预流推进为基础,但在选取活跃节点时依据贪心原则寻找最小标号活跃节点作为调整点,同时还需构造回溯检验方法终止回溯现象以提升算法效率。在仿真实验中,该算法能够适应各类复杂网络,并在稀疏网络中具有最高标号预流推进算法5倍以上执行速度;在被应用于图像分割领域时,该算法也具有50%以上性能提升。提出的基于预流推进的最小标号最大流算法能够满足大规模网络流量分配、计算机视觉图像处理等需求。
-
关键词
预流推进
最高标号
最小标号
回溯
随机网络
-
Keywords
preflow push
highest label
lowest label
backtracking
random network
-
分类号
TP301.6
[自动化与计算机技术—计算机系统结构]
-
-
题名网络最大流的自适应求解算法——SAPR算法
被引量:4
- 2
-
-
作者
江锦成
吴立新
杨宜舟
李志锋
-
机构
北京师范大学民政部/教育部减灾与应急管理研究院
中国矿业大学物联网中心
东北大学测绘遥感与数字矿山研究所
-
出处
《计算机应用研究》
CSCD
北大核心
2014年第10期2969-2973,共5页
-
基金
国家"863"计划资助项目(2011AA120302)
-
文摘
为提升对大规模不同拓扑结构网络的求解速度,通过评估基本操作的执行效率、动态调整活跃顶点的选择方式及盈余流的推进方式,提出了一种可高效求解多类拓扑网络的自适应预流推进算法——SAPR(self-adaptive push-relabel)算法。在The First DIMACS implementation Challenge提供的七类不同拓扑结构网络上,对SAPR算法及四种适用于特定拓扑网络的算法进行了对比实验,结果表明:SAPR算法在一半的数据上能持平高效的H_PRF算法,而另一半能超越H_PRF算法。SAPR算法的高效性和强稳定性解决了传统算法在多类拓扑网络中不能都取得高效率的问题。
-
关键词
最大流
自适应
预流推进
网络分析
H_PRF算法
动态
-
Keywords
maximum flow
self-adaptive
push-relabel
network analysis
H_PRF algorithm
dynamic
-
分类号
TP301.6
[自动化与计算机技术—计算机系统结构]
-
-
题名一个新的最大流问题增载轨算法
被引量:10
- 3
-
-
作者
张宪超
江贺
-
机构
大连理工大学软件学院
-
出处
《小型微型计算机系统》
CSCD
北大核心
2006年第9期1726-1730,共5页
-
基金
国家自然科学基金项目(60503003)资助.
-
文摘
通过放松Ahujia和Orlin算法的约束,给出了一个新的增载轨算法.该算法实质上提供了一个构造、阻塞无环网络的策略,它可以在每次构造无环网络中得到更多的增载轨.从而进一步降低了找到每条增载轨的代价.实验表明,新的算法比Dinic算法快2~5倍,和目前实验性能最好的预流推进算法基本相近.说明增载轨类算法在实际性能方面未必落后于预流推进类算法.
-
关键词
最大流
增载轨算法
预流推进算法
实验性能
-
Keywords
maximum flow
augmenting path algorithm
pre-flow push algorithm
empirical performance
-
分类号
TP301.6
[自动化与计算机技术—计算机系统结构]
-