Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 59
Текст из файла (страница 59)
древовидной декомпозиции (ггее десотроз111оп) графа ограничений и создании множества связанных подзадач. Каждая подзадача решается независимо, а затем итоговые решения комбинируются. Как и большинство алгоритмов, действующих по принципу "разделяй и властвуй", этот алгоритм работает успешно, если подзадачи не слишком велики. На рис. 5.8 показана древовидная декомпозиция задачи раскрашивания карты на пять подзадач. Любая древовидная декомпозиция должна удовлетворять трем приведенным ниже требованиям.
° Каждая переменная из первоначальной задачи появляется по меньшей мере в одной из подзадач. ° Если две переменные первоначальной задачи связаны ограничением, то должны появиться вместе (наряду с этим ограничением) по меньшей мере в одной из подзадач. ° Если какая-то переменная появляется в двух подзадачах в дереве, то должна появляться в каждой подзадаче вдоль пути, соединяющего эти подзадачи. Первые два условия гарантируют, что в декомпозиции будут представлены все переменные и ограничения.
Третье условие на первый взгляд кажется довольно формальным, но просто отражает то ограничение, что любая конкретная переменная должна иметь одно и то же значение в каждой подзадаче, в которой появляется; соблюдение этого ограничения гарантируют связи, соединяющие подзадачи в дереве. Например, переменная ю появляется во всех четырех связанных подзадачах на рис. 5.8. На основании рис. 5 7 можно убедиться, что эта декомпозиция имеет смысл.
232 Часть П. Решение проблем Каждая подзадача решается независимо; если какая-либо из них не имеет решения, то известно, что вся задача также не имеет решения. Если удается решить все подзадачи, то может быть предпринята попытка составить глобальное решение следующим образом. Прежде всего, каждая подзадача рассматривается как "мегапеременная", областью определения которой является множество всех решений этой подзадачи. Например, самая левая подзадача на рис. 5.8 представляет задачу раскрашивания карты с тремя переменными и поэтому имеет шесть решений; одним из них является ((ел=тес), ял=.ь2ие,д)т=ясееп). Затем решается задача с ограничениями, связывающими подзадачи; для этого используется эффективный алгоритм для деревьев, приведенный выше. Ограничения, связывающие подзадачи, указывают на то, что решения подзадач должны быть согласованными по их общим переменным.
Например, если за основу берется решение первой подзадачи (ад=кос(, яА=Ь2ие,ггт=дсееп), то единственным совместимым решением для следующей подзадачи становится (яА=Ь2ие, ггТ=дсееп, ц=сес(). Рис. 5.8. Древовидная декомпозиция графа ограниченой, показанного на рис. 5. 7, а Любой конкретный граф ограничений допускает большое количество древовидных декомпозиций; при выборе декомпозиции нужно стремиться к тому, чтобы подзадачи были как можно меньше.
Ъ. Ширина дерева древовидной декомпозиции графа на единицу меньше размера наибольшей подзадачи; ширина дерева самого графа определяется как минимальная ширина дерева среди всех его древовидных декомпозиций. Если граф имеет ширину дерева ьв и дана соответствующая древовидная декомпозиция, то соответствующая задача может быть решена за время О (пс)"" ) . Это означает, что пг задачи СБР с графами ограничений, характеризующимися конечной шириной дерева, могут быть решены за полиномиальное время.
К сожалению, задача поиска декомпозиции с минимальной шириной дерева является )ч(Р-трудной, но существуют эвристические методы, которые хорошо работают на практике. гЗЗ Глава 5. Задачи удовлетворения ограничений РЕЗЮМЕ ° Задачи удовлетворения ограничений (Сопзгга1пг БабзГасйоп РгоЫешз — СБР) состоят из переменных с налагаемыми на них ограничениями. В виде задач СЯР могут быть описаны многие важные задачи реального мира. Структуру любой задачи СБР можно представить в виде ее графа ограничений. ° Для решения задач СИР обычно применяется поиск с возвратами — одна из форм поиска в глубину.
° Независимыми от области определения методами выявления того, какая переменная должна быть выбрана следующей в ходе поиска с возвратами, являются эвристики, основанные на определении минимального количества оставшихся значений, и степенные эвристики. Для упорядочения значений переменной может применяться эвристика с наименее ограничительным значением. ° В алгоритме поиска с возвратами можно намного сократить коэффициент ветвления задачи, распространяя последствия частичных присваиваний, сформированных в ходе работы этого алгоритма.
Простейшим методом такого распространения является предварительная проверка. Более мощным методом является обеспечение совместимости дуг, но применение этого метода может оказаться более дорогостоящим. ° Возврат происходит после того, как для переменной нельзя больше найти допустимое присваивание. При использовании обратного перехода, управляемого конфликтами, возврат происходит непосредственно к источнику проблемы, возникшей в процессе поиска. ° Для решения задач с ограничениями весьма успешно используется локальный поиск на основе эвристики с минимальными конфликтами. ° Сложность решения задачи СЗР в значительной степени зависит от структуры ее графа ограничений. Задачи с древовидной структурой могут быть решены за линейное время. Метод определения условий формирования множества разрыва цикла позволяет преобразовать задачу СЗР общего вида в задачу с древовидной структурой и является очень эффективным, если существует возможность найти небольшое множество разрыва цикла.
Методы древовидной декомпозиции предусматривают преобразование задачи СБР в дерево подзадач и являются эффективными, если ширина дерева графа ограничений мала. БИБЛИОГРАФИЧЕСКИЕ И ИСТОРИЧЕСКИЕ ЗАМЕТКИ В самых ранних работах, относящихся к проблематике удовлетворения ограничений, главным образом рассматривались числовые ограничения. Выраженные в виде уравнений ограничения с целочисленными областями определения были исследованы индийским математиком Брахмагуптой в т[! веке; их часто называют ;ъ диофантовыми уравнениями в честь греческого математика Диофанта (около 200— 284 гг.), который в своих исследованиях фактически рассматривал область определения положительных рациональных чисел.
Систематические методы решения линейных уравнений путем удаления переменных исследовались Гауссом [5271; истоки 234 Часть П. Решение проблем подходов к решению ограничений с линейными неравенствами можно найти в работах Фурье [487]. Задачи удовлетворения ограничений с конечными областями определения также имеют долгую историю. Например, одной из старых задач в математике является Ж раскрашиваиие графа (раскрашивание карты — частный случай данной задачи). Согласно данным, приведенным в [125], гипотезу о четырех цветах (в соответствии с которой любой плоский граф можно раскрасить с помощью четырех или меньшего количества цветов) впервые выдвинул Френсис Гутри, студент де Моргана, в 1852 году.
Эта задача не поддавалась решению (несмотря на то, что в некоторых публикациях утверждалось обратное) до тех пор, пока доказательство не было получено с помошью компьютера Аппелем и Хакеном [35]. Специальные классы задач удовлетворения ограничений рассматривались на протяжении всей истории развития компьютерных наук. Одним из самых первых примеров решения таких задач, оказавшим наибольшее влияние, была система Ягегспрад [1476], которая решала геометрические ограничения на чертежах и была предшественником современных программ рисования и инструментальных средств САПР. Выявлению того, что задачи СБР представляют собой общий класс задач, мы обязаны Уго Монтанари [1073].
Первые попытки приведения задач СБР высокого порядка к чисто бинарным задачам СБР с помощью вспомогательных переменных (см. упр. 5.11) были впервые предприняты в Х!Х веке логиком Чарльзом Сандерсом Пирсом. Соответствующие методы бьши введены в тематику СИР Дектером [367] и доработаны Бакусом и ван Биком [55]. Задачи СБР с предпочтениями между решениями широко рассматривались в исследованиях по оптимизации; обобщение инфраструктуры СБР, позволяюшее использовать предпочтения, приведено в [134]. Для решения задач оптимизации может также применяться алгоритм устранения интервалов [369]. Использование поиска с возвратами для удовлетворения ограничений было предложено Битнером и Рейнгольдом [135], но эти ученые проследили истоки идей своего основного алгоритма до работ Х]Х века.
Кроме того, Битнер и Рейнгольд впервые предложили использовать эвристику МКЧ, названную ими эврисгликой с наиболее ограниченной перемеиной. Брелаз [18! ] использовал степенную эвристику для устранения неопределенности, возникающей после применения эвристики МКЧ. Полученный в итоге алгоритм, несмотря на его простоту, все еше остается наилучшим методом раскрашивания произвольных графов в )г цветов. Харалик и Эллиот [618] предложили эвристику с наименее ограничительным значением. Расширению популярности методов распространения ограничений способствовало успешное решение Вальцем [1552] задач полиэдральной линейной разметки для систем компьютерного зрения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
