差分约束系统
差分约束系统
- 差分约束系统（spfa）
- 1、概述
- 2、过程模拟
- 3、推理
差分约束系统（spfa）
1、概述
x j − x i ≤ w k x_j-x_i\le w_k xj−xi≤wk转换为： x j ≤ w k + x i x_j\le w_k+x_i xj≤wk+xi
在松弛操作中：
∙ \bullet ∙如果 d ( v j ) > d ( v i ) + w ( e i , j ) d(v_j)>d(v_i)+w(e_{i,j}) d(vj)>d(vi)+w(ei,j)，则更新 d ( v j ) = d ( v i ) + w ( e i , j ) d(v_j)=d(v_i)+w(e_{i,j}) d(vj)=d(vi)+w(ei,j)；
∙ \bullet ∙如果 d ( v j ) ≤ d ( v i ) + w ( e i , j ) d(v_j)\le d(v_i)+w(e_{i,j}) d(vj)≤d(vi)+w(ei,j)，则无需更新，这是最终目的。
差分约束系统转化成图的形式，再通过求解最短路径的方法（即通过松弛操作）就能够实现差分系统的求解。
2、过程模拟
由上述所知， x j − x i ≤ w k x_j-x_i\le w_k xj−xi≤wk就相当于节点 v i v_i vi到节点 v j v_j vj的边权距离为 w k w_k wk
x 2 − x 1 ≤ − 2 x_2-x_1\le -2 x2−x1≤−2
x 1 − x 3 ≤ − 1 x_1-x_3\le -1 x1−x3≤−1
x 2 − x 3 ≤ 4 x_2-x_3\le 4 x2−x3≤4
x 4 − x 2 ≤ 5 x_4-x_2\le 5 x4−x2≤5
x 3 − x 4 ≤ 2 x_3-x_4\le 2 x3−x4≤2
x 4 − x 3 ≤ − 2 x_4-x_3\le -2 x4−x3≤−2
x 5 − x 4 ≤ 3 x_5-x_4\le 3 x5−x4≤3
x 5 − x 3 ≤ − 3 x_5-x_3\le -3 x5−x3≤−3
⇓ \Darr ⇓
⇓ \Darr ⇓
以 v 1 v_1 v1作为源节点
顶点的 d d d值为： ( 0 , − 2 , 5 , 3 , 2 ) (0,-2,5,3,2) (0,−2,5,3,2)
由于 d ( v 2 ) − d ( v 1 ) ≤ w 1 , 2 d(v_2)-d(v_1)\le w_{1,2} d(v2)−d(v1)≤w1,2，所以 − 2 − 0 ≤ − 2 -2-0\le -2 −2−0≤−2成立，也可得 x 2 = − 2 x_2=-2 x2=−2， x 1 = 0 x_1=0 x1=0
⇓ \Darr ⇓
以 v 3 v_3 v3作为源节点
顶点的 d d d值为： ( − 1 , − 3 , 0 , − 2 , − 3 ) (-1,-3,0,-2,-3) (−1,−3,0,−2,−3)
⇓ \Darr ⇓
以 v 0 v_0 v0作为源节点
顶点的 d d d值为： ( − 1 , − 3 , 0 , − 2 , − 3 ) (-1,-3,0,-2,-3) (−1,−3,0,−2,−3)
以 v 2 v_2 v2作为源节点，顶点的 d d d值为： ( 4 , 0 , 7 , 5 , 8 ) (4,0,7,5,8) (4,0,7,5,8)
以 v 4 v_4 v4作为源节点，顶点的 d d d值为： ( 1 , − 1 , 2 , 0 , − 1 ) (1,-1,2,0,-1) (1,−1,2,0,−1)
总计如下：
以 v 1 v_1 v1作为源节点， x v 1 = ( 0 , − 2 , 5 , 3 , 2 ) x_{v_1}=(0,-2,5,3,2) xv1=(0,−2,5,3,2)
以 v 2 v_2 v2作为源节点， x v 2 = ( 4 , 0 , 7 , 5 , 8 ) x_{v_2}=(4,0,7,5,8) xv2=(4,0,7,5,8)
以 v 3 v_3 v3作为源节点， x v 3 = ( − 1 , − 3 , 0 , − 2 , − 3 ) x_{v_3}=(-1,-3,0,-2,-3) xv3=(−1,−3,0,−2,−3)
以 v 4 v_4 v4作为源节点， x v 4 = ( 1 , − 1 , 2 , 0 , − 1 ) x_{v_4}=(1,-1,2,0,-1) xv4=(1,−1,2,0,−1)
其中， x v 2 x_{v_2} xv2和 x v 1 x_{v_1} xv1、 x v 3 x_{v_3} xv3都没有关联性，但 x v 4 = x v 3 + 2 x_{v_4}=x_{v_3}+2 xv4=xv3+2。
3、推理
推理1：
对于差分约束系统的任意一个解 x = ( x 1 , x 2 , x 3 , x 4 , x 5 ) x=(x_1,x_2,x_3,x_4,x_5) x=(x1,x2,x3,x4,x5)，以及任意一个常数 k k k，则 x ′ = x + k = ( x 1 + k , x 2 + k , x 3 + k , x 4 + k , x 5 + k ) x'=x+k=(x_1+k,x_2+k,x_3+k,x_4+k,x_5+k) x′=x+k=(x1+k,x2+k,x3+k,x4+k,x5+k)依然是差分约束系统的解。
推理2：
以差分约束系统对应图的所以节点为源节点，得出所有的独立解（这些解之间没有关联性），差分约束系统的所有解包含：1、所有的独立解，2、这些独立解和任意一个常数的和。
推理3：
如果差分约束系统对应图存在负环（也就是不存在最短路径），则差分约束系统不存在可行解。