[인공지능] CSPs - 5

Improving Structure

Nearly Tree-Structured CSPs

"Nearly Tree-Structured CSPs"는 제약 그래프가 정확히 트리 구조는 아니지만, 트리 구조에 가까운 CSPs를 효과적으로 해결하기 위한 방법을 제시합니다. Cutset 조건화를 통해 그래프에서 사이클을 제거하고 트리 구조를 만들어, 트리 구조 CSPs의 효율적인 알고리즘을 적용할 수 있게 된다.

• 조건화(Conditioning)
  • 변수를 인스턴스화(instantiate)하고(즉, 특정 값으로 설정하고) 그 이웃의 도메인을 가지치기(prune)한다.
• Cutset 조건화(Cutset Conditioning)
  • 남아있는 제약 그래프가 트리가 되도록 변수의 집합을 (모든 방법으로) 인스턴스화(instantiate)한다.
  • 이렇게 하면 원래의 그래프에서 사이클을 제거하여 트리 구조를 만들 수 있다.
• Runtime
  
  • Cutset size c에 대해
  • O( (d^c) (n-c) d^2 )로,
  • c가 작은 경우 매우 빠르다.
  • 여기서 d는 각 변수의 도메인 크기, n은 전체 변수의 수를 나타낸다.

Cutset Conditioning

Cutset Conditioning은 제약 그래프가 트리 구조가 아닌 CSPs를 해결하기 위한 방법이다. 주요 아이디어는 그래프에서 사이클을 제거하여 트리 구조를 만들고, 그 결과로 생성된 트리 구조 CSPs를 효과적으로 해결하는 것이다.

• choose a Cutset
  • 제약 그래프에서 사이클을 제거하기 위해 제거해야 할 변수의 집합인 cutset을 선택합니다. 이 cutset을 제거하면 그래프는 트리 구조가 된다.
• Instantiate the cutset (all possible ways) (Cutset 인스턴스화) 
  • 선택한 cutset의 모든 변수를 모든 가능한 방법으로 인스턴스화(즉, 특정 값으로 설정)한다. 이렇게 하면 각 변수 할당에 대한 다양한 부분 문제가 생성된다.
• Compute residual CSP for each assignment (각 할당에 대한 잔여 CSP 계산)
  • 각 변수 할당에 대해 남아있는 제약 그래프(즉, 잔여 CSP)를 계산한다. 이 그래프는 트리 구조를 가지게 된다.

• Solve the residual CSPs (tree structured) (잔여 CSPs 해결)
  • 각 잔여 CSP는 트리 구조이므로, 트리 구조 CSPs를 해결하기 위한 효율적인 알고리즘을 사용하여 해결할 수 있습니다.

Cutset Quiz

Find the smallest cutset for the graph below. (아래 그래프에 대한 가장 작은 cutset을 찾으시오.)

Tree Decomposition*

Tree Decomposition은 복잡한 제약 그래프를 가진 CSPs를 해결하기 위한 방법 중 하나이다. 이 방법은 그래프를 여러 개의 더 간단한 트리 구조로 분해하여 문제를 더 효율적으로 해결할 수 있게 한다.

• 개념(idea): 메가-변수(mega-variable)의 트리 구조 그래프를 생성한다.
  • 여기서 "메가-변수"란 원래의 CSP의 일부를 인코딩하는 더 큰 변수를 의미한다. 이러한 메가-변수는 원래의 문제를 더 큰 덩어리로 나누어 표현한다.
• 각 메가-변수는 원래 CSP의 일부를 인코딩(encode)한다.
  • 이렇게 함으로써, 원래의 복잡한 문제를 여러 개의 더 간단한 부분 문제로 분해할 수 있다.
• 부분 문제들은 일관된 해결책을 보장(ensure)하기 위해 겹친다(overlap)
  • 부분 문제들 사이에는 겹치는 부분이 있어야 한다. 이렇게 함으로써, 각 부분 문제의 해결책이 다른 부분 문제의 해결책과 일관성을 유지할 수 있다. 즉, 하나의 부분 문제에서 얻은 해결책이 다른 부분 문제의 해결책과 충돌하지 않도록 한다.

---

Iterative Improvement

Iterative Algorithms for CSPs

