[ Algorithm ] Map color problem - Using BACKTRACKING Search

Preface: 
這邊我們要解的問題是有名的 "四色定理", 簡單來說就是使用四種顏色對某一個 Graph 進行塗色, 限制條件式每個區塊與該區塊的臨邊的區塊不能是同一個顏色, 底下是一個範例: 
 
(使用四種顏色對大陸地圖著色) 

而在某些較簡單的圖, 只需要三種顏色即可以完成. 這邊我們的問題是要對 Australia 的地圖進行著色並滿足上述條件: 
 

Problem analysis: 
在 AI 的領域, 這是個標準的 CSP (Constraint Satisfaction Problems) 問題, 而因此我們可以引用在 CSP 問題中的演算法來解這個問題. 而一個 CSP 問題會有三個元件進行問題描述 X, D 與 C: 

- X: A set of variables, {X1,...,Xn}
- D: A set of domains, {D1,...,Dn} 每個 variable 有屬於自己的 Domain, 即該 Variable 的可能值.
- C: A set of constraints that specify allowable combinations of values. 這裡說明這些 Variables 間的關係或限制. 以四色定理為範例, 即是臨邊的值必須不同.

接著分析問題, 我們將每個區塊用一個變數來表示: 

X={WA, NT, Q, NSW, V, SA, T}

因為這個圖形相對簡單, 所以使用三種顏色即可滿足條件. 接著每個變數的 Domain 則是: 

D={Red,Blue,Green}

最後便是這些變數間的關係或是限制條件, 白話說是每個區塊與其臨邊顏色不同, 寫成限制條件則像是: 

C={SA!=WA, SA!=NT, SA!=Q,SA!=NSW, SA!=V, WA!=NT, NT!=Q, Q!=NSW, NSW!=V}

BACKTRACKING Search Algorithm: 
這邊要使用的演算法 "BACKTRACKING Search" 的 pseudo code 如下: 
 
在深入說明該演算法前, 要來介紹幾個在 CSP 問題裡面 term 的解釋: 
- consistent 

To solve a CSP, we need to define a state space and the notation of a solution. Each state in a CSP is defined by an assignment of values to some or all of the variables, {Xi=vi, Xj=vj,...}. An assignment that does not violate any constraints is called a consistent or legal assignment.

- Binary constraint 

A binary constraint relates two variables. For example, SA!=NSW is a binary constraint. A binary CSP is one with only binary constraints.

- Arc consistency 

A variable in a CSP is arc-consistent if every value in its domain satisfies the variable's binary constraints. More formally, Xi is arc-consistent with respect to another variable Xj if for every value in the current domain Di there is some value in the domain Dj that satisfies the binary constraint on the arc (Xi, Xj).

- MRV (Minimum Remaining Values) 

The backtracking algorithm contains the line:

var <- i="i" select-unassigned-variable="select-unassigned-variable">csp

)
Choosing the variable with the fewest "legal" values - is called the minimum remaining variables (MRV) heuristic. It also has been called the "most constraint variable" or "fail-first" heuristic. the latter because it picks a variable that is most likely to cause a failure soon, thereby pruning the search tree.
- least-constraining-value 

Once a variable has been selected, the algorithm must decide on the order in which to examine its values. For this, the least-constraining-value heuristic can be effective in some cases. It prefers the value that rules out the fewest choices for the neighboring variables in the constraint graph.

- Complete assignment 

A complete assignment is one in which every variable is assigned, and a solution to a CSP is a consistent, complete assignment. A partial assignment is one tht assigns values to only some of the variables.

所以雖然 pseudo code 很短, 但是背後的學問可大的 orz. 首先這個演算法的概念就是一次取一個 variable 進行賦值, 如果 "consistent" 則取下一個 variable 繼續賦值並檢查 "consistent", 但如果該值不 consistent, 則從該 variable 的 Domain 取下一個值繼續上述步驟; 一旦所有的值都試過且都不 consistent, 則回到上一個賦值的 variable, 並對該 variable 重新賦值 (backtracking); 到所有可能性都試過還是不行的話呢, 就返回 failure, 或者所有的 variables 都成功賦值 (complete) 且都滿足 constraint (consistent), 則返回 assignment. 

而在進行上述過程中, 有些 heuristic 方法可以提高演算法的效能, 如: 
- MRV: 在挑選 variable 時, 先選擇最有影響力的. 在這個問題中便是 SA. 因為它有 5 個臨邊, 一旦 SA 決定顏色, 其他臨邊便被限制不能是該顏色. 

- least-constraining-value: 在挑選 variable 的值時, 先挑選該值會造成其它臨邊受限的狀況為最小. 這與 MRV 剛好相反, 因為我們的目的是要找到 solution 而不是那些受限的路徑! 因此挑最有可能達到目的地的方向走就對了. 

- forward checking: 再決定某個 variable 的值後, 該 variable 的臨邊某些值便不能被 assign 了. 因此到了對該 variable 賦值時, 便可以避開那些受限的值. 

Programming: 
在實作的部分, 我使用類別 Variable 來代表某個 variable: 
- Variable: 

