Распространение ограничения

Хотя предварительная проверка обнаруживает много несовместимостей, она не позволяет обнаружить их все. Например, рассмотрим третью строку на рис. 5.4, которая показывает, что если переменная WA имеет значение red, a Q— green, то обеим переменным, NT и SA, должно быть присвоено значение blue. Но соответствующие им регионы являются смежными и поэтому не могут иметь одно и то же значение цвета. Предварительная проверка не позволяет обнаружить эту ситуацию как несовместимость, поскольку не предусматривает достаточно далекий просмотр наперед. Распространение ограничения (constraint propagation) — это общее название методов распространения на другие переменные последствий применения некоторого ограничения к одной переменной; в данном случае необходимо распространить ограничение с WA и Q на NT и SA (как было сделано с помощью предварительной проверки), а затем — на ограничение между NT и SA, чтобы обнаружить указанную несовместимость. К тому же желательно, чтобы такая операция выполнялась быстро: нет смысла ограничивать таким образом объем поиска, если будет расходоваться больше времени на распространение ограничений, чем на выполнение простого поиска.
Идея проверки совместимости дуг легла в основу быстрого метода распространения ограничений, который является значительно более мощным по сравнению с предварительной проверкой. В данном случае термин дуга обозначает ориентированное ребро в графе ограничений, такое как дуга от SA до NSW. Если рассматриваются текущие области определения SA и NSW, то дуга является совместимой, если для каждого значения х переменной SA существует некоторое значение у переменной NSW, которое совместимо с х. В третьей строке на рис. 5.4 текущими областями определения SA и NSW являются {blue} и {red, blue} соответственно. При SA=blue существует совместимое присваивание для NSW, а именно NSW=red, поэтому дуга от SA до NSW совместима. С другой стороны, обратная дуга от NSWJXO SA несовместима, поскольку применительно к присваиванию NSW=blue не существует совместимого присваивания для SA. Эту дугу можно сделать совместимой, удалив значение blue из области определения NSW.
На том же этапе в процессе поиска проверку совместимости дуг можно также применить к дуге от SA до NT. Третья строка таблицы, приведенной на рис. 5.4, показывает, что обе переменные имеют область определения {blue}. Результатом становится то, что значение blue должно быть удалено из области определения SA, после чего эта область определения остается пустой. Таким образом, применение проверки совместимости дуг привело к раннему обнаружению той несовместимости, которая не была обнаружена с помощью предварительной проверки, применяемой в чистом виде.
Проверку совместимости дуг можно использовать либо в качестве этапа предварительной обработки перед началом процесса поиска, либо в качестве этапа распространения ограничения (аналогично предварительной проверке) после каждого присваивания во время поиска. (Последний алгоритм иногда называют MAC, сокращенно обозначая метод поддержки совместимости дуг— Maintaining Arc Consistency.) И в том и в другом случае процесс проверки необходимо выполнять повторно, до тех пор, пока не перестанут обнаруживаться какие-либо несовместимости. Это связано с тем, что при удалении (в целях устранения некоторой несовместимости дуг) любого значения из области определения некоторой переменной может появиться новая несовместимость дуг в тех дугах, которые указывают на эту переменную. В полном алгоритме проверки совместимости дуг, АС-3, используется очередь для отслеживания дуг, которые должны быть проверены на несовместимость (листинг 5.2). Каждая дуга (XifXj) по очереди "снимается с повестки дня" и проверяется; если из области определения xL необходимо удалить какие-либо значения, то каждая дуга (Xk,xL), указывающая на хь должна быть повторно вставлена в очередь для проверки. Сложность проверки совместимости дуг можно проанализировать следующим образом: любая бинарная задача CSP имеет самое большее 0(п2) дуг; каждая дуга (XkfxL) может быть "внесена в повестку дня" только d раз, поскольку область определения xL имеет самое большее d значений, доступных для удаления; проверка совместимости любой дуги может быть выполнена за время 0(d2), поэтому в наихудшем случае затраты времени составляют 0(n2d3). Хотя такой метод является значительно более дорогостоящим по сравнению с предварительной проверкой, все эти дополнительные затраты обычно окупаются1.
Листинг 5.2. Алгоритм проверки совместимости дуг АС-3. После применения алгоритма АС-3 либо каждая дуга является совместимой, либо некоторая переменная имеет пустую область определения, указывая на то, что эту задачу CSP невозможно сделать совместимой по дугам (и поэтому данная задача CSP не может быть решена). Обозначение "АС-3" предложено разработчиком данного алгоритма [967], поскольку это — третья версия, представленная в его статье
function АС-3(csp) returns определение задачи CSP# возможно,
с сокращенными областями определения переменных
inputs: csp, бинарная задача CSP с переменными {Х1г Х2, Хп}
local variables: queue, очередь, состоящая из дуг, которая
первоначально включает все дуги из определения задачи csp
while очередь queue не пуста do
(Xi, Xj) <— Remove-First (gueue) if Remove-Inconsistent-ValuesXj) then for each Xk in Neighbors [Xi] do
добавить (Xk, Xi) к очереди queue
function Remove-Inconsistent-Values(Xi# Xj) returns значение true тогда и только тогда, когда произошло удаление некоторого значения removed <— false for each x in Domain [Xi] do
if ни одно из значений у в области определения Domain[Xj] не позволяет использовать {х,у) для удовлетворения ограничения, установленного между Xi и Xj then удалить х из области определения Domain[Xi]; removed <— true return removed
Поскольку задачи CSP включают задачу 3SAT в качестве частного случая, не следует рассчитывать на то, что удастся найти алгоритм с полиномиальной временной сложностью, позволяющий определить, является ли данная конкретная задача CSP совместимой по дугам. Таким образом, можно сделать вывод, что метод проверки совместимости дуг не позволяет обнаружить все возможные несовместимости. Например, как показано на рис. 5.1, частичное присваивание {WA=red,NSW=red} несовместимо, но алгоритм АС-3 не обнаруживает такую несовместимость. Более строгие формы распространения ограничения можно определить с помощью понятия k-совместимости. Задача CSP является к-совместимой, если для любого множества к-1 переменных и для любого совместимого присваивания значений этим переменным любой к-й переменной всегда можно присвоить некоторое совместимое значение. Например, 1-совместимость означает, что совместимой является каждая отдельная переменная сама по себе; это понятие называют также совместимостью узла. Далее, 2-совместимость — то же, что и совместимость дуги, а 3-совместимость означает, что любая пара смежных переменных всегда может быть дополнена третьей соседней переменной; это понятие именуется также совместимостью пути.
Любой граф называется строго k-совместимым, если он является к-совместимым, а также (к-1)-совместимым, (к-2)-совместимым, ... и т.д. вплоть до 1-совместимого. Теперь предположим, что имеется некоторая задача CSP с узлами л, которая сделана строго n-совместимой (т.е. строго k-совместимой для к=п). Тогда эту задачу можно решить без возвратов. Для этого вначале можно выбрать совместимое значение для х±. В таком случае существует гарантия, что удастся выбрать значение для х2, поскольку граф является 2-совместимым, для х3, поскольку он — 3-совместимый, и т.д. Для каждой переменной х± необходимо выполнить поиск только среди d значений в ее области определения, чтобы найти значение, совместимое с x1,...,xi.1. Это означает, что гарантируется нахождение решения за время O(nd). Безусловно, за такую возможность также приходится платить: любой алгоритм обеспечения n-совместимости в наихудшем случае должен требовать времени, экспоненциально зависящего от п.
Между методами обеспечения n-совместимости и совместимости дуг существует целый ряд промежуточных методов, выбор которых осуществляется с учетом того, что для выполнения более строгих проверок совместимости потребуется больше времени, но это позволяет получить больший эффект с точки зрения сокращения коэффициента ветвления и обнаружения несовместимых частичных присваиваний. Существует возможность рассчитать такое наименьшее значение к, что выполнение алгоритма проверки k-совместимости будет гарантировать решение данной задачи без возвратов (см. раздел 5.4), но применение данного расчета на практике не всегда оправдано. В действительности определение подходящего уровня проверки совместимости в основном относится к области эмпирических методов.







Материалы

Яндекс.Метрика