Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 37
Текст из файла (страница 37)
Предположим, что выражение т,еда1-дссйопэ(а) обозначает множество действий, которые являются допустимыми в состоянии в, а выражение певц1с (а, а) обозначает состояние, которое следует из выполнения допустимого действия а в состоянии а. Определите функцию Бпссеввог-Рп в терминах выражений г еда1-Ас сйопв и певп1с, и наоборот. 3.4. Покажите, что в задаче игры в восемь состояния подразделяются на два непересекающихся множества, таких, что ни одно состояние из первого множества не может быть преобразовано в состояние из второго множества, даже с применением сколь угодно большого количества ходов. (Подсказка. См. [102].) Разработайте процедуру, позволяющую узнать, к какому множеству относится данное состояние, и объясните, для чего нужно иметь под рукой такую процедуру, формируя состояния случайным образом, 3.5.
Рассмотрите задачу с п ферзями, используя "эффективную" инкрементную формулировку, приведенную на с. 119. Объясните, почему размер пространства состояний равен по меньшей мере Я, и оцените наибольшее значение и, для которого является осуществимым исчерпывающее исследование. (Подсказка.
Определите нижнюю границу коэффициента ветвления, рассматривая максимальное количество клеток, которые ферзь может атаковать в любом столбце.) 3.6. Всегда ли наличие конечного пространства состояний приводит к получению конечного дерева поиска? А что можно сказать о конечном пространстве состояний, которое является деревом? Можете ли вы указать более точно, применение пространств состояний каких типов всегда приводит к получению конечных деревьев поиска? (Адааглироваио из (99!.) 3.7. Укажите для каждой из следующих задач ее компоненты: начальное состояние, проверку цели, функцию определения преемника и функцию стоимости. Выберите формулировку, которая является достаточно ~очной, чтобы ее можно было успешно реализовать.
а) Необходимо раскрасить плоскую карту, используя только четыре цвета, таким образом, чтобы никакие два смежных региона не имели один и тот же цвет. 148 Часть П. Решение проблем б) Обезьяна, имеюшая рост 3 фута, находится в комнате, где под потолком, на высоте 8 футов, подвешено несколько бананов. Обезьяна хочет получить бананы. В комнате находятся две проволочные корзины высотой по 3 фута каждая, которые можно передвигать, ставить друг на друга и на которые можно залезать. в) Некоторая программа выводит сообшение "нелопустимая входная запись" после передачи ей некоторого файла, состоящего из входных записей. Известно, что обработка каждой записи происходит независимо от других записей.
Требуется обнаружить, какая запись является недопустимой. г) Имеются три кувшина, с емкостью 12 галлонов, 8 та шопов и 3 галлона, а также водопроводный кран. Кувшины можно заполнять или опорожнять, выливая воду из одного кувшина в другой или на землю. Необходимо отмерить ровно один галлон. 3.8. Рассмотрите пространство состояний, в котором начальным состоянием является число 1, а функция определения преемника для состояния п возврашает два состояния: числа 2п и 2п~1. а) Нарисуйте часть пространства состояний, которая относится к состояниям 1 — 15. б) Предположим, что целевым состоянием является 11.
Перечислите последовательности, в которых будут посещаться узлы при поиске в ширину, поиске с ограничением глубины, с пределом 3, и поиске с итеративным углублением. в) Будет ли подходящим для решения этой задачи двунаправленный поиск? Если да, то опишите подробно, как действовал бы этот метод поиска.
г) Каковым является коэффициент ветвления в каждом направлении двунаправленного поиска? д) Не подсказывает ли вам ответ на вопрос упр. 3.8, е, что нужно найти другую формулировку этой задачи, которая позволила бы решить проблему перехода из состояния 1 в заданное целевое состояние почти без поиска? 3.9. ~Й Задача с миссионерами и каннибалами обычно формулируется следуюшим образом. Три миссионера и три каннибала находятся на одной стороне реки, где также находится лодка, которая может выдержать одного или двух человек.
Найдите способ перевезти всех на другой берег реки, никогда не оставляя гделибо группу миссионеров, которую превосхолила бы по численности группа каннибалов. Это — известная задача в искусственном интеллекте, поскольку она бьша темой первой статьи, в которой был применен подход к формулировке проблемы с аналитической точки зрения ~24). а) Точно сформулируйте эту задачу, определяя только те различия, которые необходимы для обеспечения правильного решения. Нарисуйте схему полного пространства состояний.
б) Реализуйте и решите эту задачу оптимальным образом, используя соответствующий алгоритм поиска. Действительно ли имеет смысл проверять наличие повторяющихся состояний? в) Почему, по вашему мнению, люди сталкиваются с затруднениями при решении этой головоломки, несмотря на то, что пространство ее состояний является чрезвычайно простым? Глава 3.
Решение проблем посредством поиска 149 3.10. 3.11. 3.12. 3.13. ЗЛ4. 3.15. Й) Реализуйте следующие две версии функции определения преемника для задачи игры в восемь. Первая из них должна формировать сразу всех преемников, копируя и редактируя структуру данных игры в восемь, а вторая при каждом ее вызове должна формировать по одному новому преемнику и действовать по принципу непосредственной модификации родительского состояния (отменяя эти модификации в случае необходимости). Напишите версии процедуры поиска в глубину с итеративным углублением, в которых используются эти функции, и сравните данные об их производительности.
Ф На с. ! 35 упоминался поиск с итеративным удлинением, итеративный аналог поиска по критерию стоимости. Его идея состоит в том, что должны использоваться увеличивающиеся пределы стоимости пути. Если сформирован узел, стоимость пути для которого превышает текущий предел, этот узел немедленно отбрасывается. При каждой новой итерации предел устанавливается равным самому низкому значению стоимости пути для любого узла, отвергнутого в предыдушей итерации. а) Покажите, что этот алгоритм является оптимальным применительно к обшим методам определения стоимости пути.
б) Рассмотрите однородное дерево с коэффициентом ветвления Ь, глубиной решения сг и единичными стоимостями этапов. Какое количество итераций требуется при итеративном удлинении? в) Рассмотрите стоимости этапов, взятые из непрерывного диапазона [ О, 1] с минимальной положительной стоимостью е. Сколько итераций потребуется в самом неблагоприятном случае? г) Реализуйте этот алгоритм и примените его к экземплярам задачи игры в восемь и задачи коммивояжера. Сравните производительность этого алгоритма с производительностью алгоритма поиска по критерию стоимости и прокомментируйте полученные результаты. Докажите, что поиск по критерию стоимости и поиск в ширину с постоянными значениями стоимости этапа являются оптимальными при их использовании с алгоритмом СгарЬ-ЯеахоЬ.
Продемонстрируйте такое пространство состояний с постоянными значениями стоимости этапа, в котором алгоритм СхарЬ-БеатсЬ с использованием итеративного углубления находит неоптимальное решение. Опишите пространство состояний, в котором поиск с итеративным углублением характеризуется гораздо более низкой производительностью по сравнению с поиском в глубину (например, о (и'), в отличие от 0 (и) ). йз Напишите программу, которая принимает в качестве входных данных ()%- локаторы двух %еЬ-страниц и находит путь от одной к другой, состояший из ссылок. В чем состоит подходяшая для этого стратегия поиска? Действительно ли имеет смысл применять двунаправленный поиск? Можно ли использовать для реализации функции определения предшественника машину поиска? ей Рассмотрите задачу определения кратчайшего пути между двумя точками на плоскости, на которой имеются препятствия в виде выпуклых многоугольников, как показано на рис.
3.14. Это — идеализация задачи, которую должен Часть 11. Решение проблем 150 решать робот, прокладывая свой путь через среду, в которой очень мало свободного места. Рис. 3. 14. Сцена с многоугояьными препятствиями а) Предположим, что пространство состояний состоит из всех позиций (х, у) на плоскости. Каково количество состояний в этом пространстве? Каково в нем количество путей к цели? б) Объясните в нескольких словах, почему в этой двухмерной сцене кратчайший путь от одной вершины многоугольника до любой другой должен состоять из прямолинейных отрезков, соединяющих некоторые вершины многоугольников. Теперь определите более приемлемое пространство состояний.
Насколько велико это пространство состояний? в) Определите функции, необходимые для реализации решения этой задачи поиска, включая функцию определения преемника, которая принимает в качестве входных данных координаты любой из вершин и возвращает множество вершин, достижимых по прямой линии от данной вершины. (Не забывайте при этом о соседних вершинах того же многоугольника.) Используйте в качестве значения эвристической функции расстояние между указанными точками по прямой. г) Примените для решения ряда задач из этой области один или несколько алгоритмов, представленных в настоящей главе„и прокомментируйте данные об их производительности.
3.16. Ф Определение задачи обеспечения навигации робота, приведенной в упр. 3.15, можно преобразовать в определение среды следующим образом. ° Акт восприятия будет представлять собой список позиций видимых вершин, сформированный относительно агента. Акт восприятия не предусматривает определение позиции робота! Робот должен определять свою собственную позицию по карте; на данный момент можно предположить, что каждое местоположение имеет другое "представление". ° Каждое действие должно быть вектором, описывающим прямолинейный путь, по которому будет следовать робот.
Если путь свободен, то действие выполняется успешно; в противном случае робот останавливается в той точке, Глава 3. Решение проблем посредством поиска 151 где его путь впервые сталкивается с препятствием. Если агент возвращает нулевой вектор движений и находится в целевой позиции (которая является постоянной и известной), то среда должна телепортировать этого агента в случайно выбранное местоположение (не находягдееся в пределах препятствия). ° Показатель производительности прелусматривает штрафование агента на 1 пункт за каждую единицу пройденного расстояния и награждение его 1000 пунктами каждый раз после достижения цели.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
