Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 57

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 57)

Таким образом, если каждая переменная в данном примере имеет область определения (2, 3, 4, 5, б), то из каждой области определения можно удалить значения 5 и б. При решении крупных задач проверки ресурсных ограничений с целочисленными значениями (таких как задачи снабжения, в которых предусматривается перемешение тысяч людей в сотнях транспортных средств) обычно не существует возможности представлять область определения каждой переменной в виде большого множества целых чисел и постепенно сокращать это множество с применением методов проверки совместимости.

Вместо этого области определения представляются в виде верхнего и нижнего пределов и управляются с помощью метода распространения этих пределов. Например, предположим, что имеются два рейса, Рггдлг272 и РгддЛС272, в которых самолеты имеют соответственно вместимость 165 и 385 пассажиров. Поэтому начальные области определения для количества пассажиров в каждом рейсе определяются следующим образом: Ргддлегтг я (о,таз) и и) 'длсгтг а (о,зв51 Теперь допустим, что имеется дополнительное ограничение, согласно которому в этих двух рейсах необходимо перевести 420 человек: Часть И. Решение проблем 224 Р1ддье271+кдгдие27да [420, 420] Распространяя ограничения пределов, можно сократить области определения до та- ких величин: яз'дЛЕгтЗ В [Зв,тьь] и Пдддсгтг а [ЗЗВ,ЗВЗ] Задача СБР называется совместимой с пределами (Ьоцп<Ь-сопз[згепг), если для каждой переменной х, а также одновременно для нижнего и верхнего предельных значений х существует некоторое значение у, которое удовлетворяет заданному ограничению между х и у для каждой переменной к Такого рода 'з.

распространение пределов (Ьоипбз ргораяагюп) широко используется в практических задачах с ограничениями. Интеллектуальный поиск с возвратами: поиск в обратном направлении В алгоритме васКггасКьпд-яеагсЬ, приведенном в листинге 5.1, применялось очень простое правило, касающееся того, что делать, если какая-то ветвь поиска оканчивается неудачей: вернуться к предыдущей переменной и попытаться использовать для нее другое значение.

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

5.1, с постоянным упорядочением переменных 0, лж[, у, т, яд, ид], ]дт. Предположим, что сформировано частичное присваивание []2=з.ес], гдяи=дз-ееп, [г=Ыие, т=гег]]. А после попытки присвоить значение следующей переменной, ял, будет обнаружено, что любое значение нарушает какое-то ограничение. Алгоритм возвращается к узлу т и пытается назначить новый цвет для Тасмании! Очевидно, что это — бессмысленное действие, поскольку смена цвета Тасмании не позволяет решить проблему с Южной Австралией. Более интеллектуальный подход к поиску с возвратами состоит в том, чтобы вернуться к одному из множеств переменных, которые стали причиной неудачи.

Это множество называется 'в, конфликтным множеством; в данном случае конфликтным множеством для ЯА является (О, ]два[, ]г]. Вообще говоря, конфликтное множество для переменной х представляет собой множество переменных с ранее присвоенными значениями, которые связаны с зг ограничениями.

Метод 'ъ. обратного перехода выполняет обратный переход к переменной с последним по времени присвоенным значением из конфликтного множества; в данном случае в обратном переходе следует перескочить через узел Тасмании и попытаться применить новое значение для ы Такая операция может быть легко реализована путем модификации алгоритма НасКГгасКзпд-ЯеагсЬ таким образом, чтобы он накапливал данные о конфликтном множестве, одновременно проверяя одно из значений, допустимых для присваивания. Если не будет найдено ни одного допустимого значения, алгоритм должен возвратиться к последнему по времени элементу конфликтного множества и наряду с этим установить индикатор неудачи. Внимательный читатель уже должен был заметить, что предварительная проверка позволяет определить конфликтное множество без дополнительной работы, поскольку каждый раз, когда процедура предварительной проверки, основанная на присваивании значения переменной зг, удаляет некоторое значение из области оп- Глава 5.

Задачи удовлетворения ограничений 225 ределения у, она должна добавить хк конфликтному множеству к Кроме того, каждый раз, когда это последнее значение удаляется из области определения у, переменные из конфликтного множества у добавляются к конфликтному множеству х В этом случае после перехода к у можно сразу же установить, куда должен быть выполнен обратный переход в случае необходимости. А проницательный читатель уже должен был заметить нечто странное: обратный переход происходит, когда каждое значение в некоторой области определения конфликтует с текущим присваиванием, но предварительная проверка обнаруживает этот случай и вообще исключает возможность достижения такого узла! В действительности можно показать, что ср- каждая ветвь, отсекаемая с помощью обратного перехода, отсекается также с помощью предварительной проверки.

