10.2. Основные методы решения задач удовлетворения ограничений

10.2.1. О методах решения задач удовлетворения ограничений

Методы построения решения задачи УО могут быть разбиты на три класса:

1) Первый класс содержит варианты поиска с возвратами. Эти алго­ритмы строят решение с помощью расширения частичного решения шаг за шагом, используя различные эвристики и применяя более или менее разум­ные (интеллектуальные) стратегии возврата из тупиковых вершин. Снижение размера задачи позволяет уменьшить размеры пространства поиска.

2) Алгоритмы распространения ограничений исключают некоторые элементы, не входящие в решения, из пространства поиска. В общем, эти ал­горитмы не исключают все элементы, не входящие в решения и, следова­тельно, они не строят полностью решения. Они используются либо для пре­процессинга задачи до использования алгоритма другого типа, или переме­жаются с шагами алгоритма другого типа ‑ например, поиска с возвратами ‑ для повышения его производительности.

3) Наконец, структурные алго­ритмы используют информацию о структуре первичного или двойственного графа ограничений задачи УО. Структурные алгоритмы могут также исполь­зоваться с алгоритмами других типов.

Все алгоритмы из указанных выше трех классов систематически ис­следуют пространство решений.

Эти алгоритмы:

• корректны, то есть они заканчивают работу с присвоением значе­ний всем переменным, которое является решением;

• полны, т.е. они способны исследовать все пространство поиска и найти все решения.

10.2.2. Методы поиска с возвратами

Возможно сформулировать задачи УО в виде задач поиска, что позво­ляет решать задачи УО с помощью алгоритмов поиска. Поиск с возвратами, описанный в главах 4 и 6, может использоваться для задач удовлетворения ограничений⁸.

Нвпомним, что поиск в глубину, в котором каждый раз выбираются значения для од­ной переменной и выполняется возврат, если больше не остается допустимых значений, которые можно было бы присвоить переменной, называется поис­ком с возвратами (backtracking).

Дерево присвоений значений переменным ‑ это дерево, в котором каж­дая вершина соответствует множеству присвоений, причем корень дерева отвечает пустому множеству присвоений. В каждой вершине выбирается перемен­ная, которой вне было присвоено значение. Алгоритмы поиска с возвра­тами выполняют поиск в глубину в этих деревьях присвоений значений.

Алгоритмы поиска с возвратами ‑ это алгоритмы систематического по­иска для задач УО, которые используют частичные присвоения, и строят частичное решение путем поочередного присваи­вания значений переменным. Если алгоритм обнаруживает тупик, в котором частичное решение не имеет совместимого расширения, то выбор последнего присвоения отменяется и делается попытка присвоения другого значения. Этот процесс повторяется до тех пор, пока не будут исчерпаны все возможно­сти и/или не будет найдено решение.

Алгоритмы поиска с возвратами являются полными в том смысле, что они находят решение, если оно существует.

Алгоритм поиска с возвратами характеризуется экспоненциальной вре­менной сложностью, но является линейным по используемой памяти.

Простейшим методом решения задач УО является метод ''Generate and Test'', который порождает каждое возможное решение (путем присвоения всех возможных значений для каждой переменной) и проверяется, удовлетво­ряет ли оно всем ограничениям. В наихудшем случае число всех возможных проверенных решений равно размеру декартова произведения доменов всех переменных (см. 6.1.1), в связи с чем метод полного перебора может требовать больших затрат времени при решении задач.

Хронологический поиск с возвратами (chronological backtracking) усо­вершенствует схему ''Generate and Test'', рассматривая процесса поиска как постепен­ное расширение частичных решений. Порядок задания значений ‑ это поря­док, в котором присваиваются значения переменным во время поиска. На уровне порядка присваивания прошлые (т.е. ранее рассмотренные) переменные имеют индексы, мень­шие чем, причем им уже присвоены значения. Будущие переменные имеют ин­дексы, большие, чем, и им еще не присвоены значения.

На рис. 10.5 на псевдокоде описан алгоритм поиска с возвратами для случая бинарных ограничений. Для простоты, псевдокод не различает случаев, когда не найдено решений или когда не найдено больше решений, возвращается значение ложь в обоих слу­чаях.

