Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 60
Текст из файла (страница 60)
Вальц показал, что применение методов распространения ограничений при решении многих задач позволяет полностью исключить необходимость в использовании возвратов. Монтанари [1073] ввел понятие сетей ограничений и предложил метод распространения ограничений на основе понятия совместимости пути.
Ален Макворт [967] предложил алгоритм АС-3 для обеспечения совместимости дуг, а также выдвинул обшую идею о том, что поиск с возвратами необходимо сочетать с обеспечением совместимости некоторой степени. Более эффективный алгоритм обеспечения совместимости дуг, АС-4, был разработан Мором и Хендерсоном [1068]. Вскоре после появления статьи Макворта исследователи приступили к экспериментам в области поиска компромисса между затратами на обес- Глава 5. Задачи удовлетворения ограничений 235 печение совместимости и достигаемыми за счет этого преимуществами с точки зрения сокращения объема поиска. Харалик и Эллиот [618) предпочли минимальный алгоритм предварительной проверки, описанный Макгрегором [1028), а Гашниг [522) предложил применять полную проверку совместимости дуг после присваивания значения каждой переменной; в дальнейшем соответствующему алгоритму в работе Сабина и Фрейдера [! 335) было присвоено название МАС.
В последней статье представлены некоторые убедительные свидетельства того, что при решении более трудных задач СБР полная проверка совместимости дуг вполне окупается. Фрейдер [497), [498) исследовал понятие [г-совместимости и ее связь со сложностью решения задач СБР. Апт [36] описал универсальную алгоритмическую инфраструктуру, в рамках которой могут быть проанализированы алгоритмы распространения совместимости.
Специальные методы обработки ограничений высокого порядка были созданы в основном в контексте логического программирования в ограничениях. Превосходный обзор исследований в этой области приведен в [987]. Ограничение д22 ЖЕГ исследовалось в [1272). Ограничения с пределами были включены в тематику логического программирования в ограничениях ван Хентенриком и др. [1533]. Основной метод обратного перехода был разработан Джоном Гашнигом [521), [522]. Кондрак и ван Бик [831) показали, что этот алгоритм по сути перекрывается алгоритмом предварительной проверки. Обратный переход, управляемый конфликтами, был предложен Проссером [1240). Наиболее общая и мощная форма интеллектуального поиска с возвратами фактически разработана еще довольно давно Стал- маном и Зюссманом [1456].
Предложенный ими метод 'в, поиска с возвратами, управляемого зависимостями, привел к разработке систем обеспечения истинности [409], которые будут рассматриваться в разделе ! 0.8. Связь между этими двумя научными областями проанализирована в [348). В указанной работе Сталмана и Зюссмана была также предложена идея Ъ.
регистрации ограничения, в соответствии с которой частичные результаты, полученные в ходе поиска, можно сохранять и повторно использовать на последующих этапах этого поиска. Данная идея бьиа введена формально в поиск с возвратами Дектером [366). Особенно простым методом является 'в. проставлеиие обратных отметок [522), в котором для предотвращения повторной проверки ограничений сохраняются и используются совместимые и несовместимые попарные присваивания. Проставление обратных отметок можно комбинировать с обратным переходом, управляемым конфликтами; в [831) представлен гибридный алгоритм, который превосходит любой из этих методов, отдельно взятых (и это подтверждается формальным доказательством). В методе 'га динамического поиска с возвратами [558) сохраняются успешные частичные присваивания из полученных позднее подмножеств переменных при поиске с возвратами по предыдущему варианту, который не влияет на дальнейший успех.
Применение локального поиска при решении задач удовлетворения ограничений стало популярным после публикации [799] с описанием метода эмуляции отжита (см. главу 4), который широко используется для решения задач планирования. Эвристика с минимальными конфликтами была впервые предложена в [601) и независимо разработана в [1058]. В [1447) показано, как эта эвристика может использоваться для решения задачи с 3 000 000 ферзей меньше чем за минуту.
Этот поразительный успех локального поиска на основе эвристики с минимальными конфликтами при решении задачи с и ферзями привел к переоценке характера и распространения "легких" 236 Часть П. Решение проблем и "трудных" задач. В [244] исследовалась сложность задач СБР, сформированных случайным образом, и было обнаружено, что почти все такие задачи являются либо тривиально легкими, либо не имеют решений.
"Трудные" экземширы задач встречаются, только если параметры генератора задач устанавливаются в некотором узком диапазоне, в пределах которого лишь примерно половина задач является разрешимой. Этот феномен рассматривается дополнительно в главе 7. Исследования„касающиеся структуры и сложности задач СВР, начались с [499], где было показано, что поиск в деревьях с совместимыми дугами происходит без каких-либо возвратов. Аналогичные результаты применительно к ациклическим гиперграфам были получены в области теории баз данных [92].
Со времени публикации этих статей достигнут значительный прогресс в части получения более общих результатов, касающихся связи между сложностью решения задачи СВР и структурой ее графа ограничений. Понятие ширины дерева было введено специалистами по теории графов Робертсоном и Сеймуром [1295].
Дектер и Перл [372], [373], основываясь на работе Фрейдера, применяли то же понятие [названное ими иидуцироваииой шириной) к задачам удовлетворения ограничений и разработали подход с древовидной декомпозицией, кратко описанный в разделе 5.4. Опираясь на эту работу и на результаты из области теории баз данных, Готлобб и др. [585], [586] разработали понятие ширины гипердерева, которое основано на методе характеризации задачи СВР как гиперграфа. Они не только показали, что любую задачу СБР с шириной гипердерева ьгможно решить за время О(п 12одп1, но и обосновали утверждение, что критерий ширины гипердерева превосходит все ранее предложенные критерии "ширины" в том смысле, что в некоторых случаях ширина гипердерева является конечной, тогда как ширина, определяемая другими критериями, — неограниченной.
В литературе можно найти несколько хороших обзоров с описанием методов решения задач СВР, включая [73], [370] и [866], а также энциклопедические сборники статей [368] и [968]. В [1194] приведен обзор разрешимых классов задач С8Р и описаны как методы структурной декомпозиции, так и методы, основанные на свойствах областей определения или свойствах самих ограничений. В [83Ц приведен аналитический обзор алгоритмов поиска с возвратами, а в [56] приведен обзор, характеризующийся большей практической направленностью. В [987] и [1514] эта тематика рассматривается гораздо более глубоко, чем было возможно ее представить в данной главе. Некоторые интересные приложения описаны в сборнике статей [500], который вышел под редакцией Фрейдера и Макворта.
Статьи на тему удовлетворения ограничений регулярно публикуются в журнале Агг[7]с!а! йге!!!8елсе и в специализированном журнале Сопзггатгж Основным местом встречи специалистов в этой области является конференция 1пгегпагуопа! Софегепсе ов Рппс!Р!ш апг! Ргасцсе о! Сопзггат! Ргоагавтт8, часто называемая просто СР. УПРАЖНЕНИЯ 5.1. Самостоятельно сформулируйте определения следующих понятий: проблема удовлетворения ограничений, ограничение, поиск с возвратами, совместимость дуги, обратный переход и минимизация конфликтов.
5.2. Сколько решений имеет задача раскрашивания карты, показанная на рис. 5.1? 23? Глава 5. Задачи удовлетворения ограничений з В (560) обсуждается несколько методов составления кроссвордов. В (938) рассматривается более сложная задача их решения. 5.3. 5.4. 5.5. 5.6. 5.7. Объясните, почему при поиске решения задачи СЗР одна из хороших эвристик состоит в том, что следует выбирать переменную, которая является наиболее ограниченной, и вместе с тем выбирать наименее ограничительное значение.
Рассмотрите задачу составления (а не решения) кроссвордов'. подбора слов, которые укладываются в прямоугольную сетку. Эта сетка, которая указывается как часть задания, определяет, какие квадраты пусты и какие затенены. Предположим, что предоставлен список слов (например, словарь) и задача состоит в том, чтобы заполнить пустые квадраты с использованием любого подмножества из этого списка.
Точно сформулируйте эту задачу следующими двумя способами. а) Как общую задачу поиска. Выберите соответствующий алгоритм поиска и определите эвристическую функцию, если, по вашему мнению, она необходима. Как лучше заполнять пустые квадраты: одновременно по одной букве или по одному слову? б) Как задачу удовлетворения ограничений. Должны ли переменные быть представлены в виде слов или букв? Какая формулировка, по вашему мнению, является наилучшей? Объясните, почему? Приведите точные формулировки каждой из перечисленных ниже задач в виде задач удовлетворения ограничений. а);ъ.
Планирование покрытия пола прямоугольниками. Найти в большом прямоугольнике неперекрываюшиеся места для размещения меньших прямоугольников. б) 'ж Составление расписания занятий. Определены следующие исходные данные: постоянное количество преподавателей и классов, список предлагаемых занятий и список возможных временных интервалов для занятий.
С каждым преподавателем связано множество занятий, которые он может проводить. Решите криптоарифметическую задачу, приведенную на рис. 5.2, вручную, с помощью поиска с возвратами, предварительной проверки, а также на основе эвристик с М)кЧ и наименее ограничительным значением. (Й В табл. 5.! приведены результаты проверки производительности различных алгоритмов при решении задачи с и ферзями. Проведите испытания тех же алгоритмов при решении задач раскрашивания карты, формируемых случайным образом, с помощью следующего метода: разбросать и точек на елиничном квадрате; выбрать точку х случайным образом, соединить х прямой линией с ближайшей точкой у, такой, что х еше не соединена с у, и соединительная линия не пересекает какую-либо другую линию; повторять предыдущий шаг до тех пор, пока не будет исключена возможность проводить дальнейшие соединения.
Сформируйте таблицу производительности для наибольшего значения п, с которым удастся справиться с помошью этих алгоритмов, используя как с?=4, так и с?=3 цветов. Прокомментируйте полученные вами результаты. 238 Часть Н. Решение проблем Воспользуйтесь алгоритмом лС-3, чтобы показать, что проверка совместимо- сти дуг позволяет обнаружить несовместимость частичного присваивания ((ул=гес(, У=В?ие) для задачи, показанной на рис. 5.1. Какова в наихудшем случае временная сложность при прогоне алгоритма дс- 3 применительно к задаче СБР с древовидной структурой? 5.8. 5.9. 5.10.
Алгоритм АС-3 помешает обратно в очередь каждую дугу (х„, х,) каждый раз, когда любое значение удаляется из области определения х,, даже если каждое значение х, совместимо с несколькими оставшимися значениями х,. Предположим, что для каждой дуги (Х„, х;) отслеживается количество оставшихся значений х,, которые являются совместимыми с каждым значением х„. Объясните, как можно эффективно обновлять эти числа, и тем самым докажите, что совместимость дуг можно обеспечить за суммарное время О ( и'с)') . "я+в=с", в три бинарных ограничения с использованием вспомогательной переменной. Может быть принято предположение о конечных областях определения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
