## 2012年11月5日 星期一

### [ Algorithm ] Map color problem - Using BACKTRACKING Search

Preface:

(使用四種顏色對大陸地圖著色

Problem analysis:

- 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}

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:

- 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
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.

- MRV: 在挑選 variable 時, 先選擇最有影響力的. 在這個問題中便是 SA. 因為它有 5 個臨邊, 一旦 SA 決定顏色, 其他臨邊便被限制不能是該顏色.

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

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

Programming:

- Variable:
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. }

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

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. }

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()==0return 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!=nullcontinue;
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:

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. }

[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)

## 關於我自己

Where there is a will, there is a way!