---
# System prepended metadata

title: 第五章 Constraint Satisfaction Problem
tags: [人工智慧]

---

# 第五章 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

![image](https://hackmd.io/_uploads/HJ4XMOqAJl.png)

-   變數：$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$ 不和其他變數連通，可以被視為獨立的子問題

```graphviz
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)$

```graphviz
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 解法來解決。

```graphviz
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）來處理接近樹結構的問題。
