- •Глава 10. Дискретные задачи удовлетворения ограничений (уо) и алгоритмы их решения.
- •10.1. Основные понятия теории удовлетворения ограничений.
- •10.1.1. Определение задачи удовлетворения ограничений
- •10.1.2. Примеры задач удовлетворения ограничений
- •10.1.3. Бинарные и общие задачи удовлетворения ограничений
- •10.1.4. Графовые представления структуры задачи удовлетворения ограничений
- •10.2. Основные методы решения задач удовлетворения ограничений
- •10.2.1. О методах решения задач удовлетворения ограничений
- •10.2.2. Методы поиска с возвратами
- •10.2.3. Структура и методы декомпозиции задач удовлетворения ограничений
- •10.2.4. Программирование в ограничениях
- •10.2.5. Современные программные системы программирования в ограничениях.
10.2. Основные методы решения задач удовлетворения ограничений
10.2.1. О методах решения задач удовлетворения ограничений
Методы построения решения задачи УО могут быть разбиты на три класса:
1) Первый класс содержит варианты поиска с возвратами. Эти алгоритмы строят решение с помощью расширения частичного решения шаг за шагом, используя различные эвристики и применяя более или менее разумные (интеллектуальные) стратегии возврата из тупиковых вершин. Снижение размера задачи позволяет уменьшить размеры пространства поиска.
2) Алгоритмы распространения ограничений исключают некоторые элементы, не входящие в решения, из пространства поиска. В общем, эти алгоритмы не исключают все элементы, не входящие в решения и, следовательно, они не строят полностью решения. Они используются либо для препроцессинга задачи до использования алгоритма другого типа, или перемежаются с шагами алгоритма другого типа ‑ например, поиска с возвратами ‑ для повышения его производительности.
3) Наконец, структурные алгоритмы используют информацию о структуре первичного или двойственного графа ограничений задачи УО. Структурные алгоритмы могут также использоваться с алгоритмами других типов.
Все алгоритмы из указанных выше трех классов систематически исследуют пространство решений.
Эти алгоритмы:
корректны, то есть они заканчивают работу с присвоением значений всем переменным, которое является решением;
полны, т.е. они способны исследовать все пространство поиска и найти все решения.
10.2.2. Методы поиска с возвратами
Возможно сформулировать задачи УО в виде задач поиска, что позволяет решать задачи УО с помощью алгоритмов поиска. Поиск с возвратами, описанный в главах 4 и 6, может использоваться для задач удовлетворения ограничений8.
Нвпомним, что поиск в глубину, в котором каждый раз выбираются значения для одной переменной и выполняется возврат, если больше не остается допустимых значений, которые можно было бы присвоить переменной, называется поиском с возвратами (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.
Каждая ветвь соответствует частичному присвоению (которое становится полным, когда ветвь доходит до переменной ) и уровеньдерева представляет выборы значений, сделанные для-й переменной (согласно упорядочению). Глубиной называется расстояние от корня дерева. Черные и белые вершины представляют соответственно успешные и неудачные присвоения в данной точке поиска. Вершины снабжены описанием значений доменов, приписанных данной переменной в рассматриваемой точке поиска. Путь поиска показан пунктирной направленной линией.
Поиск с возвратами неэффективен в том смысле, что требует выполнения большего числа операций, чем это нужно для нахождения решения.
Для усовершенствования поиска с возвратами используются множества неперспективных наборов значений (МННЗ). В контексте задач выполнимости МННЗ соответствует клаузе (дизъюнкту), причем использование обучения и использования большого числа клауз во время поиска оказалось весьма эффективным для решения задач выполнимости.
Распространение ограничений
Имеются различные виды методов для преодоления присущей задачам УО трудной разрешимости, в том числе распространение ограничений, называемое также сужением, с помощью которого исключаются значения. Распространение ограничений позволяет удалить избыточные значения из доменов переменных, что снижает размер пространства решений.
Распространение ограничений является центральным моментом в процессе решения задачи УО.
Уменьшение задачи может быть выполнено либо однократно ‑ в качестве этапа препроцессинга перед использованием какого-либо другого алгоритма, либо ‑ многократно, шаг за шагом, перемежаясь с исследованием пространства решений с помощью алгоритма поиска. В последнем случае отсекаются подмножества пространства решений, экономя время, которое алгоритм поиска затратил бы на систематическое исследование отброшенных элементов. Если в результате уменьшения пространства решений какой-либо домен стал пустым, тогда отсюда следует, что рассматриваемая задача УО не имеет решений.
Распространение ограничений ‑ очень общее понятие, которое появляется под разными названиями в зависимости от времени и авторов9. Ниже будут рассмотрены наиболее хорошо известные и используемые алгоритмы.
Препроцессинг или предварительная обработка в задачах УО создает эквивалентную, с тем же множеством решений, но более простую задачу, в результате чего поиск на дереве может решить полученную задачу с гораздо меньшими затратами. Исходная задача УО преобразуется следующим образом. Вначале домены переменных могут фильтроваться для удаления элементов, которые не могут быть частью ни одного решения. Далее может быть изменено множество ограничений с целью недопущения несовместимых комбинаций присвоений, причем эти изменения производятся с помощью распространения ограничений: используется локальная группа ограничений для получения информации, которая запоминается в виде измененного ограничения или уменьшенного домена переменной. Это локальное изменение является основой для получения дальнейшей информации, поэтому результат любого изменения постепенно распространяется по всей задаче.
Хотя с целью простоты изложения представленные здесь методы описаны для бинарных задач УО, они применимы к -арной задаче УО (например, используя двойственную графовую интерпретацию).
Вершинная и дуговая совместимость
Вершинная совместимость состоит в рассмотрении каждой вершины графа ограничений и соответствующих ей унарных ограничений и выполнении сужения домена: если ‑ унарное ограничение для вершины, тогда величины, не удовлетворяющие, исключаются из домена. Прямой алгоритм вершинной совместимости (node-consistency algorithm (NC)), удаляющий излишние элементы доменов переменных с помощью проверки доменов одного за другим, имеет временную сложность , где‑ максимальный размер доменов, а‑ число переменных.
Дуговая совместимость состоит в рассмотрении каждой дуги, соответствующей бинарному ограничению , и выполнении сужения доменов. Величины, не удовлетворяющие, исключаются из доменови. Можно определить-совместимость, рассматривая ограничения спеременными (для‑ путевая совместимость, а‑ гипер-дуговая совместимость).
Проверку совместимости дуг можно использовать либо в качестве этапа предварительной обработки перед началом процесса поиска, либо в качестве этапа распространения ограничения (аналогично предварительной проверке) после каждого присваивания во время поиска.
Для данного ограничения говорят, что значение для переменной в ограничении имеет поддержку (support), если существуют такие значения для других переменных в этом ограничении, что это ограничение удовлетворяется.
Ограничение дуго-совместимо, если каждое значение из доменов переменных имеет поддержку.
Для достижения дуговой совместимости на , для каждого элемента, ищется элемент, такой, что выполняется условие дуговой совместимости;поддерживает. Все элементы домена без поддержки удаляются.
Удаление значений без поддержки часто называется усечением или сужением доменов.
Для ограничений, содержащих более двух переменных, дуговая совместимость часто называется гипер-дуговой совместимостью или обобщенной дуговой совместимостью.
Например, рассмотрим ограничение с доменами переменныхи‑. Вынуждение дуговой совместимости для этого ограничения сужает домены обеих переменных до. Величины, удаленные из доменов обеих переменных, локально несовместимы ‑ они не принадлежат ни одному набору присвоений переменных, удовлетворяющих ограничению, и поэтому не могут быть частью какого-либо решения всей задачи УО.
Для вынуждения дуговой совместимости в задаче УО требуется повторно удалять величины из доменов, пока не достигнем устойчивой точки. Оптимальный алгоритм для произвольного ограничения характеризуется временной сложностью в худшем случае, равной , где‑ арность ограничения, а‑ размер доменов переменных.
Простейшим методом достижения глобальной дуговой совместимости является повторение проходов по проверке каждой дуги задачи до тех пор, пока не будет никаких изменений графа ограничений после очередного прохода. Этот подход реализован в виде алгоритма AC-110.
Вслед за исторически первым алгоритмом 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-совместимость.