view plaincopy to clipboardprint?

1. package c6.mapcolor;  
2.   
3. import java.util.ArrayList;  
4. import java.util.HashMap;  
5. import java.util.HashSet;  
6. import java.util.List;  
7. import java.util.PriorityQueue;  
8. import java.util.Set;  
9.   
10. public class Variable implements Comparable{  
11.     public String                       name; // Name of variable  
12.     public T                            value = null; // Value of variable  
13.     public List                        domain = new ArrayList(); // Domain of variable  
14.     public HashMap>    restricts = new HashMap>(); // Restriction from other variables  
15.     public List>            neighbors = new ArrayList>();   // Connected variables  
16.       
17.     /** 
18.      * BD: The available values fit constraints. 
19.      * @return 
20.      */  
21.     public List cstValues()  
22.     {  
23.         List cstList = new ArrayList();  
24.         Set rstValueSet = new HashSet();  
25.         for(List vals:restricts.values()) rstValueSet.addAll(vals);  
26.         for(T t:domain) if(!rstValueSet.contains(t)) cstList.add(t);  
27.         return cstList;  
28.     }  
29.       
30.     public Variable(String n){this.name = n;}  
31.     public void setDomain(T ...vals)  
32.     {  
33.         for(T val:vals) domain.add(val);  
34.     }  
35.       
36.     public void addNeighbor(Variable ...vars){for(Variable var:vars) neighbors.add(var);}  
37.     public void addMNeighbor(Variable ...vars)  
38.     {  
39.         for(Variable var:vars)  
40.         {  
41.             neighbors.add(var);  
42.             var.neighbors.add(this);  
43.         }  
44.     }  
45.       
46.     @Override  
47.     public String toString()  
48.     {  
49.         StringBuffer strBuf = new StringBuffer("");  
50.         strBuf.append(String.format("%s", name));  
51.         if(value!=null) strBuf.append(String.format("(%s)", value));  
52.         return strBuf.toString();  
53.     }  
54.       
55.     @Override  
56.     public int compareTo(Variable o) {  
57.         Integer n1 = Integer.valueOf(neighbors.size());  
58.         Integer n2 = Integer.valueOf(o.neighbors.size());  
59.         return n2.compareTo(n1);  
60.     }  
61.       
62. }  

在 Constraint 的部分, 我定義了介面 IConstraint 說明如何進行 consistent 的確認: 

view plaincopy to clipboardprint?

1. package c6.mapcolor;  
2.   
3. public interface IConstraint {  
4.     public boolean isConsistent(Variable a, Variable b);  
5. }  

而其實作類別 ArcDiff 則限制了臨邊 variable 必須是不同值: 

view plaincopy to clipboardprint?

1. package c6.mapcolor;  
2.   
3. public class ArcDiff implements IConstraint{  
4.   
5.     @Override  
6.     public boolean isConsistent(Variable a, Variable b) {  
7.         if(a.value.equals(b.value))   
8.         {  
9.             return false;  
10.         }  
11.         return true;  
12.     }  
13. }  

最後便是演算法的實作: 

view plaincopy to clipboardprint?

1. package c6;  
2.   
3. import java.util.ArrayList;  
4. import java.util.HashMap;  
5. import java.util.LinkedList;  
6. import java.util.List;  
7. import java.util.PriorityQueue;  
8.   
9. import c6.mapcolor.IConstraint;  
10. import c6.mapcolor.Variable;  
11.   
12. public class Algorithms {  
13.   
14.     public static boolean BACKTRACKING_SEARCH(List variables, HashMap> cs)  
15.     {  
16.         List assignment = new LinkedList();  
17.         PriorityQueue pq = new PriorityQueue();  
18.         for(Variable v:variables) pq.add(v);  
19.         return BACKTRACK(pq, cs, assignment);  
20.     }  
21.       
22.     public static boolean BACKTRACK(PriorityQueue pq, HashMap> cs, List assignment)  
23.     {  
24.         if(pq.size()==0) return true;  
25.         Variable var = pq.poll();         
26.         for(Object v:var.cstValues())  
27.         {  
28.             var.value = v;  
29.             //System.out.printf("\t[Test] Check %s...\n", var);  
30.             boolean isConsistent = true;  
31.             List clist = cs.get(var);  
32.             for(IConstraint cst:clist)  
33.             {  
34.                 for(Object av:var.neighbors)   
35.                     if(!cst.isConsistent(var, (Variable)av))   
36.                     {         
37.                         System.out.printf("\t[Info] %s is inconsistent because of %s!\n", var, av);  
38.                         isConsistent = false;  
39.                         break;  
40.                     }  
41.             }  
42.             if(!isConsistent)   
43.             {                 
44.                 continue;  
45.             }  
46.             System.out.printf("\t[Info] Assign %s...\n", var);  
47.             if(!INFERENCE(var, cs)) continue;  
48.             assignment.add(var);              
49.             if(BACKTRACK(pq, cs, assignment)) return true;  
50.               
51.             assignment.remove(var);  
52.             pq.add(var);              
53.         }  
54.         for(Object nv:var.neighbors) ((Variable)nv).restricts.remove(var);  // Remove restriction owing to current var.  
55.         System.out.printf("\t[Info] %s is out of choice and backtrack...\n", var.name);  
56.         return false;  
57.     }  
58.       
59.     protected static boolean INFERENCE(Variable var, HashMap> cs)  
60.     {  
61.         // Forward checking  
62.         for(Object o:var.neighbors)  
63.         {                         
64.             Variable nv = (Variable)o;            
65.             if(nv.value!=null) continue;  
66.             List rstValues = new ArrayList();  
67.             nv.restricts.remove(var);  
68.             List clist = cs.get(var);  
69.             for(Object v:nv.cstValues())  
70.             {  
71.                 nv.value = v;  
72.                 for(IConstraint c:clist)  
73.                 {  
74.                     if(!c.isConsistent(var, nv))  
75.                     {  
76.                         System.out.printf("\t\tRestict %s to be %s owing to %s...\n", nv.name, v, var);  
77.                         rstValues.add(v);  
78.                         break;  
79.                     }  
80.                 }  
81.             }  
82.             nv.value = null;  
83.             nv.restricts.put(var, rstValues);  
84.             if(nv.domain.size() == nv.restricts.size())   
85.             {  
86.                 System.out.printf("\t[Info] %s is inconsistent now!\n", nv);  
87.                 return false;  
88.             }             
89.         }  
90.         return true;  
91.     }  
92. }  

