AC-3 알고리즘
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
AC-3 알고리즘은 제약 조건, 변수, 변수의 정의역을 기반으로 작동하는 알고리즘이다. 변수는 여러 이산 값을 가질 수 있으며, 제약 조건은 변수가 가질 수 있는 값을 제한하는 관계를 의미한다. AC-3는 제약 만족 문제를 유향 그래프로 표현하여, 변수 쌍 사이의 아크를 검사하고, 제약 조건과 일치하지 않는 변수의 값을 제거하는 방식으로 진행된다. 알고리즘은 아크의 모음을 유지하며, 변수의 도메인에서 값이 제거되면 해당 변수를 가리키는 모든 제약 조건의 아크가 모음에 추가된다. AC-3 알고리즘은 최악의 경우 O(ed³)의 시간 복잡도와 O(e)의 공간 복잡도를 가진다.
더 읽어볼만한 페이지
| AC-3 알고리즘 | |
|---|---|
| '제약 조건 만족 문제' | |
| '분야' | '컴퓨터 과학, 수학, 운영 연구' |
| '해결 방법' | '백트래킹' '제약 조건 전파' |
| '관련 문제' | 'SAT 문제' '정수 계획법' |
| '아크 일관성 알고리즘 #3' | |
| '유형' | '제약 조건 만족 문제 해결 알고리즘' |
| '클래스' | '제약 조건 전파' |
| '제약 조건' | '이진 제약 조건' |
2. 알고리즘
AC-3 알고리즘은 제약 조건, 변수, 그리고 변수의 정의역(domain)을 기반으로 작동한다. 변수는 여러 이산(discrete) 값을 가질 수 있으며, 어떤 변수가 가질 수 있는 값들의 집합을 정의역이라 한다. 제약 조건은 변수가 가질 수 있는 값을 제한하는 관계이다. 제약 조건은 다른 변수의 값에 관계될 수 있다.[1]
2. 1. 제약 조건 만족 문제와 그래프 표현
제약 조건 만족 문제는 유향 그래프로 표현될 수 있다. 여기서 꼭짓점은 변수를 나타내고, 꼭짓점 사이의 변(edge)은 제약 조건을 나타낸다. AC-3 알고리즘은 변수들 (''x'', ''y'')의 순서쌍 변을 하나하나 보며 진행된다. ''x''와 ''y'' 사이의 제약 조건과 불일치(inconsistent)하는 ''x''와 ''y''의 값들이 있으면 ''x''와 ''y''의 정의역에서 각각 제거해 나간다.[1]예를 들어, 변수 '''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)을 사용한다.[1]
먼저, '''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}를 결정하고 종료한다.[1]
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''3'')이고, 공간 복잡도는 '''O'''(''e'')이며, 여기서 ''e''는 아크의 수이고 ''d''는 가장 큰 도메인의 크기이다.
2. 4. 시간 복잡도
AC-3 알고리즘은 최악의 경우 '''O'''(''ed''³)의 시간 복잡도를 가진다. 여기서 '''e'''는 변(edge)의 개수이고, '''d'''는 가장 큰 정의역(domain)의 크기이다.[1]
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com