賦值與限制
排程、標記和地圖著色可用有可能值的變量,以及限制哪些組合被允許的條件描述。約束滿足問題(CSP)要求找出滿足所有限制的完整賦值;它不一定為賦值附加目標函數。
定義 1.2.1
(有限二元約束網絡)
網絡有有限個變量,每個變量有有限定義域,並帶有二元約束。二元關係 指定允許的值對;反向使用轉置關係。解要從每個原始定義域選一值,並滿足每個約束。為簡化討論,同一對變量的多個約束先取關係交集,再應用以下程序。
支持與弧一致性
定義 1.2.2
(支持、修訂與弧一致性)
對約束的有向弧 ,若存在 使 ,則稱 在 有支持。修訂 ,即從 刪除所有沒有此支持的值。方向重要:修訂反向弧刪除的是 的值。若每條有向約束弧上的每個剩餘值都有支持,網絡便是弧一致的。定義域為空表示失敗;沒有約束的變量不需要鄰點支持。
反覆修訂仍可刪值的弧。定義域一旦縮小,相鄰弧可能失去支持,必須重新考慮。實作可用隊列保存受影響的弧;數學上的停止條件是相關改變後所有有向弧均已檢查。
命題 1.2.3
(修訂不會刪去任何解)
設網絡 由網絡 修訂一條有向弧而得。則 與 有相同的解,這裏解指從每個當前定義域選一值並滿足所有約束。因此,若反覆修訂令某個定義域變空,原網絡便沒有解。
證明
(解自己提供支持)
縮小定義域不會製造新解,所以 的每個解都是 的解。反過來,設 的某個解使用 ,而正在修訂 。同一個解給 指定某個 ,並滿足 ,所以 支持 , 不會被刪除,這個解在 中保留下來。對修訂次數歸納,原解集在剩餘值內被保留;若某定義域變空,就不存在解。這裏假設修訂期間約束本身沒有改變。
證明透視
為何刪除無支持的值是安全的
論證只用到解的一項性質:解給 指定的值落在當前定義域內,而這個值就是支持。因此支持是對當前定義域 檢驗的;由歸納,它仍包含每個解所用的值,所以即使每次修訂都依賴先前的刪除,整串修訂依然可靠。修訂只檢驗一個必要條件:值要出現在解中,沿一條弧必須有支持。反過來不成立,下面的三角形就是例子:每條弧上的每個值都有支持,卻沒有解。論證也依賴約束是二元且沒有改變;沿各對弧的支持,並不能合起來成為對三個變量約束的支持。
定理 1.2.4
(傳播終止於最大的弧一致網絡)
反覆修訂有向弧,直到沒有修訂能刪值為止,過程至多刪除 次便終止。所得定義域是弧一致的,而且與修訂次序無關:它是原定義域的所有弧一致子定義域選擇中最大的一個。
證明
(每次刪除都令一個有限量下降)
每次真正刪除都令定義域大小總和至少減一,所以至多刪除 次。沒有弧能再刪值時,每個剩餘值在每條有向弧上都有支持,這就是弧一致。至於與次序無關:若子定義域選擇 使 的每個值對每條弧 都在 中有支持,便稱它弧一致。兩個弧一致選擇的並集仍弧一致,因為在其中一個選擇有支持的值,在並集中也有支持,所以存在最大的一個 。任何修訂都不會刪去 的值:當前定義域滿足 時,每個 在 中有支持。最終結果包含 且本身弧一致,所以無論次序如何都等於 。
例題
例題 1.2.5
(三個互相不等的變量)
設 、、,要求 、、。修訂 會從 刪除 ,因 只能是 。接著修訂 從 刪除 ,再修訂 刪除 ,因 只能是 。定義域變為 ;唯一剩餘賦值滿足三個不等式。
例題 1.2.6
(不必分枝便發現無解)
設 、、,約束為 與 。修訂 刪除 ,因 唯一的值是 。此時 ,再修訂 刪除 ,因 唯一的值也是 。 變空,所以網絡無解。直接推理結果相同: 迫使 ,而 令 沒有可用的值。無解單靠傳播就發現了。
例題 1.2.7
(先傳播,再分枝)
設 、,三個變量要求兩兩不同。每條弧上的每個值已有支持:例如 由 與 支持, 由 與 支持。所以傳播甚麼也刪不掉,雖然只有 可能出現在解中。對 分枝:修訂 刪除 ,修訂 刪除 。在 之下,修訂 刪除 。所有定義域都成單元素:,對原始約束 、、 逐一檢查,確認它是解。
反例模式
局部支持不保證有解
取三角形變量 ,各有定義域 ,每條邊要求兩端不同。每條弧上的每個值都得到另一個值的支持,因此網絡已弧一致。但它沒有解:若 ,兩個鄰點都必須是 ,違反 ; 的情況對稱。一條弧選出的支持,未必與另一條弧的支持互相相容。
傳播後搜尋
若剩餘定義域均非空,選一個仍有多個值的變量,逐個對其剩餘值分枝。每個分枝把該變量限制為所選單元素集合,再進行傳播;若某定義域變空就捨棄該分枝。若所有變量均成單元素,報告解之前仍要檢查所有原始約束。
定理 1.2.8
(傳播加分枝既可靠又完備)
對有限網絡,先傳播、再對有多個剩餘值的變量分枝並遞歸的程序必然終止。它報告解,當且僅當解存在,而且每個被報告的賦值都滿足所有原始約束。
證明
(每個分枝都減少一個值,並保留所有解)
每個分枝把至少含兩個值的定義域換成單元素集合,傳播又只會刪值,所以沿每個分枝定義域大小總和嚴格下降,遞歸因此終止。被報告的賦值已對照所有原始約束檢查,所以是解。反過來,設解存在。它經得起安全傳播,並給分枝變量指定某個剩餘值,因此在該值對應的分枝中保留下來。對定義域大小總和歸納,它會在某個分枝中被找到。所以所有剩餘分枝都失敗,便證明無解。
此有限回溯程序的時間可隨變量數呈指數增長。弧一致性可以縮減搜尋,但不能消除此最壞情況。證明沒有聲稱某種變量選擇或隊列次序永遠最快。
常見錯誤
常見錯誤
(修訂了錯誤的方向)
修訂 刪除的是 的值,不是 的值。設 、 且 ,修訂 甚麼也刪不掉,因為 由 支持;修訂 才刪除 。兩個方向的弧都要考慮,一個方向不能代替另一個。
常見錯誤
(只掃一遍所有弧並不足夠)
取 、、,約束為 與 。按 、、、 的次序各修訂一次。只有 刪得了值:因 唯一的值是 ,它刪除 ,得 。此時網絡仍不弧一致,因為 在 中已沒有支持。較早的弧 必須再修訂一次,刪除 。最後的定義域 弧一致,並給出解 。定義域一旦縮小,相鄰的弧就要重新放回隊列。
練習
快速檢查
(在第一個例題中,為何 在弧 上沒有支持?)
看 的定義域。
解答 · 答案
只能為 ,而 違反 。
快速檢查
(在二色三角形中,分別為 在弧 和 上給出支持;為何仍得不到完整解?)
檢查兩個支持用的值彼此是否相容。
解答 · 答案
兩條弧都可用值 支持 ,但同時取 違反 。
快速檢查
(若安全修訂令某個定義域變空,可得甚麼結論?)
解必須從每個定義域取一個值。
解答 · 答案
沒有解:解必須從每個定義域取值,而安全修訂沒有刪去任何解所用的值。
快速檢查
(三個互相不等的變量各有定義域 ,給出一個解。)
依次給三個變量取三個不同的值。
解答 · 答案
取 ;每條邊的兩端均不同。