В удовлетворении ограничений алгоритм AC-3 (сокращение от Arc Consistency Algorithm #3) является одним из серии алгоритмов, используемых для решения задач удовлетворения ограничений (или CSP). Он был разработан Аланом Маквортом в 1977 году. Более ранние алгоритмы AC часто считаются слишком неэффективными, а многие из более поздних сложны в реализации, поэтому AC-3 является наиболее часто преподаваемым и используемым в очень простых решателях ограничений. Алгоритм AC-3 не следует путать с алгоритмом A3C с похожим названием в машинном обучении. [1]
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 выражается в псевдокоде следующим образом:
Вход: набор переменных X Набор доменов D(x) для каждой переменной x в X. D(x) содержит vx0, vx1... vxn, возможные значения x Набор унарных ограничений R1(x) на переменную x, которые должны быть выполнены Набор бинарных ограничений R2(x, y) на переменные x и y, которые должны быть удовлетворены Выход: Согласованные домены для каждой переменной. function ac3(X, D, R1, R2) // Начальные домены сделаны согласованными с унарными ограничениями. для каждого x в X D(x) := { vx в D(x) | vx удовлетворяет R1(x) } // 'worklist' содержит все дуги, для которых мы хотим доказать согласованность или несогласованность. worklist := { (x, y) | существует отношение R2(x, y) или отношение R2(y, x) } делать выберите любую дугу (x, y) из рабочего списка рабочий список := рабочий список - (x, y) если arc-reduce (x, y) если D(x) пусто вернуть ошибку иначе worklist := worklist + { (z, x) | z != y и существует отношение R2(x, z) или отношение R2(z, x) } пока рабочий список не пуст функция arc-reduce(x, y) bool change = false для каждого vx в D(x) найти значение vy в D(y) такое, что vx и vy удовлетворяют ограничению R2(x, y) если нет такого вы { D(x) := D(x) - vx изменить := правда } вернуть сдачу
Алгоритм имеет наихудшую временную сложность O ( ed 3 ) и пространственную сложность O ( e ) , где e — количество дуг, а d — размер наибольшего домена.