Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 52
Текст из файла (страница 52)
УПРАЖНЕНИЯ 4.1. Выполните трассировку работы алгоритма поиска А* применительно к решению задачи проезда в город Бухарест из города Лугож с использованием эвристической функции определения расстояния по прямой. Иными словами, по- Глава 4. Информированный поиск и исследование пространства состояний 205 4.3. 4.4.
4.5. 4.6. 4.7. 4.8. кажите последовательность узлов, которые рассматриваются этим алгоритмом, и приведите оценки г, о и Л для каждого узла. Эвристический алгоритм поиска пути представляет собой алгоритм поиска по первому наилучшему совпадению, в котором целевая функция равна Е(п) = (2-м! д(п)+юй(п) .
Для каких значений ы гарантируется оптимальность этого алгоритма? (Может быть принято предположение, что функция ?з является допустимой.) Какого рода поиск выполняется в этом алгоритме, когда ь-О? Когда ь-1? Когда ь-2? Докажите каждое из приведенных ниже утверждений. а) Поиск в ширину представляет собой частный случай поиска по критерию стоимости. б) Поиск в ширину, поиск в глубину и поиск по критерию стоимости (цпйопп-соы зеагс!з) — специальные случаи поиска по первому наилучшему совпадению.
в) Поиск по критерию стоимости — специальный случай поиска А*. Ф Предложите такое пространство состояний, в котором применение поиска А* с использованием алгоритма Стар!з-яеагс!з приводит к получению неоптимального решения при наличии функции б ! п), которая является допустимой, но непреемственной.
На с. 15б было показано, что применение эвристической функции определения расстояния по прямой приводит к тому, что жадный поиск по первому наилучшему совпадению безвозвратно углубляется в дерево поиска при решении задачи проезда от города Яссы до города Фэгэраш. Однако эта эвристическая функция работает идеально при решении противоположной задачи— поиска пути проезда от города Фэгэраш до города Яссы. Существуют ли такие задачи, в которых эта эвристическая функция исключает возможность успешного выполнения задачи поиска пути в любом из направлений? Предложите эвристическую функцию для задачи игры в восемь, которая иногда допускает переоценку, и покажите, каким образом это может привести к получению неоптимального решения некоторых конкретных экземпляров задачи.
(Для упрощения работы при выполнении упражнения можете использовать компьютер.) Докажите, что если функция ?з никогда не переоценивает стоимость больше чем на с, то алгоритм А' с использованием функции ?з возвращает решение, стоимость которого превышает оптимальное решение не больше чем на с. Докажите, что если эвристическая функция является преемственной, то она должна быть допустимой. Составьте допустимую эвристическую функцию, которая не является преемственной. (Й Задача коммивояжера (Тгачейпй ба!езрегзоп РгоЫет — ТЗР) может быть решена с помощью эвристической функции, основанной на определении минимального связующего дерева (М!пппшп брапп!пй Тгее — МЗТ), которая используется для оценки стоимости завершения обхода, при условии, что уже был сформирован частичный путь обхода. Стоимость МБТ для множества городов представляет собой минимальную сумму стоимостей соединений в любом дереве, которое связывает все города.
20б Часть Н. Решение проблем а) Покажите, как можно вывести эту эвристическую функцию на основе одной из ослабленных версий задачи ТБР. б) Покажите, что эвристическая функция МБТ доминирует над эвристической функцией определения расстояния по прямой. в) Напишите генератор задач для создания экземпляров задачи Т5Р, в которых города представлены случайно выбранными точками в единичном квадрате.
г) Найдите в литературе эффективный алгоритм формирования МБТ и примените его в сочетании с допустимым алгоритмом поиска для решения экземпляров задачи ТЯР. На с. 171 был определен ослабленный вариант задачи игры в восемь, в котором любая фишка может перемещаться из квадрата л в квадрат в, если квадрат в является пустым. Точное решение этой задачи предусматривает определение эвристической функции Гашнига [522]. Объясните, почему эвристическая функция Гашнига является, по меньшей мере, такой же точной, как и функция й, (в которой учитываются фишки, стоящие не на месте), и продемонстрируйте случай, в которых она является более точной по сравнению и с )з„, и с Л, (в которой используется манхэттенское расстояние).
Можете ли вы предложить способ эффективного вычисления эвристической функции Гашнига? 4.9. 4.10. Йз В данной главе были описаны две простые эвристические функции для за- дачи игры в восемь; в одной из них учитывается манхэттенское расстояние, а в другой — стояшие не на месте фишки. В литературе предложено также несколько других эвристических функций, предназначенных для использования в качестве улучшенной замены этих двух (см., например, [617], [1092] и [1141]). Проверьте обоснованность этих претензий, реализовав соответствующие эвристические функции и сравнив производительность полученных алгоритмов. 4.11. Укажите название алгоритма, который фактически становится следствием применения каждого из перечисленных ниже частных случаев.
а) Локальный лучевой поиск с )с=1. б) Локальный лучевой поиск с одним начальным состоянием и без ограничений на количество хранимых состояний. в) Моделируемый отжиг с постоянным значением т=о (и исключенной проверкой завершения). г) Генетический алгоритм с размером популяции дг=1. имеется хороший метод сравнения — способ определения того, является ли один узел лучше другого, без присваивания числовых значений тому и друго- му. Покажите, что этого достаточно для выполнения поиска по первому наи- лучшему совпадению. Есть ли соответствующий аналог алгоритма А*? 4.13. Определите, как связана временная сложность алгоритма ЖАКТА* с его пространственной сложностью.
4.14. Предположим, что некоторый агент находится в среде лабиринта 3х3, подоб- ного приведенному на рис. 4.12. Агенту известно, что его первоначальным местонахождением является пункт (1, 1), что цель находится в пункте (3, 3) и 4.12. Иногда не существует хорошей функции оценки для некоторой задачи, но Глава 4.
Информированный поиск и исследование пространства состояний 207 4.15. 4. 16. 4.17. что четыре действия, ггр, поьзз, ьеЕс, л1д?зс, приводят к своим обычным последствиям, если не будут заблокированы стеной. Агент не знает о том, где находятся внутренние стены. В любом конкретном состоянии агент воспринимает информацию о множестве допустимых действий; он также может определить, является ли данное состояние тем, которое он уже посещал ранее, или представляет собой новое состояние.
а) Объясните, каким образом к этой задаче поиска в оперативном режиме можно применить такую трактовку, чтобы она могла рассматриваться как поиск в автономном режиме в пространстве доверительных состояний, где первоначальное доверительное состояние включает все возможные конфигурации среды. Насколько велико это первоначальное доверительное состояние? Насколько велико все пространство доверительных состояний? б) Какое количество различных вариантов восприятия возможно в первоначальном состоянии? в) Опишите первые несколько ветвей плана действий в непредвиденных ситуациях для этой задачи.
Насколько велик этот план в полном виде (дайте приблизительную оценку)? Обратите внимание на то, что этот план действий в непредвиденных ситуациях является решением для каждой возможной среды, соответствующей данному описанию. Поэтому, строго говоря, чередование поиска и выполнения не требуется даже в неизвестных вариантах среды.
Ф В данном упражнении исследуется направление использования локальных методов поиска для решения задач ТБР такого типа, который определен в упр. 4.8. а) Предложите подход к решению задач ТЗР на основе поиска с восхождением к вершине. Сравните эти результаты с оптимальными решениями, полученными на основе алгоритма А' с эвристической функцией МВТ (упр. 4.8). б) Предложите подход к решению задачи коммивояжера с помощью генетического алгоритма. Сравните результаты обоих подходов. Для ознакомления с некоторыми рекомендациями по выбору представлений вы можете обратиться к [890]. 1Й Сформируйте большое количество экземпляров игры в восемь и задачи с восемью ферзями и найдите их решения (там, где это возможно) с помощью поиска с восхождением к вершине (в варианте подъема по самому крутому склону и в варианте поиска по первому наилучшему совпадению), поиска с восхождением к вершине с перезапуском случайным образом и поиска с эмуляцией отжита.
Измерьте стоимость поиска и процентное соотношение решенных задач, а также нанесите этн данные на график наряду с данными об оптимальной стоимости решения. Прокомментируйте полученные вами результаты. Йв В данном упражнении исследуется применение поиска с восхождением к вершине в контексте робототехнической навигации, с использованием в качестве примера среды, показанной на рис. 3.14.
а) Повторите упр. 3.16 с использованием поиска с восхождением к вершине. Зашел ли когда-либо предложенный вами агент в тупик в локальном ми- 208 Часть 11. Решение проблем нимуме? Возможно ли, чтобы он зашел в тупик при наличии выпуклых препятствий? б) Сформируйте среду с препятствиями в виде невыпуклых многоугольников, в которой агент может оказаться в тупике. в) Модифицируйте алгоритм поиска с восхождением к вершине таким образом, чтобы вместо выполнения поиска на глубину 1 для принятия решения о том, куда двигаться дальше, агент предпринимал бы поиск на глубину )г.
Он должен находить наилучший путь, состоящий из )г этапов, проходить по нему на один этап, а затем повторять процесс. г) Существует ли такое значение?с, при котором новый алгоритм гарантирует выход из локальных минимумов? д) Объясните, благодаря чему алгоритм 1.йТА* позволяет агенту выходить из локальных минимумов в этом случае. 4.18. Йи Сравните производительность алгоритмов А' и ВВРЯ на множестве случайно сформированных экземпляров задач в проблемных областях задачи игры в восемь (с манхэттенским расстоянием) и задачи ТЯР (с МБТ вЂ” см. упр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
