AC-3 알고리즘

AC-3 algorithm

제약 만족도에서 AC-3 알고리즘(Arc Consistency Algorithm #3)은 제약 만족 문제(CSP)의 해결에 사용되는 일련의 알고리즘 중 하나입니다.그것은 1977년 Alan Mackworth에 의해 개발되었다.이전의 AC 알고리즘은 종종 너무 비효율적이라고 간주되며, 이후의 많은 알고리즘은 구현이 어렵기 때문에 AC-3는 매우 단순한 제약 해결기에서 가장 자주 학습되고 사용됩니다.

알고리즘

AC-3은 제약조건, 변수 및 변수의 도메인(스코프)에서 동작합니다.변수는 여러 이산 값 중 하나를 사용할 수 있습니다. 특정 변수의 값 집합을 도메인이라고 합니다.제약 조건은 변수가 가질 수 있는 값을 제한하거나 제한하는 관계입니다.제약 조건은 다른 변수의 값을 포함할 수 있습니다.

알고리즘 중 CSP의 현재 상태는 문제의 변수인 방향 그래프로 볼 수 있습니다. 여기서 노드는 대칭 구속조건과 관련된 변수 사이의 가장자리 또는 호가 있는 경우, 작업 목록의 각 호는 일관성을 확인해야 하는 구속조건을 나타냅니다.AC-3은 변수 쌍(x, y) 사이의 호를 조사하는 것으로 진행됩니다.그러면 x와 y 사이의 제약 조건과 일치하지 않는 값이 x의 도메인에서 제거됩니다.알고리즘은 아직 체크되지 않은 호 컬렉션을 유지합니다.변수의 도메인에 값이 삭제되어 있는 경우 해당 프루닝 변수를 가리키는 제약 조건의 모든 호(현재 제약 조건의 호 제외)가 수집에 추가됩니다.변수의 도메인은 유한하고 각 단계에서 1개의 호 또는 적어도1개의 값이 삭제되므로 이 알고리즘은 반드시 종료됩니다.

예를 들어 매우 간단한 제약 문제의 예를 제시하겠습니다.X(변수)에는 가능한 값 {0, 1, 2, 3, 4, 5}이 있습니다.이러한 값의 집합은 X의 도메인 또는 D(X)입니다.변수 Y의 도메인은 D(Y) = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}입니다.제약 조건 C1 = "X는 짝수여야 한다" 및 C2 = "X + Y는 4여야 한다"와 함께 AC-3이 해결할 수 있는 CSP가 있습니다.C2는 무방향이지만 AC-3에서 사용되는 그래프 표현은 방향이기 때문에 이 문제를 나타내는 실제 제약 그래프에는 X와 Y 사이에 2개의 에지가 포함되어 있어야 합니다.

먼저 C1에서 요구하는 대로 X의 영역 밖으로 비짝수 값을 제거하여 D(X) = { 0, 2, 4 }을 남깁니다. 그런 다음 C2에서 암시하는 X와 Y 사이의 호를 조사합니다.제약 조건 C2에는 쌍(X=0, Y=4), (X=2, Y=2) 및 (X=4, Y=0)만 일치합니다.다음으로 AC-3은 D(X) = {0, 2, 4} 및 D(Y) = {0, 2, 4}로 종료됩니다.

AC-3 는, 다음과 같이 의사 코드로 표현됩니다.

입력: 변수 X X의 각 변수 x에 대한 도메인 D(x) 집합입니다. D(x)에는 vx0, vx1이 포함되어 있습니다...vxn, x의 가능한 값 A 변수 x의 단항 제약 조건 R1(x) 집합 충족 변수 x 및 y의 이진 제약 조건 R2(x, y) 집합 충족되어야 함 출력:각 변수에 대해 일관된 도메인을 호로 표시합니다.function ac3 (X, D, R1, R2) // 초기 도메인은 단항 구속조건과 일치합니다.X D(x)의 각 x에 대해 := D(x) vx의 { vx in D(x) vx in D1(x) } // 'complete'에는 일관성이 있는지 확인하려는 모든 호가 포함됩니다. 작업 목록 := { (x, y) 또는 R2(y, x)} 관계가 있습니다. 작업 목록 = - 작업 목록에서 원하는 호를 선택합니다.D(x)가 비어 있으면 반환 실패 작업 목록: = 작업 목록 + { (z, x) z != y이고 R2(x, z) 또는 R2(z, x) } 관계가 있는 반면 작업 목록이 비어 있지 않으면 D(x, y)의 각 vx에 대해 vy(x) 값을 찾습니다.이러한 vy { D(x) := D(x) - vx change := true } 반환 변경이 없는 경우 vx 및 vy가 제약 조건 R2(x, y)를 충족함

알고리즘의 시간 복잡도는 O(ed3)와 공간 복잡도는 O(e)입니다.e는 호의 수, d는 가장 큰 도메인의 크기입니다.

레퍼런스

  • A.K. 맥워스관계 네트워크의 일관성.인공지능, 8:99-118, 1977.
  • 스튜어트 러셀과 피터 노빅입니다 인공지능: 모던 어프로치, 202-233, 2003.