# AC-3 알고리즘

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

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

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

## [편집] 알고리즘

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

제약 만족 문제는 유향 그래프(directed graph)로서 표현될 수 있다. 꼭지점(node)가 변수가 된다. 꼭지점 사이의 변(edge, arc)들은 제약조건을 나타낸다. AC-3 알고리즘은 변수들 (x, y)의 순서쌍 변(edge)를 하나하나 보며 진행된다. 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-cast time complexity)가 O(ed³)이다. 여기서 e는 변(edge)의 개수이고, d는 가장 사이즈가 큰 정의역(domain)의 사이즈이다.

## [편집] 주석

- A.K. Mackworth. Consistency in networks of relations. Artificial Intelligence, 8:99-118, 1977.

원본 주소 ‘http://ko.wikipedia.org../../../a/c/-/AC-3_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98_c73f.html’

분류: 알고리즘 | 제약 만족

##### Views

- 문서
- 토론
- 현재 버전

##### 찾기