Local Search for CSPs
- Complete state formulation (처음엔 initial state 에 무작위로 queen 을 다 배치한다.)
- constraint 를 위반하는 변수를 랜덤으로 선택한다.
- 선택한 변수의 값을 변경해준다. (여기서는 퀸의 위치를 변경한다.)
- min-conflicts 에 해당하는 값으로 변경한다.
- 다음으로 선택한 퀸을 최소제약 즉 0의 위치로 옮기게 되면 solution 을 찾게된다.
- solution
Independent Subproblems
위 문제에서 T는 위의 6개의 node 들과 독립적이기 때문에, 독립적인 두 개의 문제를 별도로 푸는 것과 같다.
-> 같이 풀 때는 ()^7 이던 시간복잡도가 따로 풀게 된다면 ()^6 + ()^1 로 훨씬 줄어들 수 있다.
- graph 에서 connected components 를 찾는 것이 subproblem 을 결정하는 것이다.
-> BFS, DFS 로 connected components 를 찾을 수 있다. (O(v+e))
Tree-Structured CSPs
- Constrained trees : 두 변수는 하나의 path 로만 연결된다.
-> 왼쪽의 그래프는 트리가 아니고, 오른쪽은 트리가 맞다.
-> 따라서 왼쪽은 순서가 존재할 수 없고, 오른쪽은 순서가 존재한다.
T는 노드가 1개 이므로 tree가 맞고, 위의 subproblem 은 트리가 아니다.
- tree structured CSP 는 node 개수 n만큼의 선형 시간에 해결될 수 있다. O(n)
- Directed arc consistency (DAC)
- X1, X2, ... , Xn 의 순서를 가지는 node 들이 존재할 때, j>i 일때 (즉, xi는 xn보다 앞에 있는 노드이다.) Xi 가 항상 Xj 에 대해서 arc-consistent 하다면 , CSP는 DAC하다.
- ex) 다음과 같은 순서를 가지는 CSP 에서, x1이 x2 에 대해서 arc-consistent 하고, x1는 x3에 대해서, x2는 x3에 대해서 arc consistent 하다면 다음 CSP 는 DAC하다.
Topological Sort(위상정렬) of Constrained Trees
- tree 에 존재하는 아무 노드를 root 로 선택한다.
- 예)
- A를 루트로 선택한다.
- B를 루트로 선택한다면?
-> O(n) 시간에 위상정렬이 가능하고, 그 후에 n-1번(간선 개수)의 arc-consistent 확인을 통해 DAC 를 체크한다.
Making a Constrained Tree DAC
-> 간선 마다 arc-consistency 를 체크하고, 그렇지 않다면 arc-consistent 하게 만들어주는 작업을 한다.
한 간선에 걸리는 시간이 O(d^2) 시간으로, 이는 도메인 x 도메인의 조합으로 이루어지기 때문이다. 따라서 DAC 을 만드는데 걸리는 총 시간은 O(nd^2) 이 된다.
-> 어떤 변수의 domain 이 null 이 되었다면 arc-consistent 하게 만들 수 없음을 의미하므로 CSP 가 DAC 하지 않음을 바로 알 수 있다. 만약, 그렇지 않고 모든 변수가 domain 이 하나 이상 남아있다면 domain 중 어떤 값을 선택해도 정점과 정점 사이에 arc-consistent 가 참이기 때문에 O(n) 시간에 바로 solution 을 찾을 수 있다.
Transform a General Constraint Graph into a Tree
- 대부분의 문제는 tree 가 아닌 경우가 많다.
- 따라서 문제를 tree 로 만들어 줄 수 있다.
- Remove some nodes
- 제거하려는 값을 확정하고, 제거되려는 노드와 연결된 모든 노드들에서 그 값을 지워야 한다.
- 즉, TA 를 제거하기 위해 TA 의 값을 파랑으로 결정했다면, TA 와 연결된 모든 노드들의 domain 에서 파랑색을 지워야 한다. (TA 는 파랑이므로, 연결된 값들은 파랑이 될 수 없다.
- -> 그러나 복잡한 문제에서는 노드를 제거해서 트리를 만드는 것이 어렵다.
- - Cycle cutset : 지웠을 때 Tree 로 만들 수 있는 최소 노드 수 : NP-Hard 문제
- -> 가장 작은 cycle cutset 을 찾는 것은 NP-hard 문제 이기 때문에 이는 지수 시간안에 해결되지 않을 가능성이 매우 높다.
- Tree Decomposition (Also NP-hard problem)
- 원래의 CSP 를 부분 그래프들의 노드로 새로 만든 후, 부분 그래프들로 트리를 생성하는 것이다.
- 오리지널 그래프에 나타나는 변수가 적어도 한번은 트리에서 나타나야 한다.
- 오리지널 그래프에서 연결되어 있던 쌍이라면, 트리에서 적어도 하나의 쌍이 연결되어야 한다.
- 노드 하나가 두 개 이상 존재한다면, 그 사이를 연결한 모든 부분그래프에도 그 노드가 존재해야 한다. -> SA 와 SA 를 연결한 부분 그래프 두 곳 모두 SA 가 존재한다.
댓글