Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 54
Текст из файла (страница 54)
криптоарифметические головоломки, называемые также числовыми ребусами (рис. 5.2, а). Обычно предъявляется требование, чтобы каждая буква в криптоарифметической головоломке представляла отдельную цифру. В случае задачи, показанной на рис. 5.2, а, такое требование может быть выражено с помощью ограничения с шестью переменными л22с11 Гг (к, т, гг, гг, к, о) . Иным образом это требование может быть представлено в виде коллекций бинарных ограничений, таких как умт. Ограничения сложения для четырех столбцов этой головоломки также включают несколько переменных и могут быть записаны следующим образом: О~О=К+1О Х Хг ь гг + У = У ~ 10 Х2 х2+т+т=о+1О'хз хз = е где х„х, и х, — 'пк вспомогательные переменные, представляющие цифру (О или 1), которая переносится в следующий столбец.
Ограничения высокого порядка могут быть представлены в виде 'в. гиперграфа ограничений, подобного приведенному на рис. 5.2, б. Внимательный читатель заметит, что ограничение л22с)2 ГЕ может быть разбито на бинарные ограничения — кгт, к~гг и тд. И действительно, в упр. 5.11 предлагается доказать, что каждое ограничение высокого порядка с конечной областью определения можно свести к множеству бинарных ограничений, введя достаточное количество вспомогательных переменных. В связи с этим в данной главе будут рассматриваться только бинарные ограничения. 214 Часть П.
Решение проблем ти о +ти о ь) б) Рис. 5.2. Пример криптоарифметической задачи: каждая буква обозначает отдельную цифру; задание состоит в том, чтобы найти такую замену букв цифрами, чтобы результирующее выражение суммирования было арифметически правильным, с дополнительным ограничением, что наличие ведущих нулей не допускается 1а); гиперграф ограничений для этой криптоарифметической задачи, на котором показано ограничение Л11дй с б, а также ограничения сложения по столбцам; каждое ограничение обозначено квадратом, который соединен с ограничиваемыми им переменными 1б) Все ограничения, рассматривавшиеся до сих пор, были абсолютными ограничениями, нарушение которых равносильно тому, что какое-то потенциальное решение больше не рассматривается как таковое.
С другой стороны, во многих реальных задачах СЕР применяются ограничения 'ъ. предпочтения, которые указывают, какие решения являются предпочтительными. Например, в задаче составления расписания занятий в университете может потребоваться учесть, что профессор х предпочитает проводить занятия по утрам, а профессор у — после полудня. Расписание занятий, в котором предусмотрено проведение профессором х занятия в 14:00, все еше может рассматриваться как решение (если ие окажется, что профессор х должен в зто время председательствовать на заседании кафедры), но уже не будет оптимальным.
Ограничения предпочтения часто можно закодировать как стоимости присваиваний отдельных переменных; например, за назначение профессору х послеполуденного интервала придется заплатить 2 пункта, которые будут учтены в суммарном значении целевой функции, в то время как утренний интервал имеет стоимость 1 пункт.
При использовании такой формулировки задачи СБР с предпочтениями можно решать, используя методы поиска с оптимизацией, либо основанные на поиске пути, либо локальные. Подобные задачи СВР в данной главе больше не рассматриваются, но в разделе с библиографическими заметками приведены некоторые ссылки. 5.2.
ПРИМЕНЕНИЕ ПОИСКА С ВОЗВРАТАМИ ДЛЯ РЕШЕНИЯ ЗАДАЧ СБР В предыдушем разделе приведена формулировка задач СВР в виде задач поиска. Если используется такая формулировка, то появляется возможность решать задачи 2!5 Глава 5. Задачи удовлетворения ограничений СБР с помощью любых алгоритмов поиска, приведенных в главах 3 и 4. Предположим, что мы применяем алгоритм поиска в ширину к универсальной формулировке задачи СБР, приведенной в предыдущем разделе.
Но мы быстро обнаружим нечто ужасное; коэффициент ветвления на верхнем уровне равен пс), поскольку любое из с( значений может быть присвоено любой из п переменных. На следующем уровне коэффициент ветвления равен (и-1) г[ и т.д., на всех и уровнях. При этом создается дерево с п.. с)" ветвями, даже несмотря на то, что имеется только с)" возможных полных присваиваний! В применяемой нами формулировке задачи, которая внешне казалась разумной, но оказалась плохо продуманной, не было учтено существенно важное свойство, общее для всех задач СЯР, —;з. коммутативиость. Задача называется коммутативной, если порядок применения любого конкретного множества действий в процессе ее решения не влияет на результат.
Именно это свойство характерно для задач СИР, поскольку, присваивая значения переменным, мы достигаем одного и того же частичного присваивания независимо от порцдка присваивания. Поэтому гр- во всех алгоритмах поиска СЯР преемники формируются с учетом возможных присваиваний только для единственной переменной в каждом узле дерева поиска. Например, в корневом узле дерева поиска в задаче раскрашиВаиня КартЫ АВСтраЛИИ МОЖНО ИМЕТЬ ВЫбср МЕжду Ялгдае(, Яд=дХЕЕП И яд=а па, НО МЫ НИКОГда НЕ дОЛжНЫ ВЫбИратЬ МЕжду ддг лад И (уй=)Э1 НЕ.
ОПрЕ- лелив такое условие, можно надеяться сократить количество листьев до сР. Поиск в глубину, в котором каждый раз выбираются значения для одной переменной и выполняется возврат, если больше не остается допустимых значений, которые можно было бы присвоить переменной, называется Ъ. поиском с возвратами. Этот алгоритм поиска приведен в листинге 5.1. Обратите внимание на то, что в этом алгоритме по су)пеству используется метод инкрементного формирования преемников по одному преемнику за один раз, который описан на с. 131. Кроме того, для формирования преемника текущее присваивание дополняется, а не копируется. Поскольку это представление задач СБР стандартизировано, то в функции вас)сгхас)сйпд-Веахсп не требуется учитывать начальное состояние, функцию определения преемника или проверку цели, характерные для рассматриваемой проблемной области. Часть дерева поиска для задачи раскраски карты Австралии показана на рис.
5.3, где значения присваиваются переменным в порядке )гл,ит, 2,.... Листинг 5.1. Простой алгоритм поиска с возвратами для решения задач удовлетвореппя ограничеппй свр. Этот алгоритм составлен по принципу рекурсивного поиска в глубину, описанного в главе 3. Функции ве1еос-ппаввйдпег(-згасйаьзе и Оспах-Погпайп-ЗГа1пав могут использоваться для реализации эвристических функций обшего пязпвчеппя, которые ряссмвтрпввшгся в тексте данной главы Еппоейоп Васкехасхьпд-БеахсЬ(сяр) хеспсав решение хеян1С или индикатор отказа Еа11нхе хеепкп деспхвзче-вас)сегас)сьпд((), сяр) Епповйоп Весихяйие-Васкехасхйпд(аяяддпшепс, сяр) сеепзпв решение геяи1С или индикатор отказа Еа11нхе зЕ присваивание аяяйдпшепс является полным СЬев сеспсп аяяйдпшепс пах <- яе1есс-Ппаяя1дпеб- гахзаЬ1е(чахзаЬ1ея[сяр), аяяддпшепс, сяр) 2|6 Часть!!.
Решение проблем Еог еесЬ иа1ие Ьп Огдег-поиаьп-ча1иея(наг, аяяздптепе, сяр) что ЬЕ значение иа1ие является совместимым с присваиванием аяяддпеепс согласно ограничениям Сопяггаьпся(сяр! ЕЬеп добавить (иаг = иа1ие) к присваиванию аяя1дптепс геяи1с ь- неспгяьче-васхегас)сьпд(аяя1дптепс, сяр) 1Е геяи1С Ф Еа11иге ЕЬеп гегпгп геяи1С удалить (иаг = иа1ие) из присваивания аяяздптепе геспгп Еаз1иге Рис.
5.3. Часть дерева поиски, сформированного путем простого поиска с возвратами при решении задачи раскрашивания карты, приведенной на рис. 5. 1 Согласно определениям, приведенным в главе 3, алгоритм простого поиска с возвратами представляет собой неинформированный алгоритм, поэтому не следует рассчитывать на то, что он окажется очень эффективным при решении крупных задач.
Результаты его применения к некоторым примерам задач показаны в первом столбце табл. 5.1 и подтверждают эти предположения. В главе 4 было показано, что такой недостаток неинформированных алгоритмов поиска, как низкая производительность, можно устранить, предусмотрев использование в них эвристических функций, соответствуюших данной проблемной области, которые основаны на наших знаниях о данной задаче. Как оказалось, задачи СБР можно решать эффективно без таких знаний о конкретной проблемной области. Вместо этого в данной главе будут разработаны методы общего назначения, позволяющие найти ответ на перечисленные ниже вопросы. ° Какой переменной должно быть присвоено значение в следующую очередь и в каком порядке необходимо пытаться присваивать эти значения? ° Как влияют текущие присваивания значений переменным на другие перемен- ные с неприсвоенными значениями? ° Если какой-то путь оказался неудачным (т.е.
достигнуто состояние, в котором ни одна переменная не имеет допустимых значений), позволяет ли поиск избежать повторения этой неудачи при прохождении последующих путей? В приведенных ниже подразделах по очереди даны ответы на каждый из этих вопросов. 217 Глава 5. Задачи удовлетворения ограничений Локальный по- Локальный поиск Локальный поиск с нредварн- с предварительной иск с мннимальтельной проаер- проверкой на ос- ными конфлнккой нове МКУ тами Поиск с возвратами на основе МКУ Поиск с воз- аратамн Задача (> 1ОООК) (>!ОООК) 2К 60 64 Определение раскраски в 4 цвета лля 50 штатов США 13 500К (> 40 ОООК) 817К 1К 35К 0,5К 4К Задача с в ферзями (> 40 ОООК) Головоломка с 3859К зеброй Сформированная 415К случайным образом задача 1 2К ЗК 26К 2К 77К Сформированная 942К случайным образом задача 2 27 К 15К Упорядочение переменных и значений Приведенный выше алгоритм поиска с возвратами содержит следующую строку: пас < — Бе1есг-Ппаэпбдпег)-уаг[аЫе(уахьаЬ1еа ! слр), аэлбдптепг, слр) По умолчанию функция Бе1есь-Ппаээйдпес)-ЧагйаЬ1е выбирает слсдуюгцую переменную с нсприсвоснным значением в порядке, указанном в списке УагйаЬ1еэ [слр!.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