Execution: 
接著便可以如下使用上述類別定義我們的問題並執行 Backtracking search 演算法: 

view plaincopy to clipboardprint?

1. package c6.mapcolor;  
2.   
3. import java.util.ArrayList;  
4. import java.util.HashMap;  
5. import java.util.LinkedList;  
6. import java.util.List;  
7.   
8. import c6.Algorithms;  
9.   
10. public class Main {  
11.   
12.     /** 
13.      * @param args 
14.      */  
15.     public static void main(String[] args) {  
16.         // 1) Define variables X={...} and corresponding domain of them D={...}  
17.         Variable wa = new Variable("WA"); wa.setDomain("Red", "Blue", "Green");  
18.         Variable nt = new Variable("NT"); nt.setDomain("Red", "Blue", "Green");  
19.         Variable sa = new Variable("SA"); sa.setDomain("Red", "Blue", "Green");  
20.         Variable q = new Variable("Q"); q.setDomain("Red", "Blue", "Green");  
21.         Variable nsw = new Variable("NSW"); nsw.setDomain("Red", "Blue", "Green");  
22.         Variable v = new Variable("V"); v.setDomain("Red", "Blue", "Green");  
23.         Variable t = new Variable("T"); t.setDomain("Red", "Blue", "Green");  
24.           
25.         // 2) Define constraint graph  
26.         wa.addMNeighbor(nt, sa);  
27.         nt.addNeighbor(sa, q);  
28.         sa.addNeighbor(q, nsw, v);  
29.         q.addNeighbor(nsw);  
30.         nsw.addNeighbor(v);  
31.         t.addNeighbor(v, nsw);  
32.   
33.         List variables = new ArrayList();  
34.         variables.add(wa);  
35.         variables.add(nt);  
36.         variables.add(sa);  
37.         variables.add(q);  
38.         variables.add(nsw);  
39.         variables.add(v);  
40.         variables.add(t);  
41.           
42.         // 3) Define constraints for variables C={}  
43.         IConstraint arcDiff = new ArcDiff();  
44.         List clist = new LinkedList(); clist.add(arcDiff);  
45.         HashMap> constraints = new HashMap>();  
46.         constraints.put(wa, clist);  
47.         constraints.put(nt, clist);  
48.         constraints.put(sa, clist);  
49.         constraints.put(q, clist);  
50.         constraints.put(nsw, clist);  
51.         constraints.put(v, clist);  
52.         constraints.put(t, clist);  
53.           
54.         // 4) Run the algorithm Backtracking search  
55.         if(Algorithms.BACKTRACKING_SEARCH(variables, constraints))  
56.         {  
57.             for(Variable var:variables)  
58.             {  
59.                 System.out.printf("\t[Answer] %s\n", var);  
60.             }  
61.             System.out.printf("\t[Test] Done!\n");  
62.         }  
63.         else  
64.         {  
65.             System.out.printf("\t[Test] Fail!\n");  
66.         }  
67.     }  
68. }  

執行結果為其中一組 Solution: 

[Info] Assign SA(Red)...
Restict WA to be Red owing to SA(Red)...
Restict Q to be Red owing to SA(Red)...
Restict NSW to be Red owing to SA(Red)...
Restict V to be Red owing to SA(Red)...
[Info] NT(Red) is inconsistent because of SA(Red)!
[Info] Assign NT(Blue)...
[Info] Assign T(Red)...
[Info] Assign V(Blue)...
[Answer] WA(Green)
[Answer] NT(Blue)
[Answer] SA(Red)
[Answer] Q(Green)
[Answer] NSW(Green)
[Answer] V(Blue)
[Answer] T(Red)

完整代碼可以在 這裡 下載.