[인공지능] CSPs- 4

𝐾-Consistency

𝐾-Consistency

1-Consistency / 3 - Consistency / 2 - Consistency

• 일관성 정도의 증가(Increasing degrees of consistency) : 일관성의 정도는 𝐾의 값에 따라 증가한다.
  • 1-Consistency (Node Consistency)
    • 각 단일 노드의 도메인에는 해당 노드의 단항 제약 조건(unary constraint)을 충족하는 값이 있다.
  • 2-Consistency (Arc Consistency):
    • 노드 쌍마다(each pair of node) 하나에 일관된 할당이 다른 하나로 확장될 수 있다.
  • K-Consistency:
    • k개의 노드마다 k-1에 대한 일관된 할당이 k번째 노드로 확장될 수 있다.
• 더 높은 k 값을 계산하려면 더 비싸지게 된다.
• (k=2의 경우 :Arc Consistency)

Strong 𝐾-Consistency

• Strong 𝑘-consistency : 강한 𝑘-일관성은  𝑘-1, 𝑘-2, ... 1까지도 일관성이 있어야 한다.
• 주장(Claim): 강한 𝑛-일관성이 있다면 되돌리기(backtracking) 없이 문제를 해결할 수 있다!
• Why?
  • 어떤 변수에 대한 임의의 할당을 선택한다.
  • 새로운 변수를 선택한다.
  • 2-consistency에 따라, 첫 번째와 일관된 선택이 있다.
  • 새로운 변수를 선택한다.
  • 3-consistency에 따라 첫 번째 2개와 일관된 선택이 있다.
  • ... (이런 식으로 계속된다.)
• Arc Consistency와 𝑛-Consistency 사이에는 많은 중간 지점(middle ground)이 있다!
• (예: 𝑘=3, 이것을 경로 일관성path consistency이라고 합니다.)

---

Ordering

Ordering: Minimum Remaining Values

• 변수 순서 지정(Variable Ordering): 최소 남은 값 (Minimum Remaining Values, MRV)
  
  • 그 도메인에서 합법적으로(legal) 남아있는 값이 가장 적은(fewest) 변수를 선택한다.

• 왜 최대값이 아닌 최소값을 사용하는가?
  • 최소 남은 값 전략은 가장 제약이 많은 변수, 즉 가능한 값이 가장 적은 변수를 먼저 선택하여 빠르게 실패할 가능성이 높은 경로를 먼저 탐색하려는 전략이다. 이렇게 하면 빠르게 해결책을 찾거나 빠르게 실패 경로를 제거하여 효율적인 검색을 수행할 수 있다.
• "가장 제약이 많은 변수"(most constrained variable) 라고도 부른다.
• "Fail-fast" ordering:
  • 이 전략은 가능한 한 빨리 실패하는 경로를 찾아내려는 것을 목표로 한다. 이렇게 하면 비효율적인 경로를 빠르게 제거하고 해결책을 더 빨리 찾을 수 있다.

이 정보는 문서의 페이지 38에 위치해 있습니다. MRV는 CSPs의 제약 조건을 만족시키기 위한 중요한 변수 순서 지정 전략으로, 검색 과정에서 어떤 변수를 먼저 고려해야 하는지 결정하는 데 사용됩니다.

Ordering: Least Constraining Value

• 값 순서 지정: 최소 제약 값 (Least Constraining Value)을 사용
  • 변수를 선택한 후, 가장 제약이 적은 값을 선택한다.
  • 즉, 남아있는 변수에서 가장 적은(fewest) 값을 제외시키는(rules out) 값을 선택한다.
  • 이를 결정하는 데에는 일부 계산이 필요할 수 있다! (예: filtering을 다시 실행하는 경우)
• 왜 최소값을 사용하는가?
  • 최소 제약 값 전략은 다른 변수에 대한 선택의 자유도를 최대한 유지하려는 것을 목표로 한다. 즉, 선택된 값이 다른 변수에 미치는 영향을 최소화하여 검색 공간을 넓히려는 전략이다.
