006章 限制滿足問題

Post date: 2012/8/28 下午 12:34:35

限制滿足問題

本章中我們會看到不把狀態僅僅當作小黑盒子時,會如何引導設計出更強有力的新搜

尋方法,以及對問題的結構和複雜性有更深的理解。

限制滿足問題的定義

一個限制滿足問題由X、D、C 三個成份所組成:

X 是一個變數{X1, …, Xn}的集合。

D 是一個值域{D1,…, Dn}的集合,每個變數各有一個。

C 是一個限制的集合,指明值可允許的組合方式。

範例問題:地圖著色

圖6.1 (a) 澳大利亞主要的州和地方行政區。對此地圖的著色可以視為一個限制滿足問題。目標是對每

個區域分配顏色,使得相鄰的區域不同色。(b) 表示地圖著色問題的限制圖

範例問題:加工車間排程

考慮一輛車子的組裝排程問題。整個作業是由數個任務所組成,而我們能夠將每個任務塑造如同一個變數,

其中每個變數的值是任務開始的時間,以分鐘數來表示。

舉例來說,一個車輪必須先於輪轂罩裝上之前安裝好——且只有如此許多的任務才能夠同時開展。

限制也能夠指明某個任務需耗時多久才能完成。

我們考慮一小部份的車輛組裝任務,共有15 個任務:安裝車軸(前面和後面),裝上所有四個輪

子(左/右/前/後),擰緊每個車輪的螺母,裝上轂蓋,最後組裝檢查。我們能夠以15 個變數來表示這

些任務:

X = {AxleF, AxleB, WheelRF, WheelLF, WheelRB, WheelLB, NutsRF,

NutsLF, NutsRB, NutsLB, CapRF, CapLF, CapRB, CapLB, Inspect}

每個變數的值是任務開始的時間。接著我們表示出各個任務間的前提限制

每當一個任務T1 必須在任務T2 之前出現,而任務T1 需耗用時間d1 來完成

假設我們有四個工人安裝輪子,但是它們必須共用一個能協助輪軸定位的工具。

我們需要一個選言限制(disjunction constraint)來說明AxleF 與AxleB 在時間上必須不能重疊;

不是其中一個先做,就是另一個先做

我們也必須聲明檢查工作會最後完成並需時3 分鐘。除了Inspect,對每一個變數我們加了這個

形式X + dX ≤ Inspect 的限制。最後,假設有一個需求是整個組裝必須在30 分鐘內完成。我們能夠藉

由限制所有變數的值域來達成:

Di = {1, 2, 3,..., 27}

CSP 形式化的變種

最簡單的一種CSP 其涉及的變數具有離散且有限的值域。地圖著色的問題以及有時間限制的排

程這兩者都屬於這一種。第三章中描述的八皇后問題也可以視為有限值域的CSP,其中變數Q1, …,Q8

是每個皇后在列1, …, 8 中的位置,每個變數的值域是{1, 2, 3, 4, 5, 6, 7, 8}。

限制的傳播:於CSP 推理

於正常的狀態空間搜尋,一個演算法只能做一件事情:搜尋。於CSP 有一個選擇:演算法能搜

尋(從數個可能性選取一個新的變數賦值)或是做一個特定類型稱之為限制傳播(constraint propagation)

的推理

節點相容性

一個單一個變數(相應於CSP 網路的節點)屬於節點相容(node-consistent)

邊相容性

於一個CSP 的一個變數是邊相容(arc-consistent),如果變數的值域中的每一個值都滿足變數的二

元限制。

路徑相容

路徑相容藉由檢視三倍的變數所推論出的間接性限制來收緊二元限制 。

一個雙變數集合{Xi, Xj}對第三個變數Xm 是路徑相容的,如果對每一個賦值{Xi = a, Xj = b}與加

諸於{Xi, Xj}之限制,有一個賦值Xm 滿足加諸於{Xi, Xm}與{Xm, Xj}之限制。這稱之為路徑相容,因為

