[인공지능] Tree structured CSP

Tree structured CSP

Constraint tree : 모든 변수에 대해서 임의의 두 변수를 잇는 경로가 1개만 존재하는 Graph

Tree structured CSP 는 변수의 개수 n에 대해 선형시간에 해결 가능

DAC(Directed Arc Consistency)

변수 X 가 X1, X2, X3, … , Xn 순서로 나열되어 있을 때 i < j 인 모든 i, j에 대해서 Xi 가 Xj 에 대해 arc consistent 하다면 DAC

Tree 는 변수들간의 순서를 정해주기 편리함

Topological sort (위상정렬)

아무 변수나 Root 로 지정하고, 상하관계를 만들어주는 단순한 방식

B 를 Root 로 선정한 방식

Time complexity : O(n)

 

이렇게 만들어진 Topological sorted tree 에서 모든 부모→ 자식으로 Arc-consistency 검사를 수행하여 아닌 Domain 원소가 발견되면 제거

B → A : B의 Domain 원소 중 A와 arc consistency 를 해치는 원소는 제거 : O(d^2)

B → C : 위와 동일 : O(d^2)

B → D : 위와 동일 : O(d^2)

D → E : 위와 동일 : O(d^2)

D → F : 위와 동일 : O(d^2)

따라서 시간 복잡도는 O(n * d^2)

 

이렇게 진행하여 empty 인 변수(노드)가 하나라도 존재하면 답이 없고, 그렇지 않으면 답이 존재.

DAC 가 성공적으로 만들어졌다면 Root 노드의 값이 하나 결정되는 순간 나머지 모든 변수의 값이 할당될 수 있음 ( 이 과정이 O(n))

일반 그래프를 Tree 로 만드는 방법

Node Removal(몇 개의 노드를 지우는 방법)

특정 노드를 지우되 해당 노드는 Domain 중 하나의 값으로 고정한 뒤 제거

Tree 가 되었을 때까지 노드를 지워가며, 지우는 도중 failure 하게 되면 지운 노드를 다른 value 로 고정한 뒤 다시 제거

Cycle cutset : 지웠을 때 Tree 로 만들 수 있는 최소 노드 수 : NP-Hard 문제

Tree decomposition (트리 합치는 방법) : NP-Hard

그래프를 작은 트리로 쪼개서 이들을 Mega Node 라 칭하고, 이들로 Tree 를 만드는 방법

 

Mega node 의 조건

• 모든 변수가 최소 1번 tree 에도 나타나야함

• 원래 노드끼리 연결되어 있다면 Mega node 끼리도 연결되어야함

• 동일한 노드를 공유한 Mega node 끼리도 연결되어야함