인공지능개론 | Constraint Satisfaction Problem

⚠ Before reading the post ⚠

본 포스팅은 컴퓨터 공학 계열 전공자 대학교 4학년에서 대학원생 기준으로 작성하였습니다.
기본적인 자료구조나 알고리즘 내용은 생략하였습니다.

Constraint Satisfaction Problem | 제약 충족 문제

기존에는 문제를 해결하는데 있어서 상태가 알 수 없었던 상태(black box)였다면, 앞으로 해결할 문제들은 공역(domain) D 내에서 상태가 정의 된다. 이 때 목표에 대한 비용은 문제 영역으로 한정된(domain-specific) heuristic function으로 평가가 되며 모든 변수의 값이 해당 변수에 가해진 모든 constraint를 충족하면 문제가 풀릴 것이 오늘 알아볼 CSP이다. 대표적으로는 지도에 겹치지 않는 색상으로 최소한으로 색칠하기 문제가 있다. (반배정, 공장 스케쥴링, 시간표 배정 등등 여러가지 존재).

문제 solution은 항상 제약을 위반 하지 않고 일관성있으며 모든 배정이 이루어졌으므로 완전적이다. 이와 같은게 가능한 이유는 제약에 맞지 않을 경우, 추가적인 정련(refinement)가 즉시 폐기되므로 그 외 상황은 고려하지 않기 때문이다.
위 문제를 풀기 쉽게 하기 위해 우측 제약 그래프(constraint graph)를 이용하여 풀기도 한다. 예로는 cyptarithmetic이 있다.
아래는 변수의 분류다.


Discrete variables	finite domains	n variables, domain size d $O(d^n)$ : d의 경우가 각 n번씩이므로
Discrete variables	infinite domains	int ,string,,
Continuouts variables	-	linear constraints which is solvable in polynomial time ※ 시간과 같이 연속적인 값

Standard Search Formulation for CSP

들어가기 전 몇 가지 사항에 대해 알아보자.

initial state: empty statement
successor function: 후계자를 정할 때 현상태와 충돌하지 않으며 적법한(legal)한 변수를 할당한다. 물론, 일관성 유지를 위해 더 이상 legal variable이 domain에 없을 경우 실패로 처리한다.
goal test: 완전적(complete)이고 일관적(consistant)한가?
n depth: 정의역 크기가 d, 변수 n개로 이루어진 CSP 트리를 탐색할 때 DFS
b=(n-1)d at depth 1(root에서 assigned되고 나머지 경우 d개가 n-1개) → ${n!}\cdot{d^n}$ : exponential하게 커지므로 효율은 낮은 편.

결론은 여러 가지 variance(계층 node)에서의 가능한 경우 Domain 내 만족하는 경우 constraint를 만족한다.

Backtracking Search | 역추적 탐색

consistant하지 않은, 실패한 분기가 이전 최근 결정지점에 재방문하여 문제를 축소하여 변수를 줄이는 특징을 지니고 있다. 이 특징은 재귀함수가 내포되어 아래 pseudo code에서 볼 수 있듯, DFS 중 재귀함수를 사용한 방법과 동일하다.
각 노드에 하나의 변수만 고려하여 해결해 나가므로 branch가 d일 때 (b=d) 해당 계층에는 $d^n$ 개의 단말노드가 존재한다.

Backtracking 방법은 DFS를 사용하기 때문에 저장공간이 별도로 필요하나 선형적이다.

Improving Efficiency?

더 좋은 방법을 찾기 전에 몇 가지 고려할 점들이 있다.

"어떤 변수"를 다음에 successor로 둘까?
"어떤 순서"로 배치할까?
더 미리 실패를 알 수 없을까?

지도 색칠하기를 예로 다음 successor을 domain에서 어떻게 고르는지 확인해보자.

Methods	Summary
Most Constrained Variable	지도에서 가장 마주보는 state가 적은 부분부터 채워나간다. 이 때, Minimum Remaining Value를 heurstic function으로 정의한다.
Most Constraining Variable	더 많은 제한이 있는 부분을 우선(4면 다른 주)으로 채워나간다.
Least Constraining Value	1. 가장 적은 제한을 가진 영역을 선택 2. 그 다음 적은 제한을 가진 영역을 가진 주를 선택함으로써 소거해나간다. 분기점에서 SA가 가질 수 있는 더 많은 경우를 선택하게 된다. 3. 반복..

Forward Checking

위 방법에서는 CSP에서 variable을 결 정후 하나씩 할당해서 검색트리로 DFS로 해결했다. Forward checking은 모든 것을 assign한 상태에서 시작하여 value 값을 하나씩 고정하여 가능한 value를 제거하는 방법을 취하고 있다.

바주하지 않는, 비교적 자유로운 주들을 먼저 선택해나감으로써 해결해 나간다.
맨 마지막 이미지에서 해당 공간이 empty인 것은 domain에서 선택할 수 있는 변수가 없다는 것이므로 solution이 존재하지 않는다는 의미. 이 때 backtracking 하여 이전 지점으로 돌아가 다시 소거해나간다.

Wrap up & Conclusion

오늘 알아본 문제 해결 방법은 CSP로 정해진 state내에서 선택해나가여 문제를 풀어나가는 방법이다. 문제의 해결 조건은 완전적으로 풀어내느냐, 아니면 제한 조건을 지켜가며 일관성있게 풀어가느냐이다.

Backtracking: DFS와 유사하며 fail한 선택지일시 가장 최근 분기점으로 돌아가 문제를 해결해나간다. (1 Most Constrained Variable)가장 제한 조건이 덜한 (2개의 주를 마주보는 주)를 선택하여 할당하거나, (2 Most Constraining Variable) 가장 제한 조건이 많은 (4개의 주를 마주보는 주)를 먼저 선택하여 할당하거나, (3 Least Constraining Value) 가장 적은 제한을 가진 영역을 선택해나가 다음 적은 후행자가 선택할 수 있는 domain이 많은 경우를 선택해나가는 방법으로 3가지 정도로 배웠다.
Forward Tracking: Backtracking과는 다르게 미리 선택지들을 채워서 assigned된 상태에서 출발하여 상태를 고정하는 방법으로 풀어나간다. 비교적 자유로운 주들을 먼저 선택하고 마주하는 면들의 선택지가 존재하지 않을 경우 fail로 판단하여 최근 분기점으로 backtracking하여 해결해나가는 방법이다.

대학원 과제 실습으로 CSP를 이용하여 4 queens 문제를 풀어보기도 하였다. 이와 관련해서는.. 기말고사가 끝나면 올려보도록 하겠다. 실습 설명에선 Forward tracking으로 설명한 것 같은데, 나는 backtracking으로 풀었었다..!