你可以想像成正望著一條從Xi 到Xj 的路徑而Xm 位在路中間。

K-相容

用k 相容的概念可以定義更強的傳播形式。如果對於任何k-1 個變數的相容賦值,第k 個變數

總能被賦予一個和前k-1 個變數相容的值,那麼這個CSP 問題就是k 相容的

全局限制

請記得全局限制說的是一個擁有任意數目之變數(但不必然是所有變數)的限制。

數獨例子

CSP 問題的回溯搜尋

數獨問題設計上是用來於限制下做推理來解題。但是許多其他CSP 無法單單由推理來解出;總

會有這麼個時候我們必須搜尋一個解答。

我們表面上似乎很合理但是天真的形式,忽略了常見於所有的CSP 的關鍵特性:可交換性。

回溯搜尋可用於深度優先搜尋,一次為一個變數選擇值,當沒有合法的值可以再賦給該變數時

就回溯。

限制滿足問題的一個簡單回溯演算法。該演算法以第三章的遞迴深度優先搜尋為模型。將函數

SELECT-UNASSIGNED-VARIABLE 和ORDER-DOMAIN-VALUES 作變化,我們可實作課文中討論的通

用啟發式演算法。函數INFERENCE 可視需要而選擇性加上邊-、路徑-、或k-相容性。如果所選擇的值造

成失敗(由INFERENCE 或BACKTRACK 所通知),則賦值(包括由INFERENCE 所做的)會從目前的賦值

中被移除,而且會嘗試一個新的值

圖6.6

圖6.1 中的地圖著色

問題的部分搜尋樹

變數和賦值順序

一旦一個變數被選定,演算法就要決定檢驗它的取值的次序。為此,最少限制值啟發式演算法

在某些情況下是有效率的。

交錯搜尋與推理

每當我們為該變數選擇一個值,我們就有一個在該變數附近做推理新值域縮減的嶄新機會。

最簡單的推理形式被稱之為前向檢驗。無論何時只要變數X 被賦予值了之後,前向檢查程序會

為之建立邊相容性:對於每個透過限制而連接到X 的尚未賦值變數Y,從Y 的值域刪除任何與為X

所選出之值不相容的值。因為前向檢驗僅僅做邊相容性推理,如果我們已經以預先處理的步驟完成

了邊相容性,那麼沒有理由做前向檢驗。

圖6.7 使用前向檢驗方法的地圖著色搜尋的進行方式。首先賦值WA = red;然後前向檢驗從其相鄰變數

NT 和SA 的值域中刪除red。賦值Q = green 之後,green 從NT、SA、NSW 的值域中被刪除。賦值V = blue

之後,blue 從NSW 和SA 的值域中被刪除,這時SA 已沒有合法值。

更聰明的回溯:向後看

圖6.5 中的BACKTRACKING-SEARCH 演算法當某個分支上的搜尋失敗時,會採取一個簡單的

方針:倒退回前一個變數並且嘗試另一個值。這稱為時序回溯,因為重新存取的是時間最近的決策

點。

CSP 問題的局部搜尋

局部搜尋演算法(參見4.1 節)對解許多CSP 問題都很有效的。它們使用完整的狀態形式:初始

狀態給每個變數都賦予一個值,且搜尋會一次改變一個變數的取值。舉例來說,於八皇后問題(見圖

4.3),初始狀態可能是8 皇后於8 行的隨機配置,且每一步會移動一個皇后到它行內的一個新位置。

通常,剛開始的猜測會違反好幾個限制。區域搜尋的重點是如何剔除被違反的限制[2]。

在為變數選擇一個新值的時候,最明顯的啟發式演算法是選擇會造成與其他變數的衝突最小的

值——最小衝突(min-confilicits)啟發式演算法。圖6.8 顯示了該演算法,而圖6.9 圖示了這個演算法

