如果一个系统由 n 个变量和 m 个约束条件组成,每个约束条件形如 $x_j-x_i<=b_k$,其中 $i,j\in[1,n],k\in[1,m]$,则称其为差分约束系统(System of Difference Constraints)。亦即,差分约束系统是求解关于一组变量的特殊不等式组的方法。

我们先来看一个简单的数学问题,如下给定 4 个变量和 5 个不等式约束条件,求 $x_3-x_0$ 的最大值。

$$ \begin{align} x_1-x_0<=2 \tag{1} \\ x_2-x_0<=7 \tag{2} \\ x_3-x_0<=8 \tag{3} \\ x_2-x_1<=3 \tag{4} \\ x_3-x_2<=2 \tag{5} \end{align} $$

我们可以通过不等式的两两加得到三个结果,

$$ \begin{align} x_3-x_0<=8 \tag{式3} \\ x_3-x_0<=9 \tag{式2+式5} \\ x_3-x_0<=7 \tag{式1+式4+式5} \end{align} $$

由以上结果很容易得知,$x_3-x_0$ 的最大值是 7,也就是上面三式里的最小值。

这个例子很简单,只有 4 个变量和 5 个不等式约束条件,那如果有上百变量上千约束条件呢?仅凭肉眼手工计算效率太差,因此我们需要一个较为系统的解决办法。

我们先来看一幅图,如下,给定四个小岛以及小岛之间的有向距离,问从 0 号岛到 3 号岛的最短距离。箭头指向的线代表两个小岛之间的有向边,蓝色数字代表距离权值。

这个问题就是经典的最短路问题。由于这个图比较简单,我们可以枚举所有的路线,发现总共三条路线,如下:

  1. 0 -> 3,长度为 8
  2. 0 -> 2 -> 3,长度为 7 + 2 = 9
  3. 0 -> 1 -> 2 -> 3,长度为 2 + 3 + 2 = 7

最短路为三条线路中的长度的最小值,即 7,所以最短路的长度就是 7。细心的读者会发现,这幅图和最上方的五个不等式约束条件是有所关联的,但这个关联并不是巧合,而正是我们接下来要讲的那个 "系统的解决办法"。

差分约束与最短路

差分约束系统中的每个约束条件 $x_i-x_j<=c_k$ 都可以变形成 $x_i<=x_j+c_k$,这与单源最短路中的三角形不等式 $dist[y]<=dist[x]+z$ 非常相似。

因此,我们可以把每个变量 $x_i$ 看做图中的一个结点,对于每个约束条件 $x_i-x_j<=c_k$,看成是从结点 $j$ 向结点 $i$ 的一条权值为 $c_k$ 的有向边,于是我们就可以把一个差分约束系统转化成图的最短路问题。

然而在实际问题中情况往往会复杂得多,例如,把条件约束里的所有等号去掉,

$$ \begin{align} x_1-x_0<2 \notag{} \\ x_2-x_0<7 \notag{} \\ x_3-x_0<8 \tag{去掉等号后} \\ x_2-x_1<3 \notag{} \\ x_3-x_2<2 \notag{} \end{align} $$

这个时候我们就需要将上面的小于号转换成小于等于号。

当 $x_i$ 被限定只能是整数时,这个转换就会非常简单,

$$ (x_i-x_j<c_k) ↔ (x_i-x_j<=c_k-1) \notag{} $$

总结

差分约束问题下,

  1. 如果要求最大值,则想办法把每个不等式变为标准 $x_i-x_j<=c_k$ 的形式,然后建立一条从 $j$ 到 $i$ 权值为 $c_k$ 的边,最后求最短路径即可。
  2. 如果要求最小值,则想办法把每个不等式变为标准 $x_i-x_j>=c_k$ 的形式,然后建立一条从 $j$ 到 $i$ 权值为 $c_k$ 的边,最后求最长路径即可。

参考

其它

文章开源在 Github - blog-articles,点击 Watch 即可订阅本博客。 若文章有错误,请在 Issues 中提出,我会及时回复,谢谢。

如果您觉得文章不错,或者在生活和工作中帮助到了您,不妨给个 Star,谢谢。

(文章完)

文章作者:刘毅 (Ethson Liu)
发布日期:2020-06-13
原文链接:https://ethsonliu.com/2020/06/difference-constraints.html
版权声明:文章版权归本人所有,欢迎转载,但必须保留此段声明,且在文章页面明显位置给出原文链接,否则保留追究法律责任的权利。