Path Consistency, K-Consistency, Global Constraints, Backtracking Search for CSPs
아뵹젼
2021. 12. 17. 19:41
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
