본문으로 이동

AC-3 알고리즘

위키백과, 우리 모두의 백과사전.

이 문서는 제약 만족 문제에 관한 것입니다. AC-3 오디오 코덱에 대해서는 돌비 디지털 문서를 참고하십시오.

AC-3 알고리즘(Arc Consistency Algorithm #3)은 제약 만족 문제 (약어로 CSP)를 풀기 위한 일련의 알고리즘 중 하나이다. 1977년 앨런 맥워스가 고안하였다. 이전의 AC 알고리즘은 효율적(efficient)이지 않다고 여겨져 왔다. AC-3 이후의 것들은 구현하기 너무 복잡하다고 간주된다. 따라서 간단한 제약 만족 문제 해법으로서는 AC-3이 가장 많이 사용되는 알고리즘의 하나이다.

알고리즘[편집]

AC-3 알고리즘은, 주어진 제약, 변수, 변수의 정의역(domains) 내에서 동작한다. 변수는 여러 이산(discrete) 값을 가질 수 있다; 어떤 변수가 가질 수 있는 값들의 집합을 가리켜 정의역(혹은 변역)이라 한다. 제약이란 변수가 가질 수 있는 값을 제한하거나 제약하는 관계를 말한다. 제약은 어떤 다른 변수의 값에 관계된 것을 수도 있다.

제약 만족 문제는 유향 그래프로서 표현될 수 있다. 꼭짓점이 변수가 된다. 꼭짓점 사이의 변들은 제약조건을 나타낸다. AC-3 알고리즘은 변수들 (x, y)의 순서쌍 변을 하나하나 보며 진행된다. x와 y 사이의 제약 조건과 불일치(inconsistent)한 x와 y의 값들이 있으면 x와 y의 정의역에서 각각 제거해나간다.

설명을 위해, 간단한 제약 문제 하나를 예로 들겠다: X (변수)는 값으로서 {0, 1, 2, 3, 4, 5} 중 하나를 가질 수 있다. -- 이러한 값들의 집합이 X의 정의역이 된다. D(X)라고 적는다. 마찬가지로 변수 'Y가 정의역 D(Y) = {0, 1, 2, 3, 4, 5}를 갖는다고 하자. 제약 C1 = "X는 짝수이어야 한다.", C2 = "X + Y는 4이어야 한다."를 추가하면, 이제 AC-3으로 해결할 수 있는 제약 조건 문제(CSP)가 된다. 여기서, 앞서 말한 문제의 그래프 그림에서는, 제약 C2가 무방향성(undirected)이므로 X와 'Y 간의 두 개의 변(edge)이 방향이 없는 변(undirected edge)인 것인 데 반해, 일반적으로 AC-3 알고리즘이 이용하는 그래프 그림은 방향이 있는 변(directed edge)을 쓴다는 것에 유의해야 한다.

우선, X의 정의역에서 제약 C1에 맞추어 짝수가 아닌 수들을 제거한다. D(X) = { 0, 2, 4 }가 된다. 그런 다음 X와 Y 사이의 호(arc)를 제약 C2에 따라 조사한다. 순서쌍 (X=0, Y=4), (X=2, Y=2), (X=4, Y=0)만이 C2에 만족한다. AC-3 알고리즘은 D(X) = {0, 2, 4}, D(Y) = {0, 2, 4}임을 결정하고 이제 종료한다.

AC-3의 슈도-코드는 다음과 같다: 

 Input:
   A set of variables X
   A set of domains D(x) for each variable x in X. D(x) contains vx0, vx1... vxn, the possible values of x
   A set of unary constraints R1(x) on variable x that must be satisfied
   A set of binary constraints R2(x, y) on variables x and y that must be satisfied

 Output:
   Arc consistent domains for each variable.

 function ac3 (X, D, R1, R2)
 // Initial domains are made consistent with unary constraints.
     for each x in X
         D(x) := { x in D(x) | R1(x) }
     // 'worklist' contains all arcs we wish to prove consistent or not.
     worklist := { (x, y) | there exists a relation R2(x, y) or a relation R2(y, x) }

     do
         select any arc (x, y) from worklist
         worklist := worklist - (x, y)
         if arc-reduce (x, y)
             if D(x) is empty
                 return failure
             else
                 worklist := worklist + { (z, x) | z != y }
     while worklist not empty

 function arc-reduce (x, y)
     bool change = false
     for each vx in D(x)
         find a value vy in D(y) such that vx and vy satisfy the constraint R2(x, y)
         if there is no such vy {
             D(x) := D(x) - vx
             change := true
         }
     return change

이 알고리즘은 워스트-케이스 타임 컴플렉시티(worst-case time complexity)가 O(ed³)이다. 여기서 e는 변(edge)의 개수이고, d는 가장 사이즈가 큰 정의역(domain)의 사이즈이다.

참고 문헌[편집]

원본 주소 "https://ko.wikipedia.org/w/index.php?title=AC-3_알고리즘&oldid=36151759"