В

описании алгоритма используются следующие обозначения:‑ число переменных задачи; Assignments [i] ‑ массив размерности запоминает значение, присвоенное в настоящий момент каждой переменной;содержит последовательность элементов домена, соответствую­щего переменной.

Рис. 10.5. Поиск с возвратами.

Функция возвращает значениеистина, если бинарное ограничение удовлетво­ряется текущими присвоениями значений переменными. Еслине существует, Test( ) возвращаетистина (это не считается про­веркой ограничения). Каждый элемент домена поочередно присваива­ется переменной, расширяя тем самым текущее присвоение переменным. Если про­верка ограничения для предыдущей переменной не проходит, это частичное присвоение больше не расширяется. Если доменисчерпан (тупик или пол­ное исчерпание домена), алгоритм делает возврат до уровняс целью нахождения другого совместимого присвоения для. Если такого нет, он делает возврат к, и т.д. пока не будет найдена переменная с другим совмес­тимым присвоением или будет показано, что ЗУО не имеет решения.

Для данного совместимого присвоения (все проверки ограничений были успешны), делается рекурсивный вызов BTили, если не остается свободных переменных, получено решение.

Поиск с возвратами может рассматриваться как обход вершин дерева.

Рис. 10.6. Поиск с возвратами как обход дерева.

На рис. 10.6 показано, как поиск с возвратами решает задачу на рис. 10.4.

Каждая ветвь соответствует частичному присвоению (которое стано­вится полным, когда ветвь доходит до переменной ) и уровеньдерева пред­ставляет выборы значений, сделанные для-й переменной (согласно упорядоче­нию). Глубиной называется расстояние от корня дерева. Черные и белые вершины представляют соответственно успешные и неудачные присвоения в данной точке поиска. Вершины снабжены описанием значений доменов, при­писанных данной переменной в рассматриваемой точке поиска. Путь поиска показан пунктирной направленной линией.

Поиск с возвратами неэффективен в том смысле, что требует выполне­ния большего числа операций, чем это нужно для нахождения решения.

Для усовершенствования поиска с возвратами используются множества неперспективных наборов значений (МННЗ). В контексте задач выполнимости МННЗ соответствует клаузе (дизъюнкту), причем ис­пользование обучения и использования большого числа клауз во время по­иска оказалось весьма эффективным для решения задач выполнимости.

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

Имеются различные виды методов для преодоления присущей задачам УО трудной разрешимости, в том числе распространение ограничений, называемое также сужением, с помощью которого исключаются значения. Распространение ограничений позволяет удалить избыточные значения из доменов переменных, что снижает размер пространства решений.

Распространение ограничений является центральным моментом в про­цессе решения задачи УО.

Уменьшение задачи может быть выполнено либо однократно ‑ в качестве этапа препроцессинга перед использованием какого-либо другого алгоритма, либо ‑ многократно, шаг за шагом, перемежаясь с исследованием пространства решений с помощью ал­горитма поиска. В последнем случае отсекаются подмножества пространства решений, экономя время, которое алгоритм поиска затратил бы на системати­ческое исследование отброшенных элементов. Если в результате уменьшения пространства решений какой-либо домен стал пустым, тогда отсюда следует, что рассматриваемая задача УО не имеет решений.

Распро­странение ограничений ‑ очень общее понятие, которое появляется под раз­ными названиями в зависимости от времени и авторов⁹. Ниже будут рассмотрены наиболее хорошо известные и используемые алгоритмы.

Препроцессинг или предварительная обработка в задачах УО создает эквивалентную, с тем же множеством решений, но более простую задачу, в результате чего по­иск на дереве может решить полученную задачу с гораздо меньшими затра­тами. Исходная задача УО преобразуется следующим образом. Вначале до­мены переменных могут фильтроваться для удаления элементов, которые не могут быть частью ни одного решения. Далее может быть изменено множество ограничений с целью недопущения несовместимых комбинаций присвое­ний, причем эти изменения производятся с помощью распространения ограничений: ис­пользуется локальная группа ограничений для получения информации, которая запоминается в виде измененного ограничения или уменьшенного домена переменной. Это локальное изменение является основой для получения дальнейшей информации, поэтому результат любого изменения постепенно распространяется по всей задаче.

