제약 충족 문제 Constraint Satisfaction Problems(CSP)

Constraint Satisfaction Problems

---

- search problems의 special subset

- State는 도메인 D의 값을 가진 변수 에 의하여 정의된다.

- Goal test는 변수의 하위 집합에 허영되는 값의 조합을 지정하는 제약 조건 집합.

아 인공지능 배우면서 느끼는건 말이 더 어렵다. 해보는게 더 쉬운 접근법이다.

CSP Examples

---

Variables: WA, NT, Q, NSW, V, SA, T

Domains: D = { Red, Green, Blue }

Constraints: 인접한 지역은 서로 다른 색이여야 한다.

Implicit: 

Explicit: 

Solutions: 모든 Constraints를 충족시키는 것이며 솔루션은 유니크 하지 않을 수 있다.(솔루션이 여러개일 수 있음). 여러 솔루션 중 하나는 위의 이미지와 같다.

Constraint Graphs

---

제약조건을 끼치는 노드끼리 엣지로 연결해준다. T(Tasmania)는 섬이라 다른 지역과는 인접하지 않아 아무런 제약조건이 없기에 타 노드와 엣지로 연결되있지 않다.

Backtracking Search

---

솔루션을 찾기 위해 우선 DFS 방식으로 노드를 확장시켜 나가 본다. 확장시켜 나가다가 제약조건에 걸리게 되면 부모노드로 Backtracking 하여 방문하지 않은 다른 노드를 확장시켜 나간다.
이것은 매우 간단한 솔루션인데 이제 이 솔루션을 개선시킬 방법을 생각해보자. 제일 먼저 생각이 드는 것은 Backtracking를 미연에 방지하여 노드 확장 횟수를 줄이는 것이다. 이를 위해 Filtering 기법이 들어간다.

Forward Checking

---

Filtering을 사용하여 Backtracking Search보다 수고를 줄인다. 예를 들어 WA에 Red를 칠했다면 WA와 연결 된 NT, SA에서 Red 색을 지운다. Q에 Green을 칠했다면 NT, SA, NSW에서 Green을 지웠다. 이렇게 한다면 Backtracking Search보다는 수고가 훨씬 줄어들게 된다. 하지만 이것도 만족스럽지는 않다.

Arc Consistency

---

색칠된 모든 노드와 인접한 노드간의 일관성을 체크한다. 모순이 발생하는지 체크를 해보는 것이다. 포워드 체킹과 차이점이 뭔지 헷갈릴 수 있다. 포워드 체킹은 WA 노드에 Red를 칠하면 A와 인접한 노드에서 Red를 지운다. 이 지워진 노드를 Arc라고 하자. 그리고 Q에서 Green을 칠하면 NT, SA, NSW에서 Green이 지워지는데 지워진 노드 3개를 또 아크로 본다. 그럼 Arc는 4개가 되고 이 Arc간의 Consistency를 보는 것이다. 위 이미지에서는 NT와 SA Arc에서 모순이 일어났기에 WA, Q 중 하나는 다른 색으로 칠해져야 하고 이 다른색으로 칠하러 돌아 가는 것이 Backtracking이다.

K-Consistency

---

- Increasing degrees of consistency

1-Consistency(Node Consistency): 각 노드의 도메인은 해당 노드의 고유한 제약 조건을 충족하는 값을 가진다.

2-Consistency(Arc Consistency): 각 노드 쌍에 대해 consistent를 다른 노드에 연장할 수 있다.

K-Consistency: 각 K 노드에 대해 k-1에 대해 consistent를 노드에 연장할 수 있다.

- K가 높아질수록 컴퓨팅 비용이 증가한다.

- (You need to know the k=2 case: arc consistency)

Ordering: Minimum Remaining Values(MRV)

---

Variable Ordering: Minimum remaining values (MRV): 다음 할당해야할 변수로 Minimum remaining values를 할당한다. MRV를 most constrained variable라고도 부르며 이 오더링을 "Fail-fast" ordering이라 한다.

Ordering: Least Constraining Value(LCV)

---

Value Ordering: Least Constraining Value: 변수를 택할때 제약 조건이 가장 적은 값을 선택한다. 예를 들어 나머지 변수 중에서 가장 작은 값을 규정하는 변수를 택하는 것. 이때 필터링을 다시 실행하는 등의 계산이 필요할 수 있다. LCV Ordering을 적용하지 않을 경우 도메인이 조금만 많아져도 계산에 무리가 있으나 적용할 경우 계산 가능 도메인 수의 한계가 급격히 올라간다.

Tree-Structure CSPs

---

Theorem: 제약 그래프에 루프만 없다면 CSP는 에 풀 수 있다.

Order:  루트 변수를 택하고 변수를 정렬하여 부모가 자식보다 앞서도록 한다.

Remove Backward: i=n:2의 경우 를 적용

Assign forward: i=1:n의 경우 를 로 지정한다.

Nearly Tree-Structured CSPs

---

- Conditioning: 변수를 인스턴스화 하고 이웃 도메인을 prune 해버린다.

- Cut set conditioning: 나머지 제약 그래프가 트리가 되도록 변수 세트를 인스턴스와 한다.

- Cut set size c는 small c에 대해 매우 빠른 런타임을 제공한다.

Iterative Algorithms for CSPs

---

- Local search methods는 일반적으로 "complete" states에서 작동합니다. i.e., all variables assigned

- To apply to CSPs:

불만족스러운 constraints로 과제를 수행한다.

Operators가 variable values를 재할당 한다.

프린지는 필요없다. Live on the edge.

- Algorithm: While not solved

Variable selection: conflicted variable를 랜덤하게 선택한다.

Value selection: min-conflicts heuristic:

가장 적은 constraints를 위반하는 value를 선택한다.

i.e., h(x) = 위반 된 제약 조건의 총 갯수

Summary: CSPs

---

- CSP는 special kind한 search problem 입니다.

States는 partial assignments입니다.

Goal test는 constraints에 따라 정의됩니다.

- Speed-Ups:

Ordering

Filtering

Structure-turns out trees are easy!

- Iterative min-conflicts는 꽤 효과적일떄가 있다.

- Basic solution: backtracking search