Iterative Algorithms는 CSPs를 해결하기 위한 방법 중 하나로, 초기 할당에서 시작하여 반복적으로 변수 값을 변경하여 문제를 해결하려고 시도한다. 이 방법은 특히 제약 조건이 많이 위반된 경우나 초기 할당이 부정확한 경우에 유용하다. Min-conflicts 휴리스틱은 현재 할당에서 가장 적은 수의 제약 조건을 위반하는 값을 선택하여, 빠르게 문제를 해결하는 데 도움을 준다.

• 로컬 검색 방법은 일반적으로 "완전한"(complete) 상태, 즉 모든 변수가 할당된 상태에서 작동한다.

• CSPs에 적용하기 위해:
  • 만족되지 않은 제약 조건이 있는 할당을 취한다.
  • 연산자(operator)는 변수 값을 재할당한다.
  • 프린지(fringe)가 없다! 경계(edge)에서 살아남는다.(live)
• 알고리즘: 해결되지 않은 동안,(While not solved,)
  • 변수 선택: 충돌하는 변수 중에서 무작위로 선택한다.
  • 값(value) 선택: min-conflicts heuristic:
    • 제약 조건을 가장 적게 위반하는(violate) 값을 선택한다.
    • 즉, <h(n) = 위반된 제약 조건의 총 수>로 hill climb을 한다.

Example: 4-Queens

• 상태 (States) :
  • 4개의 퀸이 4개의 열에 위치한다. 이로 인해 가능한 상태의 총 수는 4^4=256 상태이다.
• 연산자 (Operators):
  • 열 내에서 퀸을 이동시킨다.
• 목표 테스트 (Goal test):
  • 공격이 없어야 한다(no attack). 즉, 어떤 두 퀸도 서로를 공격할 수 있는 위치에 있어서는 안 된다.
• 평가 (Evaluation):
  • c(n)는 공격의 수를 나타낸다. 이 평가는 현재 상태에서 퀸들 사이의 공격 횟수를 나타낸다.

Performance of Min-Conflicts

Min-Conflicts 휴리스틱은 지역 검색 알고리즘에서 사용되며, 현재 상태에서 최소한의 충돌을 초래하는 값을 선택하는 방식으로 작동한다. 이 휴리스틱은 특히 n-queens와 같은 문제에서 높은 성능을 보이며, 큰 n 값에 대해서도 효과적으로 문제를 해결할 수 있다. 또한, 임의로 생성된 다른 CSPs에 대해서도 이러한 성능 특성이 유지되는 것으로 보인다.

• 주어진 무작위 초기 상태에서, 높은 확률로 임의의 n에 대해 n-queens 문제를 거의 일정한(constant) 시간 내에 해결할 수 있다. 예를 들어, n이 10,000,000인 경우에도 이러한 성능을 보일 수 있다.
• 표를 참고하면, 위와 같은 성능은 비율의 좁은 범위(in a narrow range of ratio)를 제외하고 임의로 생성된 모든 CSP에 대해서도 참으로 보인다.

---

Summary: CSPs

• CSPs는 특별한 종류의 검색 문제이다.
  • 상태 (States)는 부분 할당(partial assignment)이다. 즉, 모든 변수에 값이 할당되지 않은 상태를 의미한다.
  • 목표 테스트 (Goal test)는 제약 조건(constraint)에 의해 정의된다. 모든 제약 조건이 만족될 때 목표 상태에 도달한 것으로 간주된다.
• 기본 해결 방법(Basic solution) : 백트래킹 검색(backtracking search)
• 속도 향상 방법:(speed-ups)
  • 정렬 (Ordering): 변수와 값의 선택 순서를 최적화하여 검색 공간을 줄인다.
  • 필터링 (Filtering): 현재의 부분 할당과 호환되지 않는 변수 값들을 제거하여 검색 공간을 줄인다.
  • 구조 (Structure): 문제의 구조를 활용하여 검색을 최적화한다. 예를 들어, 문제가 트리 구조를 가지면 더 효율적인 알고리즘을 사용할 수 있다.
• 반복적인(iterative) min-conflicts 실제로 자주 효과적이다. 이 방법은 현재 상태에서 최소한의 충돌을 초래하는 값을 선택하여 문제를 반복적으로 해결하려고 시도한다.