差分约束系统

差分约束的最短路径算法证明和解释。

差分约束系统

  • 差分约束系统用一个m×n的线性规划矩阵表示m个不等式,这m个不等式中共n个变量x1,x2,…,xn,每个不等式满足如下形式:xi - xj <= bk(1 <= i, j <= n, 1 <= k <= m),在矩阵中的表示为,每一行都有一个1和一个-1,其他元素都为0。例如
    1-1000
    1000-1
    0100-1
    -10100
    -10010
    00-110
    00-100
    000-11
    用上面的矩阵乘一个n×1的变量矩阵x = (xi),使其满足一个m×1的常数矩阵(bk)。等价于找出下面8个不等式的可行解:x1 - x2 <= b1; x1 - x5 <= b2; x2 - x5 <= b3; x3 - x1 <= b4; x4 - x1 <= b5; x4 - x1 <= b6; x5 - x3 <= b7; x5 - x4 <= b8。对于bk = (0, -1, 1, 5, 4, -1, -3, -3)的一个序列,x的一个可行解为(-5, -3, 0, -1, -4),同样,对于任意x’ = x+d,d为任意常数,x’也是该不等式组的一组解。

约束图

  • 观察差分约束系统的不等式,发现其与最短路径松弛操作相似。松弛操作的判断条件是d[v] <= d[u] + w(u, v),差分约束方程中为xi - xj <= bk,因此xi <=> d[v],xj <=> d[u],w(u, v) <=> bk,据此建边vj->vi,权值为bk,变量x1,x2,…,xn分别对应结点s1,s2,s3,…,sn。
  • 在上述图中,附加一个源点s0,将其与所有顶点相连,并将s0的所有出边权值均设为0。下面将证明,给定一个差分约束系统Ax<=b,设G=(V,E)为该系统对应的约束图,则如果G不包含负权环,从s0到其它各点的最短路径权值就是一组可行解,否则此系统不存在可行解。证明过程如下:当G不包含负权回路时,对于任意边(vi, vj),根据三角不等式d[vj] <= d[vi] + w(vi, vj),设d[vi] = xi, d[vj] = xj,那么xj - xi <= w(vi , vj),因此满足对应边(vi, vj)的差分约束。而当G中包含负权回路时,假设负权回路为,其中v1 = vk(源点s0没有入边,不可能出现在负权环上),因此整个负权环对应如下的差分约束:x2 - x1 <= w(v1,v2);x3 - x2 <= w(v2, v3);…;xk - xk-1 <= w(vk-1, vk),将这k-1个不等式相加,则左边为0,而右边是负数,矛盾。因此不存在解。

最大解与最小解

  • 当差分约束条件给出其中一个解xi,即固定解的一个元素,求解的其他元素所能取到的最大解或最小解。在约束图的创建中,我们将从源点引出的边权值都赋为0,其实隐含着:d[vi] - d[v0] <= 0这样的条件,因此求出的解一定小于等于零,如果我们把s0也看作一个变量x0,那么上面例子中的解就是(0, -5, -3, 0, -1, -4),也就是预先指定了x0的解为0。这里的x0就是源点s0的偏移量,例如当题中增加条件,要求解的所有元素都小于某个值,此时只要将该值设置为s0的偏移量即可。
  • 对于这类有一个未知数已经定死的情况,还有一个性质:通过最短路径算法求出的一组解是所有解中的最大值。考虑到Bellman-Ford等单源最短路径算法的初始化都是d[vi] = 正无穷,通过各种约束条件使d[vi]的值不短减小来满足,因此当所有约束条件都满足,无法松弛任意边时,求出的解就是最大解。同样,如果要求所求得的解是所有解中的最小解,只要将问题转化为求解最长路径,松弛条件变为d[v] >= d[u] + w(u, v),此时的不等式变为xj - xi >= -bk,因此建边vi->vj,权值为-bk,求其最长路径,即为最小值。

原创作品,允许转载,转载时无需告知,但请务必以超链接形式标明文章原始出处(http://forec.github.io/2015/12/24/Graph-Algorithms6/) 、作者信息(Forec)和本声明。

分享到