AC-3 알고리즘

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

AC-3 알고리즘은 제약 조건, 변수, 변수의 정의역을 기반으로 작동하는 알고리즘이다. 변수는 여러 이산 값을 가질 수 있으며, 제약 조건은 변수가 가질 수 있는 값을 제한하는 관계를 의미한다. AC-3는 제약 만족 문제를 유향 그래프로 표현하여, 변수 쌍 사이의 아크를 검사하고, 제약 조건과 일치하지 않는 변수의 값을 제거하는 방식으로 진행된다. 알고리즘은 아크의 모음을 유지하며, 변수의 도메인에서 값이 제거되면 해당 변수를 가리키는 모든 제약 조건의 아크가 모음에 추가된다. AC-3 알고리즘은 최악의 경우 O(ed³)의 시간 복잡도와 O(e)의 공간 복잡도를 가진다.

AC-3 알고리즘

'제약 조건 만족 문제'

'분야'	'컴퓨터 과학, 수학, 운영 연구'
'해결 방법'	'백트래킹' '제약 조건 전파'
'관련 문제'	'SAT 문제' '정수 계획법'

'아크 일관성 알고리즘 #3'

'유형'	'제약 조건 만족 문제 해결 알고리즘'
'클래스'	'제약 조건 전파'
'제약 조건'	'이진 제약 조건'

📚 더 읽어볼만한 페이지

제약 프로그래밍 - 제약된 최적화
제약된 최적화는 제약 조건을 만족하는 해 중에서 목적 함수를 최적화하는 해를 찾는 문제로, 자원 할당, 스케줄링 등에 활용되며, 다양한 제약 조건과 해법을 통해 해결될 수 있습니다.
제약 프로그래밍 - 제약 충족 문제
제약 충족 문제는 주어진 제약 조건을 만족하는 변수 값을 찾는 문제로, 백트래킹, 제약 전파 등의 방법으로 해결하며, 특정 조건에서는 다항 시간 내에 해결 가능하다.

1. 개요
2. 알고리즘

2. 알고리즘

AC-3 알고리즘은 제약 조건, 변수, 그리고 변수의 정의역(domain)을 기반으로 작동한다. 변수는 여러 이산(discrete) 값을 가질 수 있으며, 어떤 변수가 가질 수 있는 값들의 집합을 정의역이라 한다. 제약 조건은 변수가 가질 수 있는 값을 제한하는 관계이다. 제약 조건은 다른 변수의 값에 관계될 수 있다.

2.1. 제약 조건 만족 문제와 그래프 표현

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

예를 들어, 변수 X의 정의역 D(X) = {0, 1, 2, 3, 4, 5}이고, 변수 Y의 정의역 D(Y) = {0, 1, 2, 3, 4, 5}라고 가정하자. 여기에 제약 조건 C1 = "X는 짝수여야 한다"와 C2 = "X + Y는 4이어야 한다"가 추가되면 AC-3 알고리즘으로 해결 가능한 제약 조건 문제가 된다. 이때 문제의 그래프 그림에서는 제약 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}를 결정하고 종료한다.

2.2. 예시

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는 먼저 C1에 따라 X의 정의역에서 짝수가 아닌 값들을 제거하여 D(X) = { 0, 2, 4 } 를 만든다. 그 후, C2에 따라 X와 Y 사이의 관계를 조사한다. (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}를 결정하고 종료한다.

2.3. 슈도 코드

AC-3 알고리즘의 슈도 코드는 다음과 같다.

입력:
* 변수 집합 X
* X의 각 변수 x에 대한 도메인 D(x) 집합. D(x)는 x의 가능한 값인 vx0, vx1... vxn을 포함한다.
* 충족되어야 하는 변수 x에 대한 단항 제약 조건 R1(x) 집합
* 충족되어야 하는 변수 x와 y에 대한 이항 제약 조건 R2(x, y) 집합

출력:
* 각 변수에 대한 아크 일관성 도메인.

함수 ac3(X, D, R1, R2)
// 초기 도메인은 단항 제약 조건과 일치하도록 한다.
각 x 에 대해 X 에서
D(x) := { vx in D(x) | vx는 R1(x)를 만족 }
// 'worklist'에는 일관성을 증명하거나 그렇지 않기를 원하는 모든 아크가 포함되어 있다.
worklist := { (x, y) | 관계 R2(x, y) 또는 관계 R2(y, x)가 존재 }

do
worklist에서 임의의 아크 (x, y) 선택
worklist := worklist - (x, y)
if arc-reduce (x, y)
if D(x)가 비어 있음
return 실패
else
worklist := worklist + { (z, x) | z != y 및 관계 R2(x, z) 또는 관계 R2(z, x)가 존재 }
while worklist not 비어 있음

함수 arc-reduce(x, y)
bool change = false
각 vx 에 대해 D(x) 에서
vx와 vy가 제약 조건 R2(x, y)를 만족하는 D(y)의 값 vy 찾기
if 그런 vy가 없으면 {
D(x) := D(x) - vx
change := true
}
return change

이 알고리즘은 최악의 경우 시간 복잡도가 O(ed³)이고, 공간 복잡도는 O(e)이며, 여기서 e는 아크의 수이고 d''는 가장 큰 도메인의 크기이다.

2.4. 시간 복잡도

AC-3 알고리즘은 최악의 경우 O(ed³)의 시간 복잡도를 가진다. 여기서 e는 변(edge)의 개수이고, d는 가장 큰 정의역(domain)의 크기이다.