Skip to content
返回搜索结果

推送-重贴标签算法

提出者
Andrew V. Goldberg and Robert E. Tarjan
年份
1988
类型
algorithm
类别
Graph Algorithms

本文为机器翻译,尚未经过审校。 阅读英文原文

字号

它有什么作用?

推送-重贴标签算法由Andrew V. Goldberg和Robert E. Tarjan于1988年开发,是一种计算网络最大流的高效方法。与增广路径方法不同,它维护一个预流,并使用局部推送和全局重贴标签操作将流导向汇点,从而实现了卓越的最坏情况复杂度。

方法背后的直觉

该算法为每个节点维护一个“高度”或“距离标签”,并使用预流(节点可以暂时超过汇点需求)。它反复地将多余的流从标签较高的节点推向标签较低的邻居,并重新贴标签以创建通往汇点的路径。关键在于,通过维护高度不变性和使用高效数据结构,该算法避免了像增广路径方法那样反复探索整个图。当所有多余的流都到达汇点时,算法终止。

历史学

Goldberg和Tarjan于1988年发表了他们的推送-重贴标签算法,引入了一种根本不同的最大流计算范式。他们的算法实现了O(V³)的最坏情况复杂度,优于Edmonds-Karp的O(VE²)。在随后的几十年里,开发了许多变体,包括间隙启发式(Goldberg和Tarjan,1990)、最高标签规则,以及最新的变体在实际网络上实现了近线性经验性能。

何时使用

将推送-重贴标签算法应用于计算大型稠密网络中的最大流,在这些网络中增广路径方法效率低下。它对于具有数千或数百万条边的网络特别有效。当您需要保证的多项式时间性能并希望利用现代数据结构时使用它。对于稀疏网络或教育目的,增广路径方法可能更易于理解和实现。

局限与注意事项

  • 比增广路径方法更复杂,难以理解和实现
  • 需要仔细处理数据结构(释放列表、间隙启发式)以获得最佳性能
  • 最坏情况复杂度仍高于某些针对特殊图类的专用算法
  • 与增广路径相比,对解决方案过程的直观理解较少

来源中的条件不能替代独立的科学审查或分析引擎的验证。

优势

  • 卓越的最坏情况时间复杂度:O(V³) 或 O(V²√E)(带间隙启发式)
  • 在实践中非常高效,尤其适用于大型稠密网络
  • 操作的局部性(推送/重贴标签)允许良好的缓存性能
  • 易于并行化和分布式实现
  • 针对不同问题结构有多种实现变体

应用

  • 网络路由:计算大规模通信网络中的最大吞吐量
  • 图像处理:使用最大流进行图像分割和抠图应用
  • 航空调度优化:确定复杂路由网络中的最大乘客流量
  • 电网分析:计算电力网络中的最大输电容量
  • 供应链管理:优化多层分销网络中的产品流
  • 生物网络:分析代谢和蛋白质相互作用网络中的最大流

使用方式

使用方式

1

将源节点的高度设置为顶点数,所有其他节点的高度设置为零。饱和源节点的所有出边,创建初始预流(邻近节点有剩余)。

2

反复选择一个活跃节点(有剩余流),然后将其多余流推向高度较低的邻居,或重新贴标签以增加其高度。使用高效的选择策略和释放操作来最小化迭代次数。

3

继续执行直到没有活跃节点为止,此时所有预流都已解决为从源到汇的最大流。

常见陷阱

  • 错误地实现高度更新或推送操作,导致非最大流
  • 忽略使用间隙启发式和高效节点选择,导致实际性能不佳
  • 未能正确维护预流不变性(节点上的剩余流和边上的容量约束)

常见问题

预流和流有什么区别?

预流暂时允许节点持有剩余流(流入减流出可以为正),而真正的流必须在除源点和汇点外的所有节点上守恒。当预流变为有效流时,算法终止。

高度函数的作用是什么?

高度创建了一种准距离度量:流只能从高处推向低处(从较高高度到较低高度),防止不必要的循环并确保终止。通过重新贴标签来增加高度,以便在需要时创建新路径。

什么是间隙启发式及其重要性?

间隙启发式检测何时某个高度范围内没有节点,这表明某些节点无法到达汇点。这些节点及其剩余流被快速识别和处理,显著提高了实际性能。

在实践中,推送-重贴标签算法与Edmonds-Karp算法相比如何?

推送-重贴标签算法具有更优的最坏情况复杂度,并且在大型网络上通常优于Edmonds-Karp算法,但对于小型网络或稀疏图,Edmonds-Karp算法可能更容易实现且性能具有竞争力。

相关方法

参考文献

  1. Goldberg, A. V., & Tarjan, R. E. (1988). A new approach to the maximum flow problem. Journal of the ACM, 35(4), 921-940.

    打开 DOI 文献
    已复制。
  2. Goldberg, A. V. (1998). Recent advances in maximum flow and minimum-cost flow algorithms. In Algorithm Theory (pp. 1-10). Springer, Berlin.

    打开出版物文献
    已复制。