差分约束系统（Difference Constraints System）
字数 2239 2025-12-14 21:50:37

差分约束系统（Difference Constraints System）

问题描述

差分约束系统是一类特殊的线性不等式组，其中每个不等式形如 \(x_j - x_i \leq b_k\)，变量 \(x_1, x_2, \dots, x_n\) 为实数，\(b_k\) 为常数。目标：判断是否存在一组实数解，若存在，通常希望求出一组可行解。

应用场景

  • 任务调度（如工序前后时间约束）
  • 时钟同步
  • 图论中的最短路径建模

问题转化

将每个不等式 \(x_j - x_i \leq b\) 转化为一条有向边：

  • 从结点 \(i\) 到结点 \(j\) 建边，边权为 \(b\)。
  • 则不等式组对应一个有向图。

关键观察
若图中存在负权环，则系统无解；否则，令 \(x_i\) 为从 新增源点 到结点 \(i\) 的最短路径长度，即为可行解。

算法步骤

步骤1：建图

设变量编号 \(1 \dots n\)，建图 \(G = (V, E)\)：

  1. 对每个不等式 \(x_j - x_i \leq b\)，添加有向边 \(i \xrightarrow{b} j\)。
  2. 添加一个超级源点 \(s\)（编号 \(0\) 或 \(n+1\)），从 \(s\) 向每个变量结点 \(i\) 连一条 权重为 0 的有向边 \(s \xrightarrow{0} i\)。
    • 目的：保证所有结点可达，初始化距离 \(d[s] = 0\)，其余 \(d[i] = +\infty\)。

例子
不等式组：
\(x_2 - x_1 \leq 3\)
\(x_3 - x_2 \leq -2\)
\(x_1 - x_3 \leq 1\)
建图（不含源点）：

  • 边 \(1 \xrightarrow{3} 2\)
  • 边 \(2 \xrightarrow{-2} 3\)
  • 边 \(3 \xrightarrow{1} 1\)

步骤2：判断解存在性（检测负环）

从源点 \(s\) 出发，求单源最短路径：

  • 使用 Bellman-Ford 算法（因为边权可负）。
  • 若 Bellman-Ford 检测到负权环 → 系统无解。
  • 若无负环，则最短路径值 \(d[i]\) 即为 \(x_i\) 的一组可行解。

原理
对于任意边 \(i \xrightarrow{b} j\)，最短路径性质保证 \(d[j] \leq d[i] + b\)，即 \(d[j] - d[i] \leq b\)，恰好满足原不等式。

步骤3：求解并验证

若不存在负环，输出解 \(x_i = d[i]\)。
验证方法：检查所有边是否满足三角不等式 \(d[j] \leq d[i] + w(i,j)\)。

示例演示

不等式组：

\[\begin{cases} x_2 - x_1 \leq 5 \\ x_3 - x_2 \leq 6 \\ x_1 - x_3 \leq -3 \end{cases} \]

建图（含源点 \(s\)）：

  • 边：\(1 \xrightarrow{5} 2,\ 2 \xrightarrow{6} 3,\ 3 \xrightarrow{-3} 1\)
  • 加 \(s \to 1,\ s\to 2,\ s\to 3\) 权重 0

运行 Bellman-Ford：
初始化 \(d[s]=0,\ d[1]=d[2]=d[3]=\infty\)。
迭代更新：

  1. 从 \(s\) 更新邻居：\(d[1]=d[2]=d[3]=0\)。
  2. 用 \(1\to 2\)：\(d[2] \leq d[1]+5 \Rightarrow 0 \leq 0+5\) 成立。
  3. 用 \(2\to 3\)：\(d[3] \leq d[2]+6 \Rightarrow 0 \leq 0+6\) 成立。
  4. 用 \(3\to 1\)：\(d[1] \leq d[3]+(-3) \Rightarrow 0 \leq 0-3\)？不成立，更新 \(d[1] = -3\)。
    → 此更新会导致后续再次更新 \(d[2]\) 等，最终发现无负环，得到解：
    \(x_1 = -3,\ x_2 = 2,\ x_3 = 8\)（可能不唯一，因为可整体加减常数）。

注意事项

  1. 不等式的其他形式
    • \(x_j - x_i \geq b\) ⇔ \(x_i - x_j \leq -b\)（反向边）。
    • \(x_j - x_i = b\) ⇔ 同时满足 \(\leq b\) 和 \(\geq b\)。
  2. 解的唯一性
    若图中所有结点与 \(s\) 连通，则任意解可加上同一常数得到新解，故解不唯一；若不连通，不同连通分量可独立平移。
  3. 优化
    可使用 SPFA（队列优化 Bellman-Ford），但在约束规模大时仍可能退化为 \(O(nm)\)。

复杂度

  • 时间：\(O(nm)\)，其中 \(n\) 为变量数（含源点），\(m\) 为边数（约束数 + 源点边）。
  • 空间：\(O(n+m)\)。
