AI 筆記26 - Solving CSP

Inference by Constraint propagation

之前說過CSP是一個search problem，但是因為有一些constraints，所以除了直接search之外，我們也可以用constraint propagation 當作前處理來reduce search space，有時候甚至constraint propagation就能解決問題，這個之前在Udacity的introduction project: Sudoku中就有講過了。

Backtracking Search (BTS)

針對CSP的DFS search我們稱為BTS，每次先固定一個variable的值。在DFS過程中會backtrack，如果某個variable assignment違反了之前的assignment（當然都要符合constraints)，所以一次先固定一個variable，然後變成一個新的限制propagate出去，類似像這樣。

例如以下coloring map，進行DFS會發現可能無法再給某個variable賦值了，那就需要backtracking了：

所以這個search problem formulation:

如何選擇下一個要search的variable?

這個問題其實就是DFS的要怎麼把neighbors放入frontier的順序。有一個原則就是類似我們在玩sudoku的直覺：先找最少可能legal moves的neighbor（相當於最多constraint的variable)，這邊稱為Minimum Remaining Values:

1. 上圖一開始，任何一個state都可以選，因為目前所有的state的顏色選擇度都是一樣的。
2. 圖二先選了最左邊的state，並且上紅色，接下來最少顏色選擇的明顯就是跟紅色state接界的，因為不跟他接界的至少多了一個紅色可以選擇。
3. 圖三選了接界的第一個，並且塗上綠色，接下來只有同時與紅綠色接界的state是選擇最少的
4. 選藍色state

邏輯就是先把選擇少的給予選擇，減少DFS backtrack的可能。

如何選擇下一個要try的domain value?

上面我們用minimum remaining values principle來選則下一個要上色的state，但是要上哪一個顏色？ 也就是要先選domain中的哪一個value?

這邊反過來要先選最少限制的domain value，稱為least constraining value，為什麼？
因為每次assign某個domain value之後，其他的variable就不能使用這個domain value了（以這個coloring map來說），所以一開始先選了most constraining value的話，等於其他的variable選擇變少，這樣DFS一定backtracking會變多，等於自己挖坑給自己跳！

演算法如下：

Forward Checking

這是一個提早發現assignment有問題，提早backtrack的方法，也就是每次assign某個domain value給某一個variable之後，就檢查其他的variable是否還有legal values? 沒有的話，就不用在這個branch繼續search下去了，減少node expansion。

1. 一開始所有的variable (states)都有所有的domain values (colors）可以選：

2. 如果assign WA紅色的話，我們來做forward checking update剩下variable的legal colors:

WA交界的NT和SA的紅色顏色都被去掉了

3. 同理

4. 這個V assign blue此時發生了SA再也沒有看選的顏色了，forward checking發現必須backtrack了：