基于线性规划的“有向无环图（DAG）最长路径”问题的动态规划与线性规划建模求解示例 题目描述 考虑一个有向无环图（Directed Acyclic Graph, DAG）\( G = (V, E) \)，其中 \( V = \{1, 2, \dots, n\} \) 是顶点集合，\( E \) 是边的集合。每条边 \( (i, j) \in E \) 都有一个实数权重（或长度）\( w_ {ij} \)。我们定义一条路径的长度为路径上所有边的权重之和。问题是：在 DAG 中寻找一条从源点 \( s \) 到汇点 \( t \) （其中 \( s, t \in V \)）的最长路径（即权重和最大的路径）。如果图中存在正权重回路，最长路径问题是 NP-Hard 的，但由于给定的是 DAG（无回路），该问题可以在多项式时间内求解。本题目将展示两种求解方法：一种是经典的动态规划（拓扑排序）方法，另一种是将其建模为一个线性规划问题并求解。我们将比较这两种方法的内在联系。 解题过程 步骤1：理解问题与动态规划解法 在 DAG 中，由于没有有向环，我们可以对顶点进行拓扑排序，使得所有边都从排在前面的顶点指向后面的顶点。设 \( \text{dist}[ v ] \) 表示从源点 \( s \) 到顶点 \( v \) 的最长路径长度。动态规划递推关系为： \[ \text{dist}[ v] = \max_ {(u, v) \in E} \left( \text{dist}[ u] + w_ {u v} \right) \] 其中 \( \text{dist}[ s] = 0 \)。按照拓扑顺序依次计算每个顶点的 \( \text{dist}[ \cdot] \)，最后 \( \text{dist}[ t ] \) 即为最长路径长度。路径本身可以通过记录前驱节点回溯得到。 示例图 ： 考虑一个简单的 DAG：顶点集 \( V = \{1, 2, 3, 4\} \)，边集和权重为： \( (1, 2) \) 权重 3 \( (1, 3) \) 权重 2 \( (2, 4) \) 权重 4 \( (3, 4) \) 权重 5 设源点 \( s = 1 \)，汇点 \( t = 4 \)。 动态规划求解： 拓扑顺序：1, 2, 3, 4。 \( \text{dist}[ 1 ] = 0 \)。 \( \text{dist}[ 2] = \text{dist}[ 1] + w_ {12} = 0 + 3 = 3 \)。 \( \text{dist}[ 3] = \text{dist}[ 1] + w_ {13} = 0 + 2 = 2 \)。 \( \text{dist}[ 4] = \max(\text{dist}[ 2] + w_ {24}, \text{dist}[ 3] + w_ {34}) = \max(3+4, 2+5) = \max(7, 7) = 7 \)。 最长路径长度为 7，路径有两条：1→2→4 和 1→3→4。 步骤2：线性规划建模 我们引入变量 \( d_ v \) 表示从源点 \( s \) 到顶点 \( v \) 的最长路径长度的 下界 。对于每条边 \( (u, v) \in E \)，如果有一条路径经过该边到达 \( v \)，那么 \( d_ v \) 至少是 \( d_ u + w_ {uv} \)。为了最大化从 \( s \) 到 \( t \) 的路径长度，我们建立如下线性规划模型： 决策变量：\( d_ v \) 对每个顶点 \( v \in V \)（连续变量）。 目标：最大化 \( d_ t - d_ s \)。由于 \( d_ s \) 可以固定为 0（通过约束），目标等价于最大化 \( d_ t \)。 约束： 对每条边 \( (u, v) \in E \)：\( d_ v \geq d_ u + w_ {uv} \)（这称为三角不等式或最长路径约束）。 为消除平移不变性（所有 \( d_ v \) 同时加一个常数不影响约束），我们固定 \( d_ s = 0 \)。 变量 \( d_ v \) 可以是任意实数（无非负要求，因为权重可能为负）。 线性规划模型（LP）： \[ \begin{aligned} \max \quad & d_ t \\ \text{s.t.} \quad & d_ v - d_ u \geq w_ {uv}, \quad \forall (u, v) \in E, \\ & d_ s = 0, \\ & d_ v \in \mathbb{R}, \quad \forall v \in V. \end{aligned} \] 注意 ：此模型是 DAG 最长路径问题的线性规划松弛。实际上，由于 DAG 无环，该线性规划的最优解正好给出最长路径长度，并且可以取到整数解（如果权重为整数，\( d_ v \) 也为整数）。对于有正环的图，此模型无上界（无解）；对于有负环的最短路径问题，则需要改变不等号方向。 步骤3：将示例图建模为线性规划 对于示例图，设变量 \( d_ 1, d_ 2, d_ 3, d_ 4 \)。LP 模型为： \[ \begin{aligned} \max \quad & d_ 4 \\ \text{s.t.} \quad & d_ 2 - d_ 1 \geq 3 \quad (\text{边 } (1,2)), \\ & d_ 3 - d_ 1 \geq 2 \quad (\text{边 } (1,3)), \\ & d_ 4 - d_ 2 \geq 4 \quad (\text{边 } (2,4)), \\ & d_ 4 - d_ 3 \geq 5 \quad (\text{边 } (3,4)), \\ & d_ 1 = 0, \\ & d_ 1, d_ 2, d_ 3, d_ 4 \in \mathbb{R}. \end{aligned} \] 步骤4：求解线性规划 我们将约束改写为： \( d_ 2 \geq d_ 1 + 3 = 3 \) （因为 \( d_ 1 = 0 \)） \( d_ 3 \geq d_ 1 + 2 = 2 \) \( d_ 4 \geq d_ 2 + 4 \geq 3 + 4 = 7 \) \( d_ 4 \geq d_ 3 + 5 \geq 2 + 5 = 7 \) 为了最大化 \( d_ 4 \)，我们应尽可能增大 \( d_ 2 \) 和 \( d_ 3 \)，但增大 \( d_ 2 \) 不会影响 \( d_ 4 \) 的下界（因为约束是 \( d_ 4 \geq d_ 2+4 \)），但 \( d_ 2 \) 本身没有上界。然而，由于目标只涉及 \( d_ 4 \)，且 \( d_ 4 \) 受 \( d_ 2 \) 和 \( d_ 3 \) 约束，实际上最优解会在某些约束取等号时达到。观察约束： 要使 \( d_ 4 \) 尽可能大，我们希望 \( d_ 4 \) 尽可能大，但约束给出了下界。实际上，在最优解中，\( d_ 4 \) 将等于其下界，因为增加 \( d_ 4 \) 会违反约束 \( d_ 4 \geq d_ 2+4 \) 或 \( d_ 4 \geq d_ 3+5 \) 吗？不，增加 \( d_ 4 \) 不会违反这些约束，因为它们是 \( d_ 4 \geq \cdots \)。但目标最大化 \( d_ 4 \)，所以 \( d_ 4 \) 可以无限增大，除非有其他约束限制上界。这里没有上界约束，模型似乎是无界的？但这与已知最长路径长度 7 矛盾。 检查建模错误 ：在 DAG 最长路径问题中，我们实际上要模拟的是“沿着某条路径”的长度，即 \( d_ v \) 表示从 \( s \) 到 \( v \) 的某条路径的长度。但我们的约束 \( d_ v \geq d_ u + w_ {uv} \) 对每条边都成立，这意味着 \( d_ v \) 至少是所有进入边的 \( d_ u + w_ {uv} \) 的最大值。这正是动态规划中的递推式！但为什么模型会无界？因为如果 \( d_ 2 \) 可以无限增大，那么 \( d_ 4 \geq d_ 2+4 \) 也会无限增大，目标 \( d_ 4 \) 就无界。然而，在 DAG 中，由于无环，\( d_ 2 \) 本身也受其前驱约束。这里 \( d_ 2 \) 的唯一前驱是 \( d_ 1 \)，且 \( d_ 2 \geq d_ 1+3 = 3 \)，但 \( d_ 2 \) 可以大于 3 吗？约束只给出了下界，没有上界。所以 \( d_ 2 \) 可以取任意大于等于 3 的值，导致 \( d_ 4 \) 无界。 修正 ：在最长路径问题中，我们实际上要求 \( d_ v \) 是“从 \( s \) 到 \( v \) 的某条路径的长度”，这意味着 \( d_ v \) 应等于所有可能路径中的最大值，而不只是一个下界。但线性规划中我们只能用不等式约束。如何保证 \( d_ v \) 不会过大？我们需要增加约束：\( d_ v \) 不应超过从 \( s \) 到 \( v \) 的最长路径长度。但这是我们要优化的目标，不能直接作为约束。 正确建模 ：实际上，对于 DAG 最长路径，经典的线性规划模型是 对偶 于动态规划递推的。考虑原始问题为：我们想给每条边分配一个“流量”，使得形成一条从 \( s \) 到 \( t \) 的路径。但更优雅的建模是使用“差分约束”系统，并最大化 \( d_ t - d_ s \)。但为了防止无界，我们注意到，在 DAG 中，如果我们按照拓扑顺序处理，可以增加约束：对于每条边 \( (u,v) \)，有 \( d_ v \leq d_ u + w_ {uv} \)？不对，那会变成最短路径。 关键点 ：在 DAG 最长路径的线性规划模型中，我们实际上要 最小化 \( d_ t - d_ s \)，但约束是 \( d_ v \geq d_ u + w_ {uv} \)。这会产生无界解，因为我们可以无限增加 \( d_ v \)。然而，如果我们考虑对偶问题，就会发现对偶问题正是寻找从 \( s \) 到 \( t \) 的一条路径，使得路径权重和最大。让我们写出原问题的对偶。 原问题（Primal）： \[ \begin{aligned} \max \quad & d_ t - d_ s \\ \text{s.t.} \quad & d_ v - d_ u \geq w_ {uv}, \quad \forall (u,v) \in E, \\ & d_ v \in \mathbb{R}. \end{aligned} \] （这里我们不固定 \( d_ s=0 \)，因为对偶会更清晰。） 引入非负变量 \( x_ {uv} \geq 0 \) 对应于每个约束 \( d_ v - d_ u \geq w_ {uv} \)。根据线性规划对偶理论，原问题的对偶为： \[ \begin{aligned} \min \quad & \sum_ {(u,v) \in E} w_ {uv} x_ {uv} \\ \text{s.t.} \quad & \sum_ {v: (u,v) \in E} x_ {uv} - \sum_ {v: (v,u) \in E} x_ {vu} = \begin{cases} 1, & u = t \\ -1, & u = s \\ 0, & \text{否则} \end{cases}, \\ & x_ {uv} \geq 0, \quad \forall (u,v) \in E. \end{aligned} \] 这正是一个 单位流 从 \( s \) 到 \( t \) 的流模型，变量 \( x_ {uv} \) 表示边上的流量。由于是 DAG，基本可行解对应一条从 \( s \) 到 \( t \) 的路径（因为无环，流分解为路径流，且流量为 1）。对偶目标是最小化 \( \sum w_ {uv} x_ {uv} \)，即路径总权重。由于权重可正可负，最小化权重和等价于找一条从 \( s \) 到 \( t \) 的路径，使得 \( \sum w_ {uv} \) 最小。但我们原问题是要最大化最长路径，所以我们对所有权重取负，即设 \( w' {uv} = -w {uv} \)，则最小化 \( \sum w' {uv} x {uv} \) 等价于最大化 \( \sum w_ {uv} x_ {uv} \)。因此，通过对偶，我们将最长路径问题转化为在 DAG 上寻找最短路径（对负权重），可以用动态规划（拓扑排序）求解。 为了直接建立最长路径的线性规划 ，我们可以将目标设为最大化 \( d_ t \)，并添加约束 \( d_ s = 0 \) 和 \( d_ v \geq d_ u + w_ {uv} \)。虽然这看起来无界，但如果我们按照拓扑顺序处理，可以证明最优解中每个 \( d_ v \) 都会取到其 紧的下界 ，即 \( d_ v = \max_ {(u,v) \in E} (d_ u + w_ {uv}) \)。因为如果有某个 \( d_ v \) 严格大于其所有入边的 \( d_ u + w_ {uv} \)，那么我们可以降低 \( d_ v \) 而不违反约束，同时可能增加目标？不，降低 \( d_ v \) 可能会违反以 \( v \) 为起点的边的约束（因为 \( d_ j \geq d_ v + w_ {vj} \)），但如果我们从汇点 \( t \) 往前推，可以调整。实际上，对于 DAG，此线性规划有无穷多最优解，但最优值 \( d_ t \) 是唯一的，等于最长路径长度。例如，在示例中，取 \( d_ 1=0, d_ 2=3, d_ 3=2, d_ 4=7 \) 是一个可行解，目标值 7。如果我们令 \( d_ 2=100 \)，则为了满足 \( d_ 4 \geq d_ 2+4=104 \)，且 \( d_ 4 \geq d_ 3+5 \)，我们可以取 \( d_ 4=104 \)，目标值 104 更大。但这是否允许？检查约束：\( d_ 4 \geq d_ 2+4=104 \) 和 \( d_ 4 \geq d_ 3+5 \)。但 \( d_ 3 \) 没有约束与 \( d_ 2 \) 相关，所以我们可以取 \( d_ 3=2 \)，那么 \( d_ 4 \geq 2+5=7 \)，所以我们取 \( d_ 4=104 \) 是可行的，且目标值 104 大于 7。这显然不对，因为最长路径只有 7。 错误在哪里 ？当我们增加 \( d_ 2 \) 到 100 时，必须检查边 (2,4) 的约束：\( d_ 4 \geq d_ 2+4=104 \)。但还要检查边 (3,4)：\( d_ 4 \geq d_ 3+5 \)。如果我们取 \( d_ 3=2 \)，那么 \( d_ 4 \) 必须同时满足 \( \geq 104 \) 和 \( \geq 7 \)，所以 \( d_ 4 \) 至少 104，没问题。但这样目标值变为 104，似乎得到更长的路径？然而，这并不对应实际路径，因为从 \( s \) 到 \( t \) 的路径长度是固定的，不会因为 \( d_ 2 \) 增大而增大。问题在于，我们误解了 \( d_ v \) 的含义：在正确的模型中，\( d_ v \) 应表示从 \( s \) 到 \( v \) 的最长路径长度，它必须同时满足所有入边的约束，并且应该是满足这些约束的 最小值 ？不，最长路径应该是最大值。实际上，动态规划的递推式 \( d_ v = \max_ {(u,v) \in E} (d_ u + w_ {uv}) \) 表明，\( d_ v \) 是满足 \( d_ v \geq d_ u + w_ {uv} \) 且尽可能小的值？不对，应该是尽可能大的值，但由前驱决定。在 DAG 中，如果按照拓扑序计算，\( d_ v \) 被其前驱的 \( d_ u \) 决定。但在线性规划中，如果我们只要求 \( d_ v \geq d_ u + w_ {uv} \)，那么我们可以任意增大 \( d_ v \)，但增大会影响以 \( v \) 为起点的边的约束：\( d_ j \geq d_ v + w_ {vj} \)，这可能会迫使 \( d_ j \) 更大，从而可能使目标 \( d_ t \) 更大。但在 DAG 中，从 \( v \) 出发的边只能指向拓扑序后面的顶点，最终会影响 \( t \)。所以，如果我们任意增大 \( d_ 2 \)，为了满足边 (2,4)，\( d_ 4 \) 必须至少增大，从而目标 \( d_ 4 \) 增大。但这样得到的目标值 104 对应什么路径？实际上，不存在从 1 到 4 的路径长度为 104。这揭示了一个关键点：线性规划模型 \( \max d_ t, \text{ s.t. } d_ v \geq d_ u + w_ {uv}, d_ s=0 \) 在 DAG 中确实会给出无界解，除非权重全非正。因为我们可以沿着一条路径反复增加 \( d_ v \) 的值（但 DAG 无环，不能反复）。然而，我们可以从 \( s \) 到 \( t \) 找到一条路径，然后增加路径上所有顶点的 \( d \) 值，同时保持约束成立。例如，在路径 1→2→4 上，我们可以设 \( d_ 1=0, d_ 2=3+\Delta, d_ 4=7+\Delta \)，其中 \( \Delta > 0 \)。检查约束： 边 (1,2): \( d_ 2 \geq d_ 1+3 \) → \( 3+\Delta \geq 3 \) ✓ 边 (2,4): \( d_ 4 \geq d_ 2+4 \) → \( 7+\Delta \geq (3+\Delta)+4 = 7+\Delta \) ✓ (取等号) 边 (1,3): \( d_ 3 \geq d_ 1+2 \) → 我们可取 \( d_ 3=2 \) 边 (3,4): \( d_ 4 \geq d_ 3+5 \) → \( 7+\Delta \geq 2+5=7 \) ✓ 所以对所有 \( \Delta \geq 0 \)，这都是可行解，且目标值 \( d_ 4=7+\Delta \) 可以任意大。因此模型无界。这显然不是我们想要的最长路径。 结论 ：直接最大化 \( d_ t \) 的线性规划模型是 错误 的，因为它允许“虚增”路径长度。正确的线性规划建模应通过 对偶 来实现，即我们建模为寻找一条从 \( s \) 到 \( t \) 的路径，使得总权重最大。这可以表示为一个网络流问题，变量 \( x_ {uv} \in \{0,1\} \) 表示边是否在路径上，约束为流平衡。但这是整数规划（0-1 规划）。由于 DAG 无环，该整数规划的线性松弛是紧的（最优解为整数），因此我们可以求解线性规划松弛得到最长路径。模型如下： 变量：\( x_ {uv} \geq 0 \) 对每条边 \( (u,v) \in E \)。 目标：最大化 \( \sum_ {(u,v) \in E} w_ {uv} x_ {uv} \)。 约束： 流平衡：对每个顶点 \( v \in V \)， \[ \sum_ {u: (u,v) \in E} x_ {uv} - \sum_ {u: (v,u) \in E} x_ {vu} = \begin{cases} 1, & v = s \\ -1, & v = t \\ 0, & \text{否则} \end{cases}. \] 非负：\( x_ {uv} \geq 0 \)。 由于是 DAG，该线性规划的最优解中 \( x_ {uv} \) 会自动取 0 或 1（因为系数矩阵是全单模的），即对应一条从 \( s \) 到 \( t \) 的路径。 步骤5：用流模型求解示例 对示例图，建立流模型： 变量：\( x_ {12}, x_ {13}, x_ {24}, x_ {34} \geq 0 \)。 目标：最大化 \( 3x_ {12} + 2x_ {13} + 4x_ {24} + 5x_ {34} \)。 约束： 对顶点 1 (s)：流出 - 流入 = 1 → \( (x_ {12}+x_ {13}) - 0 = 1 \)。 对顶点 2：流出 - 流入 = 0 → \( x_ {24} - x_ {12} = 0 \)。 对顶点 3：流出 - 流入 = 0 → \( x_ {34} - x_ {13} = 0 \)。 对顶点 4 (t)：流出 - 流入 = -1 → \( 0 - (x_ {24}+x_ {34}) = -1 \) 即 \( x_ {24}+x_ {34}=1 \)。 此外，\( x \geq 0 \)。 求解：从约束可得 \( x_ {12} = x_ {24} \)，\( x_ {13} = x_ {34} \)，且 \( x_ {12}+x_ {13}=1 \)，\( x_ {24}+x_ {34}=1 \)（相同）。所以系统有多个解。目标函数：\( 3x_ {12}+2x_ {13}+4x_ {24}+5x_ {34} = 3x_ {12}+2(1-x_ {12})+4x_ {12}+5(1-x_ {12}) = (3x_ {12}+2-2x_ {12}+4x_ {12}+5-5x_ {12}) = (0\cdot x_ {12} + 7) = 7 \)。所以无论 \( x_ {12} \) 取何值，目标值都是 7。但要求 \( x_ {12} \in [ 0,1] \)，且 \( x_ {13}=1-x_ {12} \)。当 \( x_ {12}=1, x_ {13}=0, x_ {24}=1, x_ {34}=0 \) 时，对应路径 1→2→4；当 \( x_ {12}=0, x_ {13}=1, x_ {24}=0, x_ {34}=1 \) 时，对应路径 1→3→4。两种解都是最优，目标值 7。 步骤6：比较动态规划与线性规划 动态规划直接利用拓扑序递推，时间复杂度 O(|V|+|E|)。线性规划（流模型）可用单纯形法或网络流算法求解，由于全单模性，可得到整数解。两种方法本质相通：动态规划的递推式对应线性规划的对偶变量 \( d_ v \)（即最短路径中的距离标签），而流模型是原始问题。实际上，最长路径问题的线性规划对偶正是我们最初写的“无界”模型，但通过对偶可以知道，原始问题的最优值等于对偶问题的最优值，且对偶问题中 \( d_ t - d_ s \) 的最大值等于最长路径长度，但需要在对偶问题中添加约束防止无界。如何防止？在对偶问题中，我们隐含了 \( d_ s=0 \) 和 \( d_ v \) 是拓扑序的，但线性规划本身无界是因为没有上界约束。如果我们强制 \( d_ v \leq \max_ {(u,v) \in E} (d_ u + w_ {uv}) \)，那就会变成等式。然而，线性规划中我们通常不这样加约束。实际求解时，我们应使用流模型（原始），或使用动态规划。 总结 DAG 最长路径问题可用动态规划（拓扑排序）高效求解。 可建模为线性规划（流模型），变量为边上的流，约束为从 s 到 t 的单位流，目标为最大化路径权重和。由于 DAG 的全单模性，线性规划松弛得到整数解。 最初直观的“差分约束”模型（最大化 \( d_ t \) 受约束 \( d_ v \geq d_ u + w_ {uv} \)）会导致无界，除非增加上界约束，但上界约束等价于 \( d_ v = \max_ {(u,v) \in E} (d_ u + w_ {uv}) \)，这是非线性。因此，流模型是合适的线性规划建模。 两种方法在多项式时间内求解，动态规划更高效，但线性规划模型可方便地扩展为多商品流或带额外约束的情况。