Path Consistency, K-Consistency, Global Constraints, Backtracking Search for CSPs

Path Consistency

- arc consistency 의 문제점

• Map coloring using two colors
• -> 해결책이 없다.
• 그러나 AC-3 알고리즘은 솔루션이 없음에도 이를 탐지하면 못한다. 왜냐하면 모든 변수가 이미 arc consistent 하기 때문이다. 

- 두 개의 변수 집합 {Xi, Xj} 가 제 3의 변수 Xm에 대해서 consistent 하다는 것은 , 

Xi 와 Xj 의 모든 할당 상태에 대해서 {Xi, Xm} 그리고 {Xm,Xj} 사이에 모든 constraint 를 만족하는 값을 할당하는 것이 가능할 때 consistent 하다고 정의한다. 

 

WA가 red, SA 가 green 이면 둘 사이에 path consistent 는 성립한다. 이때 WA와도 path consistent 를 만족하며 SA 와도 path consistent 를 만족하는 NT 는 없기 때문에 WA,SA는 NT 에 대해서 path-consistent 하지 않다.

 

 

 

K-Consistency

CSP 에 존재하는 임의의 k-1 개의 변수들과 consistent 한 할당들에 대해서, consistent 한 변수가 k번째 변수에 할당될 수 있다면 k-consistent 하다.

- CSP 가 strongly k-consistent 하다는 것은 k-consistent 한 동시에, k-1 consistent, k-2 consistent, ... , 1-consistent 하다는 것이다.

- 만약 CSP 가 n-consistent 하다면, 이런 알고리즘을 푸는데 O(n^2d) 시간이 걸리게 된다.

 

 

Global Constraints

- 관련된 변수가 정해지지 않고 문제에 따라 달라진다. ex) Alldiff

NT, SA, Q 는 실질적으로 Alldiff(NT,Q,SA) 가 존재하는 상황이다. 이때 이미 WA,NSW 가 red 이기 때문에 Alldiff 가 가능한 domain 은 red 를 제외한 {green, blue} 가 된다. 따라서 Alldiff 를 만족할 수 없다. 

-> 3가지 변수가 가능한 색깔이 2개밖에 없기 때문이다. 

 

 

Backtracking Search for CSPs

depth-search 를 할 때에 각 depth 마다 어떤 변수를 선택하는데 걸리는 시간을 줄인다.

즉, 미리 각 depth 별로 변수를 선택해놓고, 할당할 수 있는 변수가 없을 때에는 가장 최신의 분기점으로 돌아가는 backtrack 을 실행한다.

1번째에서 WA 를 미리 선택했을 때 WA가 가능한 색은 3가지이다.

WA가 red일때 NT가 가능한 색은 2가지이며, 이런 식으로 밑으로 탐색해가다가, 할당 가능한 것이 없으면 

다시 backtrack 해서 가능한 분기점으로 재탐색한다.

 

 

A Backtracking Search Algorithm

(1) -> 할당되지 않은 변수 중 하나의 변수를 선택한다.

(2) -> domain 중 무엇을 할당할지 선택한다.

(3) -> search 방향, search 가 더 이상 필요없는지 등을 알아낼 수 있다.

 

- (1),(2) 은 heuristic 으로, csp 로 정의되는 문제라면 어떤 문제냐에 상관없이 공통으로 적용될 수 있다.

-> CSP 의 장점, does not need domain-specific knowledge

 

 

Variable Ordering

위 알고리즘의 (1)번.

var <- SELECT-UNASSIGNED-VARIABLE(csp)

• Minimum-remaining-values (MRV) heuristic (fail-first)
• 가장 값이 적게 남아 있는 변수를 선택한다.

• 

  -> 경우의 수가 가장 적게 남은, SA 를 선택한다.-> 즉, 경우의 수가 가장 적으므로 fail 을 빨리 찾게 해주는 변수이다.
• -> heuristic 이므로 항상 맞다는 것을 보장하지는 않는다.

 

• Degree heuristic
• MRV heuristic 을 사용할 수 없는 경우 (색이 하나도 할당되지 않는 경우 최소로 남은 변수가 없다.)
• 차수가 가장 높은 것을 선택한다. (다른 변수에 가장 영향을 많이 주는 변수)
• SA 는 5개의 변수와 연결되어 있다.

• 

Value Ordering

알고리즘의 (2)번.

- Least-constraining-value (LCV) heuristic (fail-last)

- 할당 가능한 값을 가장 많이 남기는 값 (주변에 제약을 가장 적게하는 값) 을 선택한다.

Q 는 red 또는 blue 가 선택될 수 있다.

• red 로 칠해진 경우, SA는 green, blue 가 가능하고, NSW 는 green, blue 가 가능하다.
• blue 로 칠해진 경우, SA 는 할당 가능한 값이 없고, NSW 는 red, green 이 가능하다.

-> 따라서 할당 가능한 값이 더 많이 남는 red 를 선택하게 된다.

 

 

Interleaving Search and Inference

알고리즘의 (3)번.

- Forward checking

1) WA 에 red를 할당을 한 후, NT, SA 의 domain 에서 red 를 제거한다.

2) Q 에 green 을 할당한 후, NT 와 SA, NSW 의 domain 에서 green 을 제거한다.

-> 즉 연관된 변수들의 consistency check 를 통해 domain 의 값들을 줄여준다.