查看“︁差分约束系统”︁的源代码

{{refimprove|time}}
'''差分约束系统'''（System of Difference Constraints），是求解關於一組變數的[[特殊不等式組]]之方法。

如果一个系统由<math> n </math>个变量和<math> m </math>个约束条件组成，其中若每个约束条件形如 <math> x_j-x_i \le b_k(i,j \in [1,n], k \in [1,m]) </math>，则称其为差分约束系统。亦即，差分约束系统是求解关于一组变量的特殊不等式组的方法。
　　
== 解法 ==
求解差分約束系統，可以轉化成求解[[圖論]]的單源最短[[路徑]]。觀察<math> x_j-x_i \le b_k </math>，會發現它類似最短路中的三角不等式<math> d[v] \le d[u]+w[u,v] </math>，即<math> d[v]-d[u] \le w[u,v] </math>。因此，以每個變數<math> x_i </math>為結點，對於約束條件<math> x_j-x_i \le b_k </math>，連接一條邊<math> (i,j) </math>，邊權為<math> b_k </math>。再增加一個[[原點]]<math> (s, s) </math>與所有[[定點]]相連，[[邊權]]均為0（在某些题目中可能需要根据实际情况进行改动）。對這個圖以s為原點運行[[贝尔曼-福特算法|Bellman-Ford 算法]]（或[[SPFA算法|SPFA]]），最終<math> \{d[i]\} </math>即為一組可行解。<br/>
　　例如，考虑这样一个问题，寻找一个5维向量<math> x=(x_i) </math>以满足：

这一问题等价于找出未知量 <math>x_i, i \in \{1,2,3,4,5\}</math> ，满足下列8个差分约束条件：<br />
　<math> x_2-x_5 \le 1 </math><br />
　<math> x_1-x_2 \le 0 </math><br />
　<math> x_1-x_5 \le -1 </math><br />
　<math> x_3-x_1 \le 5 </math><br />
　<math> x_4-x_1 \le 4 </math><br />
　<math> x_4-x_3 \le -1 </math><br />
　<math> x_5-x_3 \le -3 </math><br />
　<math> x_5-x_4 \le -3 </math><br />该问题的一个解为<math> x=(-5,-3,0,-1,-4) </math>，另一个解<math> y=(0,2,5,4,1) </math>，这2个解是有联系的：<math> y </math>中的每个元素比<math> x </math>中相应的元素大5。

'''引理'''：设<math> x=(x_1,x_2,\cdots,x_n) </math>是差分约束系统<math> Ax \le b </math>的一个解，d为任意常数，则<math> x+d=(x_1+d,x_2+d,\cdots,x_n+d) </math>也是该系统<math> Ax \le b </math>的一个解。

<br />
[[Bellman-Ford算法|Bellman-Ford 算法]]-{zh-hans:伪代码; zh-hant:虛擬碼; zh-cn:伪代码; zh-tw:虛擬碼; zh-hk:虛擬碼; zh-sg:伪代码}-：
<pre>
# 初始化
for each v in V do 
    d[v] ← ∞; 
d[source] ← 0
# 松弛
for i =1,...,|V|-1 do
    for each edge (u,v) in E do
        d[v] ← min{d[v], d[u]+w(u,v)}
# 检查负环
for each edge (u, v) in E do 
    if d[v]> d[u] + w(u,v) then 
        <无解>
</pre>

==参考资料==
[[Category:數學术语]]
[[分类:数学概念]]