УПРАЖНЕНИЯ
4.1. Выполните трассировку работы алгоритма поиска А* применительно к решению задачи проезда в город Бухарест из города Лугож с использованием эвристической функции определения расстояния по прямой. Иными словами, покажите последовательность узлов, которые рассматриваются этим алгоритмом, и приведите оценки f, д и h для каждого узла.
4.2. Эвристический алгоритм поиска пути представляет собой алгоритм поиска по первому наилучшему совпадению, в котором целевая функция равна f (п) = {2-w) д{п) +wh(n). Для каких значений w гарантируется оптимальность этого алгоритма? (Может быть принято предположение, что функция h является допустимой.) Какого рода поиск выполняется в этом алгоритме, когда w=0? Когда w=l? Когда w=2?
4.3. Докажите каждое из приведенных ниже утверждений.
а) Поиск в ширину представляет собой частный случай поиска по критерию
стоимости.
б) Поиск в ширину, поиск в глубину и поиск по критерию стоимости
(uniform-cost search) — специальные случаи поиска по первому наилуч-
шему совпадению.
в) Поиск по критерию стоимости — специальный случай поиска А*.
4.4. (§Е) Предложите такое пространство состояний, в котором применение поиска А* с использованием алгоритма Graph-Search приводит к получению неоптимального решения при наличии функции h(n), которая является допустимой, но непреемственной.
4.5. На с. 156 было показано, что применение эвристической функции определения расстояния по прямой приводит к тому, что жадный поиск по первому наилучшему совпадению безвозвратно углубляется в дерево поиска при решении задачи проезда от города Яссы до города Фэгэраш. Однако эта эвристическая функция работает идеально при решении противоположной задачи — поиска пути проезда от города Фэгэраш до города Яссы. Существуют ли такие задачи, в которых эта эвристическая функция исключает возможность успешного выполнения задачи поиска пути в любом из направлений?
4.6. Предложите эвристическую функцию для задачи игры в восемь, которая иногда допускает переоценку, и покажите, каким образом это может привести к получению неоптимального решения некоторых конкретных экземпляров задачи. (Для упрощения работы при выполнении упражнения можете использовать компьютер.) Докажите, что если функция h никогда не переоценивает стоимость больше чем на с, то алгоритм А* с использованием функции h возвращает решение, стоимость которого превышает оптимальное решение не больше чем на с.
4.7. Докажите, что если эвристическая функция является преемственной, то она должна быть допустимой. Составьте допустимую эвристическую функцию, которая не является преемственной.
4.8. (i§D Задача коммивояжера (Traveling Salesperson Problem — TSP) может быть решена с помощью эвристической функции, основанной на определении минимального связующего дерева (Minimum Spanning Tree — MST), которая используется для оценки стоимости завершения обхода, при условии, что уже был сформирован частичный путь обхода. Стоимость MST для множества городов представляет собой минимальную сумму стоимостей соединений в любом дереве, которое связывает все города.
а) Покажите, как можно вывести эту эвристическую функцию на основе
одной из ослабленных версий задачи TSP.
б) Покажите, что эвристическая функция MST доминирует над эвристиче-
ской функцией определения расстояния по прямой.
в) Напишите генератор задач для создания экземпляров задачи TSP, в которых города представлены случайно выбранными точками в единичном квадрате.
г) Найдите в литературе эффективный алгоритм формирования MST и
примените его в сочетании с допустимым алгоритмом поиска для решения экземпляров задачи TSP.
4.9. На с. 171 был определен ослабленный вариант задачи игры в восемь, в котором любая фишка может перемещаться из квадрата А в квадрат в, если квадрат в является пустым. Точное решение этой задачи предусматривает определение эвристической функции Гашнига [522]. Объясните, почему эвристическая функция Гашнига является, по меньшей мере, такой же точной, как и функция п± (в которой учитываются фишки, стоящие не на месте), и продемонстрируйте случай, в которых она является более точной по сравнению и с hl9 и с п2 (в которой используется манхэттенское расстояние). Можете ли вы предложить способ эффективного вычисления эвристической функции Гашнига?
4.10. (И) В данной главе были описаны две простые эвристические функции для задачи игры в восемь; в одной из них учитывается манхэттенское расстояние, а в другой — стоящие не на месте фишки. В литературе предложено также несколько других эвристических функций, предназначенных для использования в качестве улучшенной замены этих двух (см., например, [617], [1092] и [1141]). Проверьте обоснованность этих претензий, реализовав соответствующие эвристические функции и сравнив производительность полученных алгоритмов.
4.11. Укажите название алгоритма, который фактически становится следствием применения каждого из перечисленных ниже частных случаев.
а) Локальный лучевой поиск с к=1.
б) Локальный лучевой поиск с одним начальным состоянием и без ограничений на количество хранимых состояний.
в) Моделируемый отжиг с постоянным значением Т=0 (и исключенной
проверкой завершения).
г) Генетический алгоритм с размером популяции N=1.
4.12. Иногда не существует хорошей функции оценки для некоторой задачи, но имеется хороший метод сравнения — способ определения того, является ли один узел лучше другого, без присваивания числовых значений тому и другому. Покажите, что этого достаточно для выполнения поиска по первому наилучшему совпадению. Есть ли соответствующий аналог алгоритма А*?
4.13. Определите, как связана временная сложность алгоритма LRTA* с его пространственной сложностью.
4.14. Предположим, что некоторый агент находится в среде лабиринта 3x3, подобного приведенному на рис. 4.12. Агенту известно, что его первоначальным местонахождением является пункт (1,1), что цель находится в пункте (3,3) и что четыре действия, Up, Down, Left, Right, приводят к своим обычным последствиям, если не будут заблокированы стеной. Агент не знает о том, где находятся внутренние стены. В любом конкретном состоянии агент воспринимает информацию о множестве допустимых действий; он также может определить, является ли данное состояние тем, которое он уже посещал ранее, или представляет собой новое состояние.
а) Объясните, каким образом к этой задаче поиска в оперативном режиме
можно применить такую трактовку, чтобы она могла рассматриваться как
поиск в автономном режиме в пространстве доверительных состояний, где
первоначальное доверительное состояние включает все возможные кон-
фигурации среды. Насколько велико это первоначальное доверительное
состояние? Насколько велико все пространство доверительных состояний?
б) Какое количество различных вариантов восприятия возможно в первоначальном состоянии?
в) Опишите первые несколько ветвей плана действий в непредвиденных ситуациях для этой задачи. Насколько велик этот план в полном виде (дайте приблизительную оценку)?
Обратите внимание на то, что этот план действий в непредвиденных ситуациях является решением для каждой возможной среды, соответствующей данному описанию. Поэтому, строго говоря, чередование поиска и выполнения не требуется даже в неизвестных вариантах среды.
4.15. (И) В данном упражнении исследуется направление использования локальных методов поиска для решения задач TSP такого типа, который определен в упр. 4.8.
а) Предложите подход к решению задач TSP на основе поиска с восхождением к вершине. Сравните эти результаты с оптимальными решениями,
полученными на основе алгоритма А* с эвристической функцией MST (упр. 4.8).
б) Предложите подход к решению задачи коммивояжера с помощью генетического алгоритма. Сравните результаты обоих подходов. Для ознакомления с некоторыми рекомендациями по выбору представлений вы можете обратиться к [890].
4.16. (ё) Сформируйте большое количество экземпляров игры в восемь и задачи с восемью ферзями и найдите их решения (там, где это возможно) с помощью поиска с восхождением к вершине (в варианте подъема по самому крутому склону и в варианте поиска по первому наилучшему совпадению), поиска с восхождением к вершине с перезапуском случайным образом и поиска с эмуляцией отжига. Измерьте стоимость поиска и процентное соотношение решенных задач, а также нанесите эти данные на график наряду с данными об оптимальной стоимости решения. Прокомментируйте полученные вами результаты.
4.17. (ж) В данном упражнении исследуется применение поиска с восхождением к вершине в контексте робототехнической навигации, с использованием в качестве примера среды, показанной на рис. 3.14.
а) Повторите упр. 3.16 с использованием поиска с восхождением к вершине. Зашел ли когда-либо предложенный вами агент в тупик в локальном минимуме? Возможно ли, чтобы он зашел в тупик при наличии выпуклых препятствий?
б) Сформируйте среду с препятствиями в виде невыпуклых многоугольников, в которой агент может оказаться в тупике.
в) Модифицируйте алгоритм поиска с восхождением к вершине таким образом, чтобы вместо выполнения поиска на глубину 1 для принятия решения о том, куда двигаться дальше, агент предпринимал бы поиск на глубину к. Он должен находить наилучший путь, состоящий из к этапов,
проходить по нему на один этап, а затем повторять процесс.
г) Существует ли такое значение к, при котором новый алгоритм гарантирует выход из локальных минимумов?
д) Объясните, благодаря чему алгоритм LRTA* позволяет агенту выходить
из локальных минимумов в этом случае.
4.18. (И) Сравните производительность алгоритмов А* и RBFS на множестве случайно сформированных экземпляров задач в проблемных областях задачи игры в восемь (с манхэттенским расстоянием) и задачи TSP (с MST — см. упр. 4.8). Обсудите полученные вами результаты. Как изменяется производительность алгоритма RBFS после добавления небольшого случайного числа к эвристическим значениям в проблемной области задачи игры в восемь?