差分约束系统（Difference Constraints System） 问题描述 差分约束系统是一类特殊的线性不等式组，其中每个不等式形如 \( x_ j - x_ i \leq b_ k \)，变量 \( x_ 1, x_ 2, \dots, x_ n \) 为实数，\( b_ k \) 为常数。目标：判断是否存在一组实数解，若存在，通常希望求出一组可行解。 应用场景 任务调度（如工序前后时间约束） 时钟同步 图论中的最短路径建模 问题转化 将每个不等式 \( x_ j - x_ i \leq b \) 转化为一条有向边： 从结点 \( i \) 到结点 \( j \) 建边，边权为 \( b \)。 则不等式组对应一个有向图。 关键观察 若图中存在负权环，则系统无解；否则，令 \( x_ i \) 为从 新增源点 到结点 \( i \) 的最短路径长度，即为可行解。 算法步骤 步骤1：建图 设变量编号 \( 1 \dots n \)，建图 \( G = (V, E) \)： 对每个不等式 \( x_ j - x_ i \leq b \)，添加有向边 \( i \xrightarrow{b} j \)。 添加一个超级源点 \( s \)（编号 \( 0 \) 或 \( n+1 \)），从 \( s \) 向每个变量结点 \( i \) 连一条 权重为 0 的有向边 \( s \xrightarrow{0} i \)。 目的：保证所有结点可达，初始化距离 \( d[ s] = 0 \)，其余 \( d[ i ] = +\infty \)。 例子 不等式组： \( x_ 2 - x_ 1 \leq 3 \) \( x_ 3 - x_ 2 \leq -2 \) \( x_ 1 - x_ 3 \leq 1 \) 建图（不含源点）： 边 \( 1 \xrightarrow{3} 2 \) 边 \( 2 \xrightarrow{-2} 3 \) 边 \( 3 \xrightarrow{1} 1 \) 步骤2：判断解存在性（检测负环） 从源点 \( s \) 出发，求单源最短路径： 使用 Bellman-Ford 算法 （因为边权可负）。 若 Bellman-Ford 检测到负权环 → 系统无解。 若无负环，则最短路径值 \( d[ i] \) 即为 \( x_ i \) 的一组可行解。 原理 对于任意边 \( i \xrightarrow{b} j \)，最短路径性质保证 \( d[ j] \leq d[ i] + b \)，即 \( d[ j] - d[ i ] \leq b \)，恰好满足原不等式。 步骤3：求解并验证 若不存在负环，输出解 \( x_ i = d[ i ] \)。 验证方法：检查所有边是否满足三角不等式 \( d[ j] \leq d[ i ] + w(i,j) \)。 示例演示 不等式组： \[ \begin{cases} x_ 2 - x_ 1 \leq 5 \\ x_ 3 - x_ 2 \leq 6 \\ x_ 1 - x_ 3 \leq -3 \end{cases} \] 建图（含源点 \( s \)）： 边：\( 1 \xrightarrow{5} 2,\ 2 \xrightarrow{6} 3,\ 3 \xrightarrow{-3} 1 \) 加 \( s \to 1,\ s\to 2,\ s\to 3 \) 权重 0 运行 Bellman-Ford： 初始化 \( d[ s]=0,\ d[ 1]=d[ 2]=d[ 3 ]=\infty \)。 迭代更新： 从 \( s \) 更新邻居：\( d[ 1]=d[ 2]=d[ 3 ]=0 \)。 用 \( 1\to 2 \)：\( d[ 2] \leq d[ 1 ]+5 \Rightarrow 0 \leq 0+5 \) 成立。 用 \( 2\to 3 \)：\( d[ 3] \leq d[ 2 ]+6 \Rightarrow 0 \leq 0+6 \) 成立。 用 \( 3\to 1 \)：\( d[ 1] \leq d[ 3]+(-3) \Rightarrow 0 \leq 0-3 \)？不成立，更新 \( d[ 1 ] = -3 \)。 → 此更新会导致后续再次更新 \( d[ 2 ] \) 等，最终发现无负环，得到解： \( x_ 1 = -3,\ x_ 2 = 2,\ x_ 3 = 8 \)（可能不唯一，因为可整体加减常数）。 注意事项 不等式的其他形式 \( x_ j - x_ i \geq b \) ⇔ \( x_ i - x_ j \leq -b \)（反向边）。 \( x_ j - x_ i = b \) ⇔ 同时满足 \( \leq b \) 和 \( \geq b \)。 解的唯一性 若图中所有结点与 \( s \) 连通，则任意解可加上同一常数得到新解，故解不唯一；若不连通，不同连通分量可独立平移。 优化 可使用 SPFA（队列优化 Bellman-Ford），但在约束规模大时仍可能退化为 \( O(nm) \)。 复杂度 时间：\( O(nm) \)，其中 \( n \) 为变量数（含源点），\( m \) 为边数（约束数 + 源点边）。 空间：\( O(n+m) \)。