# 第五章 Constraint Satisfaction Problem

## 約束滿足問題（CSP）

- 目標是尋找滿足所有約束的解
- 組成要素
- 變數：有限數量的 $V_1$, $V_2$, ..., $V_n$
- 值域：變數可以取的值的非空集合 $D_{V_1}$, $D_{V_2}$, ..., $D_{V_n}$
- 約束：有限數量的約束條件 $C_1$, $C_2$, ..., $C_m$
- 限制變數之間關係的條件
- 例如：$C_1$ 為 $V_1 \neq V_2$
- 狀態是對部分或全部變數賦值的一種分配（assignment）
- 解答必須具有完整性（complete）和一致性（consistent）
- 完整性：所有變數皆已賦值
- 一致性：滿足所有約束條件
- 應用案例
- 數獨
- 圖著色問題
- 密碼分析
- 排程問題

#### 範例：Map Coloring


- 變數：$WA$, $NT$, $SA$, $Q$, $NSW$, $V$, $T$
- 值域：$D_i = \{red, green, blue\}$
- 約束：相鄰的區域不能有相同顏色
- $WA \neq NT$...
- $(WA, NT) \in \set{(red, green), (red, blue), (green, blue), \dots}$
- Solution：$WA = red$, $NT = green$, $SA = blue$, $Q = red$, $NSW = green$, $V = blue$, $T = green$

### 約束圖（Constraint Graph）

Constraint Graph 可以用來表示 CSP 的結構

- 節點為變數，邊為約束
- 例如：
- $WA$ 和 $NT$ 之間有一條邊，表示它們之間有約束
- $T$ 不和其他變數連通，可以被視為獨立的子問題

digraph map_coloring_graph {
    rankdir=LR;
    edge[dir=none];
    WA -> NT
    WA -> SA
    NT -> SA
    NT -> Q
    SA -> Q
    SA -> NSW
    SA -> V
    Q -> NSW
    V -> NSW
    T->NSW[style=invis]
}

### CSP 的變數

- 離散變數（Discrete Variables）
- 有限的值域（Finite Domains）：
- 對於 $n$ 個變數都各別有大小為 $d$ 的值域
- 共有 $O(d^n)$ 種完整 assignment
- 例如：真質表、地圖著色問題
- 無限的值域（Infinite Domains）：
- 如整數、字串等
- 通常需使用「約束語言」表示條件（例如線性不等式）
- 線性約束可解，非線性通常不可解（undecidable）
- 例如：工作排程問題
- 連續變數（Continuous variables）
- 變數可取任意實數
- 多數線性約束可用線性規劃（Linear Programming） 在多項式時間內求解
- 例如：哈伯太空望遠鏡的觀測時間安排

### 約束的種類

- 一元約束（Unary Constraints）：
- 只涉及一個變數的約束
- 例如：$SA \neq green$
- 二元約束（Binary Constraints）：
- 只涉及兩個變數的約束
- 例如：$WA \neq NT$
- 多元約束（Global Constraints）：
- 涉及三個或以上變數的約束
- 例如：密碼算術中的欄位限制
- 偏好約束（Soft Constraints）：
- 不是硬性規定，而是「比較好」
- 例如：「紅色比綠色好」⇒ 每種指派有對應的「代價」，希望總成本最小

### CSP 的解法

CSP 可以視為一個標準的搜尋問題（Standard Search Problem），可以用以下的方式來表示

- 初始狀態：空的指派（empty assignment）：$\set{}$
- `Successor` 函數：指派合法值給未賦值的變數，並且跟約束條件沒有衝突
- Goal 測試： 所有變數都已被賦值，且滿足所有約束（complete & consistent）
- Path cost：一般為每步固定成本（通常不特別考慮）
- 複雜度：
- Solution 的深度為變數的數量 $n$
- 分支因子$b$ 初期為 $nd$
- 在深度為 $l$ 時， $b = (n - l)d$
- 有 $n!d^n$ 個葉節點
- CSP 具有可交換性（commutativity）
- 指派變數的順序**不影響結果**
- 例如：先做 $WA$ 再做 $NT$，或是先做 $NT$ 再做 $WA$，只要最終的值相同，則狀態相同
- 所以搜尋演算法通常只需考慮「一個變數一個值」的步驟，而非不同順序
- 只有 $d^n$ 個葉節點

## 回溯法（Backtracking Search）

- 使用 DFS 搜尋答案
- 每次選擇一個變數，然後賦值
- 如果賦值後不滿足約束，則回溯（backtrack）到上一步，重新選擇其他值

### 提升回溯法的效率

使用 General-purpose Methods（通用策略）來提升回溯法的效率：

- 下一個被指派的變數要選哪個？
- 要用什麼順序來嘗試值？
- 能否提早偵測失敗？
- 能否利用問題結構？

### 最少剩餘值域（Minimum Remaining Values, MRV）

