Алгоритм AC-3

В удовлетворении ограничений алгоритм AC-3 (сокращение от Arc Consistency Algorithm #3) является одним из серии алгоритмов , используемых для решения проблем удовлетворения ограничений (или CSP). Он был разработан Аланом Маквортом в 1977 году. Более ранние алгоритмы AC часто считаются слишком неэффективными, а многие из более поздних алгоритмов трудно реализовать, поэтому AC-3 чаще всего изучается и используется в очень простых решателях ограничений.

Алгоритм

AC-3 работает с ограничениями , переменными и областями переменных (областями действия). Переменная ; может принимать любое из нескольких дискретных значений набор значений для конкретной переменной известен как ее область определения . Ограничение отношение — это , которое ограничивает или ограничивает значения, которые может иметь переменная. Ограничение может включать значения других переменных.

Текущее состояние CSP во время работы алгоритма можно рассматривать как ориентированный граф , где узлами являются переменные задачи, с ребрами или дугами между переменными, связанными симметричными ограничениями, где каждая дуга в рабочем списке представляет собой ограничение, которое необходимо проверить целостность . AC-3 продолжает исследование дуг между парами переменных ( x , y ). Он удаляет из области определения x те значения , которые не соответствуют ограничениям между x и y . Алгоритм хранит коллекцию дуг, которые еще предстоит проверить; когда из домена переменной удалены какие-либо значения, в коллекцию добавляются все дуги ограничений, указывающие на эту сокращенную переменную (кроме дуги текущего ограничения). Поскольку области определения переменных конечны и на каждом шаге удаляется либо одна дуга, либо хотя бы одно значение, этот алгоритм гарантированно завершится .

Для иллюстрации вот пример очень простой задачи с ограничениями: 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» мы имеем CSP, который может решить AC-3. Обратите внимание, что фактический граф ограничений, представляющий эту проблему, должен содержать два ребра между X и Y, поскольку C2 ненаправлен, но представление графа, используемое AC-3, является направленным.

AC-3 решает проблему, сначала удаляя нечетные значения из области определения X , как того требует C1 , оставляя D( X ) = { 0, 2, 4 }. Затем он исследует дуги между X и Y , подразумеваемые 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) := { vx in D(x) | vx satisfies 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 and there exists a relation R2(x, z) or a relation R2(z, x) }
     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

наихудшую временную сложность O ed ( Алгоритм имеет ³ ) и пространственная сложность O ( e ) , где e — количество дуг, а d — размер наибольшей области.

Ссылки

• АК Макворт. Согласованность в сетях отношений . Искусственный интеллект , 8:99-118, 1977.
• Стюарт Дж. Рассел и Питер Норвиг . Искусственный интеллект: современный подход , 202–233, 2003.