Алгоритм AC-3 - AC-3 algorithm

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

Алгоритм

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

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

Для иллюстрации вот пример очень простой проблемы с ограничениями:Икс (переменная) имеет возможные значения {0, 1, 2, 3, 4, 5} - набор этих значений является областью Икс, или D (Икс). Переменная Y имеет область определения D (Y) = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Вместе с ограничениями C1 = "Икс должно быть даже "и C2 = "Икс + Y должен быть равен 4 ", у нас есть CSP, который может решить AC-3. Обратите внимание, что фактический граф ограничений, представляющий эту проблему, должен содержать два ребра между Икс и Y поскольку C2 является неориентированным, но представление графа, используемое AC-3, является направленным.

Для этого сначала удаляются нечетные значения из домена Икс как того требует C1, оставляя D (Икс) = {0, 2, 4}. Затем он исследует дуги между Икс и Y подразумевается C2. Только пары (Икс=0, Y=4), (Икс=2, Y= 2) и (Икс=4, Y= 0) соответствует ограничению C2. Затем AC-3 завершается с D (Икс) = {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, которые должны быть удовлетворены. Результат: согласованные области для каждой переменной. функция ac3 (X, D, R1, R2)     // Начальные домены согласованы с унарными ограничениями.     для каждого Икс в X D (x): = {vx в D (x) | vx удовлетворяет R1 (x)} // 'рабочий список' содержит все дуги, согласованность которых мы хотим или нет.     рабочий список: = {(x, y) | существует отношение R2 (x, y) или отношение R2 (y, x)} делать         выберите любую дугу (x, y) из рабочего списка рабочий список: = рабочий список - (x, y) если уменьшение дуги (x, y) если D (x) пусто возвращаться отказ еще                 рабочий список: = рабочий список + {(z, x) | z! = y и существует отношение R2 (x, z) или отношение R2 (z, x)} пока рабочий список нет пустой функция уменьшение дуги (x, y) bool изменить = ложный     для каждого vx в D (x) находит такое значение vy в D (y), что vx и vy удовлетворяют ограничению R2 (x, y) если такого vy {D (x): = D (x) - vx change: = истинный         }     возвращаться изменять

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

Рекомендации

- -