Local Search for CSPs, Independent Subproblems, Tree-Structured CSPs

Local Search for CSPs, Independent Subproblems, Tree-Structured CSPs

728x90

반응형

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

, CSP는 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 을 찾는 것은 NP-hard 문제 이기 때문에 이는 지수 시간안에 해결되지 않을 가능성이 매우 높다.

Tree Decomposition (Also NP-hard problem) 원래의 CSP 를 부분 그래프들의 노드로 새로 만든 후, 부분 그래프들로 트리를 생성하는 것이다. 오리지널 그래프에 나타나는 변수가 적어도 한번은 트리에서 나타나야 한다. 오리지널 그래프에서 연결되어 있던 쌍이라면, 트리에서 적어도 하나의 쌍이 연결되어야 한다. 노드 하나가 두 개 이상 존재한다면, 그 사이를 연결한 모든 부분그래프에도 그 노드가 존재해야 한다. -> SA 와 SA 를 연결한 부분 그래프 두 곳 모두 SA 가 존재한다.

728x90

반응형

from http://jyeonnyang2.tistory.com/126 by ccl(A) rewrite - 2021-12-17 23:00:49