應用於八皇后問題時的情況。

一個用局部搜尋解決CSP 問題的MIN-CONFLICTS 演算法。初始狀態的選擇可採隨機方式,或

藉由貪婪賦值過程依次為每個變數選擇一個最小衝突的值而完成。函數CONFLICTS 統計一個特定值破

壞限制的數量,在已知當前賦值的剩餘值的情況下

用最小衝突演算法解決八皇后問題的一個兩步解。每一步選擇一個皇后,在它所在列中重新分配

位置。衝突的個數(在這個問題中是能攻擊到的皇后的個數)在每個方格裡列出來。演算法將皇后移到最小

衝突的方格裡,最小衝突值有多個方格時則隨機地選取其中之一

問題的結構

我們考慮以什麼方式利用問題的結構,如限制圖所表示的,能快速地找到解。

再看一次澳洲地圖的限制圖

(圖6.1b,重複於圖6.12a),凸顯出一種事實:Tasmania 和大陸不相連[3]。直觀上,顯然對Tasmania

著色和對大陸著色是獨立的子問題——任何對大陸區域著色的解和任何對Tasmania 著色的解合併起

來,都得到整個地圖的一個解。獨立性可以簡單地透過在限制圖中尋找連通域來確定。

當任兩個變數僅僅由一條路徑所連通的時候,一個限制圖形是一棵樹。我們將證明任何一個樹狀結

構的CSP 問題可以在變數個數的線性時間內求解[4]。關鍵之處是一個新的相容概念,稱之為有向的

邊相容性或DAC。一個CSP 在變數順序 X1, X2, …, Xn 下被定義為是邊相容的,若且唯若各個Xi 於j

> i 下與每一個Xj 是邊相容的。

要求解一個樹狀架構的CSP,首先挑選任一個變數當做樹的根節點,並選取一個變數的順序使

得每個變數出現在樹的母節點之後。這樣的排序被稱之為拓樸排序

(a) 樹狀結構CSP 的限制圖。(b) 與以A 為根節點的樹相容的變數的線性排序。這稱為該變數的

拓樸排序

TREE-CSP-SOLVER 演算法用於求解樹狀架構CSP。如果該CSP 有一個解答,我們會於線性時

間內找到它;如果沒有,我們會找出矛盾

(a) 圖6.1 的原始限制圖。(b) 刪除SA 之後的限制圖

1. 從CSP 變數中選擇一個子集S,使得限制圖在刪除S 之後成為一棵樹。S 稱為環割集

圖6.12(a)中限制圖的樹分解

限制滿足問題(CSP)以變數/值對的集合來表示狀態並以施加於該變數之限制的集合來表示解答

的條件。許多重要的現實世界問題都可以描述為CSP 問題。

● 有些推理技術使用限制來推論哪些變數/值對是相容的且哪些是是不相容的。這些包括節點,

邊,路徑,與k-相容。

● 回溯搜尋,深度優先搜尋的一種形式,經常用於求解CSP 問題。推理可以與搜尋交錯運用。

● 最少剩餘值和度啟發式演算法是在回溯搜尋中決定下一步選擇哪個變數的兩個獨立於值域的方

法。對於一個已給定的變數,最少限制值(least-constraining-value)啟發式有助於決定該優先試哪

一個值。回溯發生在對一個變數找不到合法賦值的時候。衝突導向的後向跳躍,直接回溯到問

題的源頭。

● 使用最小衝突啟發式演算法的局部搜尋,在求解限制滿足問題方面,已經很成功。

●求解CSP 問題的複雜度大部份上取決於限制圖的結構。樹狀結構的問題可以在線性時間內求

解。割集調整可以把一般的CSP 問題簡化為樹狀結構,並且在能找到比較小的割集的情況下,

十分有效。樹分解技術把CSP 問題轉變為子問題的樹,並且當限制圖的樹寬很小的時候是很有

效的。