Хотя с целью простоты изложения представленные здесь методы опи­саны для бинарных задач УО, они применимы к -арной задаче УО (напри­мер, используя двойственную графовую интерпретацию).

Вершинная и дуговая совместимость

Вершинная совместимость состоит в рассмотрении каждой вершины графа ограничений и соответствующих ей унарных ограничений и выполне­нии сужения домена: если ‑ унарное ограничение для вершины, то­гда величины, не удовлетворяющие, исключаются из домена. Пря­мой алгоритм вершинной совместимости (node-consistency algorithm (NC)), удаляющий излишние элементы доменов переменных с помощью про­верки доменов одного за другим, имеет временную сложность , где‑ максимальный размер доменов, а‑ число переменных.

Дуговая совместимость состоит в рассмотрении каждой дуги, соответ­ствующей бинарному ограничению , и выполнении сужения доменов. Величины, не удовлетворяющие, исключаются из доменови. Можно определить-совместимость, рассматривая ограничения сперемен­ными (для‑ путевая совместимость, а‑ гипер-дуговая со­вместимость).

Проверку совместимости дуг можно использовать либо в качестве этапа предварительной обработки перед началом процесса поиска, либо в качестве этапа распространения ограничения (аналогично предварительной проверке) после каждого присваивания во время поиска.

Для данного ограничения говорят, что значение для переменной в огра­ничении имеет поддержку (support), если существуют такие значения для других переменных в этом ограничении, что это ограничение удовлетворя­ется.

Ограничение дуго-совместимо, если каждое значение из доменов пере­менных имеет поддержку.

Для достижения дуговой совместимости на , для каждого элемента, ищется элемент, такой, что выполняется условие дуговой со­вместимости;поддерживает. Все элементы домена без поддержки уда­ляются.

Удаление значений без поддержки часто называется усечением или суже­нием доменов.

Для ограничений, содержащих более двух переменных, дуговая совмес­тимость часто называется гипер-дуговой совместимостью или обобщенной дуговой совместимостью.

Например, рассмотрим ог­раничение с доменами переменныхи‑. Вынуждение дуговой совместимости для этого ограниче­ния сужает домены обеих переменных до. Величины, удаленные из доменов обеих переменных, локально несовместимы ‑ они не принадлежат ни одному набору присвоений переменных, удовлетворяющих ограничению, и поэтому не могут быть частью какого-либо решения всей за­дачи УО.

Для вынуждения дуговой совместимости в задаче УО требуется по­вторно удалять величины из доменов, пока не достигнем устойчивой точки. Оптимальный алгоритм для произвольного ограничения ха­рактеризуется временной сложностью в худшем случае, равной , где‑ арность ограничения, а‑ размер доменов переменных.

Простейшим методом достижения глобальной дуговой совместимости является повторение проходов по проверке каждой дуги задачи до тех пор, пока не будет никаких изменений графа ограничений после очередного про­хода. Этот подход реализован в виде алгоритма AC-1¹⁰.

Вслед за исторически первым алгоритмом AC-1 были разработаны ал­горитмы AC-2,…, AC-7, каждый из которых улучшает хранение информации об измененных доменах и управление итерациями. Временная сложность ал­горитма AC-3 составляет , емкостная сложность ‑, где‑ число бинарных ограничений. Алгоритм AC-4 улучшает AC-3 и имеет временную и емкостную сложность. Другим усовершенствованием алгоритма AC-3 является алгоритм AC-5, исполь­зующий семантику специальных видов ограничений. Алгоритм AC-7 исполь­зует симметрию бинарных ограничений.

Определение 10.9. Задача УО является направленно-дуго-совместимой по отношению к упорядочению , тогда и только тогда, когда каждая переменнаяреберно-совместима по отношению к каждой перемен­ной, такой что.