Поэтому простой поиск с обратным переходом в сочетании с поиском с предварительной проверкой становится избыточным, а фактически обратный переход избыточен в любом поиске, в котором используется более строгая проверка совместимости, такая как МАС. Несмотря на замечания, сделанные в предыдущем абзаце, идея, лежащая в основе обратного перехода, остается перспективной, если возврат осуществляется с учетом причин неудачи.

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

Предположим, что на следующем этапе предпринимается попытка присваивания Т=кес1, а затем осуществляется присваивание значений переменным Ит, д, Гг, яЛ. Известно, что ни одно присваивание не применимо для этих последних четырех переменных, поэтому в конечном итоге не остается доступных значений, которые можно было бы попытаться присвоить переменной вт. Теперь возникает вопрос, куда выполнить возврат? Обратный переход не может применяться, поскольку в области определения переменной вгт имеются значения, совместимые со значениями, ранее присвоенными переменным, — переменная дгт не имеет полного конфликтного множества из переменных с ранее присвоенными значениями, которое вызвало бы неудачу при попытке присваивания ей значения.

Однако известно, что неудачу вызывают четыре переменные, ГгТ, !2, Гг и Ы, вместе взятые, поскольку во множестве переменных с ранее присвоенными значениями должны существовать такие переменные, которые непосредственно конфликтуют с этими четырьмя. Эти рассуждения приводят к созданию более глубокого определения понятия конфликтного множества для такой переменной, как зчт'. ноги)!ликтным множеством называется множество переменных с ранее присвоенными значениями, которые, наряду со всеми переменными со значениями, присваиваемыми в дальнейшем, становятся причиной того, что для ьгт не существует совместимого решения. В таком случае конфликтное множество состоит из переменных ьггг и вангу, поэтому алгоритм должен выполнить возврат к ияг и пропустить переменную, соответствующую Тасмании.

Алгоритм обратного перехода, в котором используются конфликтные множества, определенный таким образом, называется Ж алгоритмом обратного перехода, управляемого конфликтами (сопрйсг-д)гесгед ЬасЦцшр)пя). Теперь необходимо обьяснить, как вычисляются эти новые конфликтные множества. Применяемый для этого метод фактически очень прост.

"Окончательная" неудача в какой-то ветви поиска всегда возникает из-за того, что область определения некоторой переменной становится пустой; эта переменная имеет типичное 226 Часть П. Решение проблем конфликтное множество. В данном примере неудача возникает при присваивании значения переменной яд, а ее конфликтным множеством является (скажем) ( йгд, ит, а). Выполняется обратный переход к переменной 0, и эта переменная поглощает конфликтное множество, полученное от ял (безусловно, после исключения из него самой переменной 0), объединяя его со своим собственным прямым конфликтным множеством, представляющим собой (дгт,дгяйг); новым конфликтным множеством становится (игл, ит, лгж). Это означает, что, продолжая поиск от (2, нельзя найти решение при наличии ранее выполненного присваивания переменным ( игл, )ут, )(гяйг) .

Поэтому обратный переход выполняется к переменной ит, присваивание значения которой выполнено последним по времени по сравнению с другими этими переменными. Переменная ит поглощает множество (игл, дгт, дг~йг) — (вгт), объединяя его со своим собственным прямым конфликтным множеством ( йи), что приводит к получению ( игл, лг~йг) (как было указано в предыдущем абзаце). Теперь алгоритм осуществляет обратный переход к лгяйг, как и предполагалось. Подведем итог: допустим, что х, — текущая переменная, а сопй(хз) — ее конфликтное множество.

Если все попытки присваивания каждого возможного значения переменной хз оканчиваются неудачей, то необходимо выполнить возврат к переменной хг с последним по времени присвоенным значением во множестве сопй(х,) и установить: сонг(х,) + — сопГ(хг) г.г сонг(хз) — (Хг) Обратный переход, управляемый конфликтами, позволяет вернуться в правильную точку дерева поиска, но не предотвращает возможности возникновения таких же ошибок в другой ветви того же дерева.

Характеристики

Список файлов книги