- 又稱為 Most Constrained Variable Heuristic、fail-first heuristic
- 優先選擇剩餘值域最少的變數
- 例如：$WA$ 剩餘值域為 $\{red, green\}$，$NT$ 剩餘值域為 $\{red, green, blue\}$，則選擇 $WA$

### 度啟發式（Degree Heuristic）

- 優先選擇與最多未賦值變數相連的變數。
- 這樣可以最大程度地減少未來的選擇空間，從而提高搜尋效率。
- 當多個變數的 MRV 相同時使用

### 最少限制值（Least Constraining Value, LCV）

- 優先選擇對其他變數限制最少的值。
- 目的是最大程度地保留其他變數的選擇空間，減少未來可能的衝突。
- 例如：如果 $WA$ 的值為 $red$、$NT$ 的值為 $green$，則
- $Q$ 選擇 $red$ 時，$SA$ 有 1 種選擇
- $Q$ 選擇 $green$ 時，$SA$ 有 0 種選擇

### 向前檢查（Forward Checking）

當某個變數賦值後，立即檢查該賦值對其他未賦值變數的影響

- 如果有變數的值域為空，則立即回溯
- 避免深入無解的分支

## 局部搜尋

- 從一個完整的狀態開始
- 所有變數皆已賦值
- 但可能不滿足所有約束
- 接著反覆隨機的「小幅度改動」以降低衝突，直到找到合法解或滿意解
- 適合用於大規模的 CSP 問題
- 例如：n 皇后問題、數獨、排程問題

### 衝突最小化啟發式（Min-Conflicts Heuristic）

- 每次隨機選擇一個變數，然後將其值改為使衝突最少的值

## 問題結構（Problem Structure）

識別特定種類的問題結構可以幫助我們改進效率

### 樹狀結構（Tree-Structured CSPs）

- 若 CSP 的 Constraint Graph 沒有環，則可以在 $O(nd^2)$ 時間內解決
- 一般的 CSP 問題的 worst case 是 $O(d^n)$

digraph map_coloring_graph {
    rankdir=LR;
    edge[dir=none];
    A -> B
    C -> B
    B -> D
    D -> E
    D -> F
}

### 近似樹結構（Nearly Tree-Structured CSPs）

一個約束圖如果**只需少量修改就能變成樹**，我們就稱它是近似樹結構。

我們可以使用以下方法來解決近似樹結構的 CSP：

- 切割集條件法（Cutset Conditioning）
- 樹狀分解（Tree Decomposition）

### Cutset Conditioning

找出一小組變數，移除它們後，剩下的約束圖就是一棵樹。這組變數稱為 cutset（切割集）。如以下步驟所示：

1. 找到一組變數 cutset，使得移除它們會讓剩餘圖成為樹。
2. 枚舉 cutset 的所有可能指派（最多 $d^c$ 種，$c$ 為 cutset 大小）
3. 對於每種 cutset 指派：
- 套用「樹狀 CSP 解法」來解剩下部分
- 如果成功找到符合的完整解 → 結束！

例如：

當 cutSet 為 $\set{SA}$ 時，剩下的圖為樹狀結構，可以用樹狀 CSP 解法來解決。

digraph map_coloring_graph {
    rankdir=LR;
    edge[dir=none];
    WA -> NT
    WA -> SA
    NT -> SA
    NT -> Q
    SA -> Q
    SA -> NSW
    SA -> V
    Q -> NSW
    V -> NSW
    T->NSW[style=invis]
}

### 樹狀分解

- 將變數拆分成若干個「子問題節點」
- 每個子問題都是一個可以獨立解決 CSP，並且
- 每個變數至少出現在一個子問題中
- 如果變數 $X$ 和 $Y$ 相依，則它們必須在同一個子問題中
- 如果變數 $X$ 出現在兩個子問題，則必須在這兩個節點的路徑上的每一個節點中出現
- 最終的解答是所有子問題的解答的組合

## 小結

1. **CSP 的基本組成**：
- CSP 包含變數、值域和約束，目標是找到滿足所有約束的解。
- 常見應用包括數獨、圖著色問題和排程問題。
2. **回溯法（Backtracking Search）**：
- 使用深度優先搜尋（DFS）逐步為變數賦值。
- 提升效率的策略包括：
- 最少剩餘值域（MRV）
- 度啟發式（Degree Heuristic）
- 最少限制值（LCV）
- 向前檢查（Forward Checking）
3. **局部搜尋（Local Search）**：
- 從完整但可能不合法的解開始，通過隨機小幅度改動來減少衝突。
- 衝突最小化啟發式（Min-Conflicts Heuristic）是局部搜尋中的常用方法。
4. **問題結構（Problem Structure）**：
- **樹狀結構（Tree-Structured CSPs）**：
- 若約束圖無環，可在 $O(nd^2)$ 時間內高效求解。
- **近似樹結構（Nearly Tree-Structured CSPs）**：
- 使用切割集條件法（Cutset Conditioning）或樹狀分解（Tree Decomposition）來處理接近樹結構的問題。