Процедура распространения ограничений directional-arc-consistency работает с задачей УО (как обычно, задача УО ‑ это тройка(‑ множество переменных,‑ множество доменов и‑ множество ограниче­ний) и упорядочениемдля задачи УО. Процедура исследует переменные в обратном порядке. Для каждой переменнойона проверяет родителейили, иными словами, те переменные, соединенные с, которые предшествуютв упорядочении; для задачи с шириной 1 число родителей будет всегда 0 или 1. Затем вызывается процедураUpdate-Domain для удале­ния из домена родителя всех значений, не совместных по крайней мере с од­ним значением из домена .

Это ‑ законное преобразование, так как удаленное значение не является частью решения.

После выполнения этой предварительной обработки выясняется на­правленная дуговая совместимость. Это означает, что для любого значения домена переменной и для лю­бого сына этой переменной найдется по крайней мере одно значение из до­мена сына, совместимое со значением родителя.

Глобально совместимые ЗУО обладают свойством, что любое совмес­тимое присвоение значений подмножеству переменных может быть расши­рено до совместимого присвоения значений всем переменным без получения тупиков.

Путевая совместимость

Для бинарных задач УО имеется еще один вид совместимости ‑ путевая совместимость.

Определение 10.10. Бинарная задача УО является путе-совместимой (path-consistent), если для любого пути в ее графе ограничений справедливо сле­дующее: если присвоения значений начальной и конечной переменной пути совместимы, то это может быть расширено на совместимое частичное при­своение значений оставшимся переменных на пути.

Аналогично семейству алгоритмов дуговой совместимости, имеется се­мейство алгоритмов достижения путевой совместимости бинарной задачи УО. Эти алгоритмы также гарантируют вершинную и дуговую совмести­мость. Наилучший из этих алгоритмов ‑ PC-4, аналогичный AC-4, характери­зуется временной и емкостной сложностью вида .

Локальная путевая совместимость выполняется, если для данного пути длины через вершины, для всех значенийитаких, что ограниченияивыполняются, имеется последовательность значений:, такая, что ограничениявыполняются. На рис. 10.7 показан пример для пути.

Рис. 10.7. Эффект вынуждения путевой совместимости.

Начальное состояние показано на рис. 10.7 a. Добавлено новое ограни­чение (рис. 10.7 b), которое не разрешает пару присвоений , т.к. для этих присвоений не существует присвоения для, удовлетворяющего. Вынуждение дуговой совместимости не разрешает этой пары присвоений.

Глобальная путевая совместимость выполняется, если любая пара при­своений значений, которые совместимы с прямым ограничением между двумя переменными, также совместима со всеми путями между двумя вер­шинами. Если любой путь длины 2 в полном графе ограничений является путе-совместимым, то путевая совместимость выполняется глобально.

Путевая совместимость вынуждается с помощью изменения прямого ограничения между начальной и конечной точкой пути для того, чтобы за­претить все пары назначений, которые нарушают требуемое условие. Истин­ные ограничения могут быть обновлены, добавляя новое явное ограничение к задаче (см. рис. 10.7).

-совместимость

Дуговая совместимость может также пониматься как информация о том, насколько далеко частичное решение может всегда быть расширено. А именно, любое частичное решение, содержащее лишь одну зафиксированную переменную, может быть расширено с помощью фиксации любой другой пе­ременной на соответствующим образом выбранном значении.

Применение того же принципа для большего числа переменных приво­дит к понятию -совместимости.

Определение 10.11 (-совместимость). Задача УО-совместима, если лю­бой совместимый кортеж значений любых переменных может быть рас­ширен путем задания значения любой одной из оставшихся переменных.

Задача УО строго -совместима тогда и только тогда, когда она -со­вместима для всех.

Строго -совместимая сеть, где‑ число переменных ЗУО, называетсяглобально совместимой.

Дуговая и путевая совместимость соответствуют 2- и 3-совместимости.

Заметим, что -совместимая ЗУО не обязательно разрешима, и наобо­рот, разрешимость задачи не влечет за собой совместимости любого уровня, а не только 1-совместимость.