AI 筆記25 - Constraint Satisfaction Problem

A search problem, too

CSP是比較特別的search problem，因為此類probelm不關心怎麼抵達goal的路徑，而是關心有無抵達goal而已。

CSP formulation主要有以下三者：

1. a set of variables: X1, X2, ...
2. a set of domains: 每個Xi的domain Di: D1, D2, D3
3. a set of constraints C: 合法的combination

所以解決CSP就是在找出符合constraints C的assignment(給X1, X2,...)，稱為consistent assignment。

有名的例子就是8-Queen problem。

Example: Coloring Map

把一張地圖上的區塊填色，基本限制是相鄰的區塊不能同色，這是代表性的CSP。嘗試來formalize CSP:

上圖把CSP formalization解釋得很清楚。constraints可以寫得更清楚如下，例如把所有valid pairs列出來，當然不能有重複的element在一個pair裡面：

solution就是assignment to Xi:

Constraint Graph

CSP通常也可以畫成graph來看出限制，好處是可以用graph algorithm來加速解決問題：

Discrete Variables

如果variable可能的值來自finite domain，假設n個variables來自可能的d個domains，則排列組合為d^n，所以如果要complete assignment(定義是什麼 課程中沒講清楚）會是O(d^n)。

如果domain是infinitely discrete，那就要看怎麼描述這個constraint（稱為constraint language)，例如用不等式來描述某個事件應該要在前一個事件t秒後發生：

Continuous Variables

這是operations research problem，就要用到linear programming技巧，不解。

Example: Cryptarithmetic puzzle

這是一個複合字，就是一個英文字偽裝成數學式的謎題，例如以下題目：

這“可以”是一個CSP problem，有0~9 10個數字，而這裡面牽涉到了T W O F U R五個不同的數字，所以全部的組合有choose(10,5)只有252種。當然如果看成CSP，那就要看CSP怎麼解？

我們一樣先formalize CSP:

C1,C2,C3分別是個十百位的進位數字，可能是{0,1}。列出的constraints其實就是加法的一些限制。

我們一樣把CSP換成hypergraph （i.e. 一個node可以連接很多edge）來看constraints與node間的關係：

藍色方匡就代表某個constraint，有edge連接代表對那個node此constraint是applied。不過上圖hypergraph似乎漏掉了constraint 2？！