推送-重贴标签算法
- 提出者
- 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)(带间隙启发式)
- 在实践中非常高效,尤其适用于大型稠密网络
- 操作的局部性(推送/重贴标签)允许良好的缓存性能
- 易于并行化和分布式实现
- 针对不同问题结构有多种实现变体
应用
- 网络路由:计算大规模通信网络中的最大吞吐量
- 图像处理:使用最大流进行图像分割和抠图应用
- 航空调度优化:确定复杂路由网络中的最大乘客流量
- 电网分析:计算电力网络中的最大输电容量
- 供应链管理:优化多层分销网络中的产品流
- 生物网络:分析代谢和蛋白质相互作用网络中的最大流
使用方式
使用方式
将源节点的高度设置为顶点数,所有其他节点的高度设置为零。饱和源节点的所有出边,创建初始预流(邻近节点有剩余)。
反复选择一个活跃节点(有剩余流),然后将其多余流推向高度较低的邻居,或重新贴标签以增加其高度。使用高效的选择策略和释放操作来最小化迭代次数。
继续执行直到没有活跃节点为止,此时所有预流都已解决为从源到汇的最大流。
常见陷阱
- 错误地实现高度更新或推送操作,导致非最大流
- 忽略使用间隙启发式和高效节点选择,导致实际性能不佳
- 未能正确维护预流不变性(节点上的剩余流和边上的容量约束)
常见问题
预流和流有什么区别?
预流暂时允许节点持有剩余流(流入减流出可以为正),而真正的流必须在除源点和汇点外的所有节点上守恒。当预流变为有效流时,算法终止。
高度函数的作用是什么?
高度创建了一种准距离度量:流只能从高处推向低处(从较高高度到较低高度),防止不必要的循环并确保终止。通过重新贴标签来增加高度,以便在需要时创建新路径。
什么是间隙启发式及其重要性?
间隙启发式检测何时某个高度范围内没有节点,这表明某些节点无法到达汇点。这些节点及其剩余流被快速识别和处理,显著提高了实际性能。
在实践中,推送-重贴标签算法与Edmonds-Karp算法相比如何?
推送-重贴标签算法具有更优的最坏情况复杂度,并且在大型网络上通常优于Edmonds-Karp算法,但对于小型网络或稀疏图,Edmonds-Karp算法可能更容易实现且性能具有竞争力。