基于线性规划的图最大流问题的Push-Relabel算法中的间隙重标启发式优化求解示例 1. 问题描述 我们考虑一个有向图 \( G = (V, E) \) 上的最大流问题。其中： \( V \) 是顶点集合，\( |V| = n \)。 \( E \) 是边集合，每条有向边 \( (u, v) \in E \) 具有非负容量 \( c(u, v) \geq 0 \)。 有两个特殊顶点：源点 \( s \) 和汇点 \( t \)。 目标是找到从 \( s \) 到 \( t \) 的流 \( f: E \to \mathbb{R}^+ \)，满足： 容量约束 ：对每条边 \( (u, v) \)，满足 \( 0 \leq f(u, v) \leq c(u, v) \)。 流量守恒 ：对所有 \( u \in V \setminus \{s, t\} \)，满足 \( \sum_ {v: (u,v) \in E} f(u, v) = \sum_ {v: (v,u) \in E} f(v, u) \)。 在满足上述约束下，最大化从 \( s \) 流出的总流量，即 \( \text{value}(f) = \sum_ {v: (s,v) \in E} f(s, v) \)。 Push-Relabel 算法是求解最大流问题的高效算法之一。本示例聚焦于其核心变种之一： 间隙重标（Gap Relabeling）启发式 ，该启发式可显著加速算法收敛。我们将从线性规划的对偶视角理解算法的操作，并详细展示如何将间隙重标集成到标准 Push-Relabel 框架中。 2. 核心概念与算法基础 2.1 预流（Preflow）与高度函数 Push-Relabel 算法不保持流量守恒，而是维护一个 预流 \( f \)，满足： 容量约束。 对所有 \( u \in V \setminus \{s\} \)，有 超额流量 \( e(u) = \sum_ {v: (v,u) \in E} f(v, u) - \sum_ {v: (u,v) \in E} f(u, v) \geq 0 \)。 每个顶点 \( u \) 有一个整数 高度 \( h(u) \)，初始时 \( h(s) = n \)，\( h(u) = 0 \) 对 \( u \in V \setminus \{s\} \)。算法在运行时始终保持 高度差约束 ：如果存在从 \( u \) 到 \( v \) 的残量边（即 \( c_ f(u, v) = c(u, v) - f(u, v) > 0 \)），则必须满足 \( h(u) \leq h(v) + 1 \)。这保证了算法沿“下坡”方向推送流。 2.2 基本操作 推送（Push） ：如果顶点 \( u \) 有超额流量 \( e(u) > 0 \)，且存在残量边 \( (u, v) \) 满足 \( h(u) = h(v) + 1 \)，则沿该边推送 \( \delta = \min(e(u), c_ f(u, v)) \) 单位的流。 重标（Relabel） ：如果顶点 \( u \) 有超额流量 \( e(u) > 0 \)，但所有残量出边 \( (u, v) \) 都满足 \( h(u) \leq h(v) \)（即不存在满足推送条件的高度差），则将 \( h(u) \) 增加到 \( \min\{h(v) + 1 \mid (u,v) \text{ 是残量边}\} \)。 2.3 对偶视角 最大流问题的线性规划对偶是最小割问题。在 Push-Relabel 中，高度函数 \( h \) 可看作对偶变量。当算法终止时，满足 \( h(s) = n \)，\( h(t) = 0 \)，且所有从 \( h(u) \geq k+1 \) 的顶点到 \( h(v) \leq k \) 的顶点的边都处于饱和状态。这对应于一个值为 \( \sum_ {u: h(u) \geq k+1, v: h(v) \leq k} c(u, v) \) 的割，而最大流的值等于最小割的容量。 3. 间隙重标（Gap Relabeling）启发式 3.1 间隙现象 在算法执行过程中，高度值是离散整数。设 \( d \) 为任一高度值。如果存在某个高度 \( g \)，使得没有顶点的高度恰好为 \( g \)，但存在顶点的高度 \( > g \) 和 \( < g \)，则称高度 \( g \) 是一个 间隙（Gap） 。 3.2 间隙的性质 可以证明：一旦出现高度为 \( g \) 的间隙（且 \( 0 < g < n \)），则所有高度 \( > g \) 的顶点都无法将流送到汇点 \( t \)，因为任何从高度 \( > g \) 到高度 \( \leq g-1 \) 的路径都需要经过一个高度为 \( g \) 的顶点作为中间步骤，而这样的顶点不存在。因此，这些高度 \( > g \) 的顶点可以被“隔离”，其超额流量永远无法送到汇点。 3.3 间隙重标操作 当检测到高度 \( g \) 是一个间隙时，算法将所有高度 \( > g \) 的顶点的高度重标为 \( n+1 \)（或一个足够大的值，例如 \( n \)）。这实际上将这些顶点“抬高”，使其超额流量可以通过重标和推送操作，最终被推送回源点 \( s \)。这避免了在这些“无效”顶点上继续无用的推送和重标操作，从而加速收敛。 4. 算法步骤详解 我们考虑一个包含间隙重标的 Push-Relabel 算法实现，采用“最高标号优先”策略以进一步提升效率。 步骤 0：初始化 对每条边 \( (u, v) \in E \)，设 \( f(u, v) = 0 \)。 对每个顶点 \( u \)，设超额流量 \( e(u) = 0 \)，高度 \( h(u) = 0 \)。 对源点 \( s \)，设 \( h(s) = n \)。 对每条从 \( s \) 出发的边 \( (s, v) \)，执行饱和推送：推送 \( c(s, v) \) 单位流，即设 \( f(s, v) = c(s, v) \)，\( e(v) = c(s, v) \)，\( e(s) \) 相应减少。 初始化一个数组 \( \text{cnt}[ 0..2n-1] \) 记录每个高度的顶点数量，初始时 \( \text{cnt}[ n] = 1 \)（对应 \( s \)），\( \text{cnt}[ 0 ] = n-1 \)。 初始化一个桶结构（或优先队列），按高度组织有超额流量的顶点。 步骤 1：主循环 当存在有超额流量的非源非汇顶点时： 从最高标号的桶中选取一个顶点 \( u \)（最高标号优先策略）。 尝试对 \( u \) 执行推送操作：检查其所有残量出边 \( (u, v) \)。 如果存在边满足 \( h(u) = h(v) + 1 \) 且 \( c_ f(u, v) > 0 \)，则沿该边推送 \( \delta = \min(e(u), c_ f(u, v)) \) 单位流。更新 \( f, e, c_ f \)。 如果推送后 \( v \neq s, t \) 且 \( v \) 获得超额流量，将其加入对应高度的桶中。 如果 \( u \) 仍有超额流量但无法推送，则对 \( u \) 执行重标操作： 计算新高度 \( h_ {\text{new}} = 1 + \min\{h(v) \mid (u,v) \text{ 是残量边}\} \)。 更新高度计数：\( \text{cnt}[ h(u)] \) 减 1，\( \text{cnt}[ h_ {\text{new}} ] \) 加 1。 将 \( h(u) \) 设为 \( h_ {\text{new}} \)。 检查是否产生间隙：如果 \( \text{cnt}[ h_ {\text{old}}] = 0 \) 且 \( 0 < h_ {\text{old}} < n \)，则高度 \( h_ {\text{old}} \) 是一个间隙。执行间隙重标子程序。 步骤 2：间隙重标子程序 输入：间隙高度 \( g \)。 遍历所有顶点 \( v \in V \setminus \{s, t\} \)： 如果 \( h(v) > g \) 且 \( h(v) \leq n \)： 从高度计数中移除：\( \text{cnt}[ h(v) ] \) 减 1。 将 \( h(v) \) 设为 \( n+1 \)（或 \( n \)）。 注意：通常 \( n+1 \) 是为了确保这些顶点高度超过 \( n \)，使其在后续推送中只能将流送回 \( s \) 或同高度顶点。 由于这些顶点的高度被设为 \( n+1 \)，它们不再属于任何在 \( [ 1, n ] \) 范围内的桶，因此后续主循环不会再选取它们进行推送，除非它们被重标降低高度（这通常不会发生）。 步骤 3：终止 当除 \( s \) 和 \( t \) 外没有顶点有超额流量时，算法终止。此时的流 \( f \) 即为最大流。 5. 实例演示 考虑一个简单有向图： 顶点 \( V = \{s, a, b, t\} \) (n=4)，边与容量： \( (s, a): 3 \), \( (s, b): 2 \), \( (a, b): 2 \), \( (a, t): 2 \), \( (b, t): 3 \)。 初始化 ： \( h(s)=4, h(a)=0, h(b)=0, h(t)=0 \)。 饱和推送从 \( s \) 出发的边： \( f(s,a)=3, e(a)=3 \); \( f(s,b)=2, e(b)=2 \)。 \( e(s) = -5 \)（不存储，只关心超额流量非负的顶点）。 高度计数：cnt[ 4]=1, cnt[ 0 ]=3。 迭代 1 ：选最高标号顶点。当前只有 \( a, b \) 有超额流量，高度均为 0，选 \( a \)。 残量出边：\( (a,b) \) 容量 2, \( (a,t) \) 容量 2。检查高度：\( h(a)=0 \)，需找 \( h(v)= -1\) 的顶点，不存在。因此执行重标： 最小邻接高度：\( \min(h(b)=0, h(t)=0) = 0 \)。 新高度 \( h(a) = 1 \)。 更新计数：cnt[ 0] 减 1 变为 2，cnt[ 1 ] 加 1 变为 1。 检查间隙：旧高度 0 的计数 cnt[ 0 ]=2 ≠ 0，无间隙。 迭代 2 ：仍有超额流顶点 \( a \) (高 1) 和 \( b \) (高 0)。选最高 \( a \)。 检查残量边：\( h(a)=1 \)，需找 \( h(v)=0 \) 的邻点。存在 \( b \) 和 \( t \) 高度均为 0。 沿 \( (a,t) \) 推送：推送 \( \delta = \min(e(a)=3, c_ f(a,t)=2) = 2 \)。 更新：\( f(a,t)=2, e(a)=1, e(t)=2 \)。 \( a \) 仍有超额流量 1，继续检查残量边 \( (a,b) \)：推送 \( \delta = \min(1, 2)=1 \)。 更新：\( f(a,b)=1, e(a)=0, e(b)=3 \)。 现在 \( a \) 超额流量为 0，移出桶。 迭代 3 ：超额流顶点：\( b \) (高 0) 和 \( t \) (高 0，但汇点不处理)。选 \( b \)。 残量出边：\( (b,t) \) 容量 3 残量 3。检查高度：需找 \( h(v)=-1 \)，无。重标： 最小邻接高度：\( h(t)=0 \)。 新高度 \( h(b)=1 \)。 更新计数：cnt[ 0] 减 1 变为 1，cnt[ 1 ] 加 1 变为 2。 检查间隙：旧高度 0 的计数 cnt[ 0 ]=1 ≠ 0。 迭代 4 ：选最高标号顶点：\( b \) (高 1)。 残量边 \( (b,t) \) 满足 \( h(b)=1, h(t)=0 \)（高度差 1），推送 \( \delta = \min(e(b)=3, 3)=3 \)。 更新：\( f(b,t)=3, e(b)=0, e(t)=5 \)。 \( b \) 超额流量为 0。 迭代 5 ：此时只有汇点 \( t \) 有超额流量，但它是汇点，不参与推送/重标。检查高度计数： cnt[ 4]=1 (s), cnt[ 1]=2 (a 和 b), cnt[ 0]=1 (t)。高度 2 和 3 的计数为 0，但高度 0 和 1 都有顶点，没有形成“间隙”吗？注意间隙定义是：存在高度 \( g \) 使得 cnt[ g]=0 且存在高度 >g 和 <g 的顶点。这里高度 2 满足 cnt[ 2]=0，且存在高度 >2 的顶点（s 高度 4）和高度 <2 的顶点（a,b 高度 1，t 高度 0）。因此高度 2 是一个间隙。 执行间隙重标 ：高度 g=2。 遍历顶点：a 高度 1 ≤ 2，不动；b 高度 1 ≤ 2，不动；t 高度 0 ≤ 2，不动；s 高度 4 > 2，但 s 是源点，通常不重标（或不需处理）。实际上，只有非源非汇顶点高度 >2 才重标，这里没有这样的顶点。所以此例中间隙重标没有实际改变高度，但机制已演示。 算法实际上已结束，因为没有非源非汇顶点有超额流量。最大流值 = 进入 t 的流量 = f(a,t)+f(b,t)=2+3=5。 6. 算法复杂度与启发式效果 标准 Push-Relabel（最高标号优先）的时间复杂度为 \( O(|V|^2 \sqrt{|E|}) \)。 间隙重标启发式不改变最坏情况复杂度，但能显著减少实际运行中的重标和推送次数。一旦出现间隙，算法能立即识别并“抛弃”一些顶点，避免无效操作。 从对偶角度看，间隙重标相当于识别出对偶变量（高度）的某些值不可能对应最小割的边界，从而提前修剪搜索空间。 7. 总结 Push-Relabel 算法通过维护高度函数和预流，高效求解最大流。 间隙重标是一种启发式优化，利用高度计数数组检测“间隙”，并将高于间隙的顶点高度设为无穷大，从而避免无效计算。 该启发式易于实现，仅需额外维护高度计数数组，并在重标操作后检查计数是否为零。 结合最高标号优先策略和间隙重标，Push-Relabel 算法在实际应用中性能优异，是许多高效最大流实现的基础。 通过此例，你可以看到线性规划对偶思想如何启发出实用的启发式策略，并将理论算法进一步优化以适应实际问题。