• 이러한 순서 지정 아이디어를 결합(combining ordering ideas)하면 1000 퀸 문제도 해결 가능해진다.

---

Structure

Problem Structure

문제의 구조를 이해하는 것은 CSPs를 효과적으로 해결하는 데 중요한 역할을 한다. 특히 독립적인 부분 문제들을 식별하면 전체 문제를 더 빠르게 해결할 수 있다.

• 극단적인 경우(extreme case): 독립적인 부분 문제들(independent subproblems)
  • 예: 타스마니아(T)와 본토(mainland)는 상호 작용하지 않는다.(do not interact)
• 독립적인 부분 문제들은 제약 그래프(constraint graph)의 연결된 구성 요소(connected componet)로 식별될 수 있다. (identifiable)
• 제약 그래프의 n개의 변수가 c개의 변수만 있는 부분 문제로 나눌 수 있다고 가정해보자:
  • 최악의 경우 해결 비용은 O((n/c)(d^c))이며, 이는 n에 선형적(linear)이다.
  • 예를 들어, n = 80, d = 2, c =20인 경우
    • 2^80 = 40억 년 at 1000만 nodes/sec
    • (4)(2^20) =  0.4초 at 1000만 nodes/sec에서

Tree-Structured CSPs

Tree-Structured CSPs는 제약 그래프가 트리 구조를 가질 때 해당 CSPs를 효과적으로 해결할 수 있음을 나타낸다. 루프가 없는 구조는 계산 복잡성을 크게 줄일 수 있으며, 이는 확률론적 추론과 같은 다른 문제 영역에도 적용될 수 있다.

• 정리(Theorem):
  • 제약 그래프에 루프(loop)가 없다면, CSPs는 O(nd^2) 시간 내에 해결될 수 있다.
    • 최악의 경우(worst case)의 시간이 O(d^2)인 일반적인 CSPs와 비교한 것.
• 이 속성(property)은 확률론적 추론(probability reasoning)에도 적용된다. (나중에):
  • 위 그림은 구문 제한(syntactic restriction)과 추론의 복잡성(complexity of reasoning) 사이의 관계의 한 예시이다.??

• 트리 구조 CSPs에 대한 알고리즘: 루트에서 시작하여 트리의 각 노드에 대해 일관성 있는 값을 할당하면서 트리를 통해 전진한다.
  • 순서: 루트 변수를 선택하고, 부모가 자식보다 앞선(precede) 순서로 변수를 정렬한다.
  • 뒤로 제거(Remove backward): i = n : 2에 대해, RemoveInconsistent(Parent(Xi), Xi)를 적용한다.
  • 앞으로 할당(Assign forward): i = 1 : n에 대해, Xi를 Parent(Xi)와 일관성 있게 할당한다.
  • Runtime: O(nd^2) (why?) 런타임이 O(nd^2)인 이유는 각 변수에 대해 d 가능한 값들을 고려하면서 그래프의 각 간선에 대해 일관성을 확인해야 하기 때문이다.

• 주장 1(Claim 1): 뒤로 가는 단계를 거친 후(After backward pass), 모든 루트에서 리프로의 호(all root-to-leaf arc)는 일관성이 있다.
  • 증명(Proof) : 각 X -> Y는 한 시점에 일관성 있게 만들어졌고, Y의 도메인은 그 후 줄어들지 않았다. (Y의 자식들이 Y 전에 처리되었기 때문에).
• 주장 2(Claim 2): 루트에서 리프로의 호가 일관성이 있다면, 전방 할당(forward assignment)은 되돌리지(backtrack) 않을 것이다.
  • 증명(Proof): 위치에 대한 귀납법 (Induction to position)
• 왜 이 알고리즘은 제약 그래프에 사이클(cycle)이 있을 때 작동하지 않는가?
  • 트리 구조가 아닌 그래프에서는 변수 간의 순서가 명확하지 않기 때문에, 일관성을 보장하는 뒤로 가는 단계와 전방 할당 단계가 제대로 작동하지 않을 수 있다.
•  Bayes' nets에 대해 배울 때 이 기본 개념을 다시 볼 것임.