差分约束系统

维基百科,自由的百科全书
跳到导航 跳到搜索

差分约束系统(System of Difference Constraints),是求解關於一組變數的特殊不等式組之方法。

如果一个系统由个变量和个约束条件组成,其中每个约束条件形如,则称其为差分约束系统。亦即,差分约束系统是求解关于一组变量的特殊不等式组的方法。   

解法[编辑]

求解差分約束系統,可以轉化成圖論的單源最短路徑問題。觀察,會發現它類似最短路中的三角不等式,即。因此,以每個變數為結點,對於約束條件,連接一條邊,邊權為。再增加一個原點與所有定點相連,邊權均為0。對這個圖以s為原點運行Bellman-ford演算法(或SPFA演算法),最終即為一組可行解。
  例如,考虑这样一个问题,寻找一个5维向量以满足:

  这一问题等价于找出未知量 ,满足下列8个差分约束条件:
    
    
    
    
    
    
    
    
  该问题的一个解为,另一个解,这2个解是有联系的:中的每个元素比中相应的元素大5。
  引理:设是差分约束系统的一个解,d为任意常数。则也是该系统的一个解。
bellman-ford算法伪代码:

# initialization
for each v in V do 
    d[v] ← ∞; 
d[source] ← 0
# Relaxation
for i =1,...,|V|-1 do
    for each edge (u,v) in E do
        d[v] ← min{d[v], d[u]+w(u,v)}
# Negative cycle checking
for each edge (u, v) in E do 
    if d[v]> d[u] + w(u,v) then 
        no solution