УПРАЖНЕНИЯ

3.1. Самостоятельно сформулируйте определения следующих понятий: состояние, пространство состояний, дерево поиска, поисковый узел, цель, действие, функция определения преемника и коэффициент ветвления.
3.2. Объясните, почему составление формулировки задачи должно осуществляться вслед за составлением формулировки цели.
3.3. Предположим, что выражение Legal-Actions (s) обозначает множество действий, которые являются допустимыми в состоянии s, а выражение Result (a, s) обозначает состояние, которое следует из выполнения допустимого действия а в состоянии s. Определите функцию Successor-Fn в терминах выражений Legal-Actions и Result, и наоборот.
3.4. Покажите, что в задаче игры в восемь состояния подразделяются на два непересекающихся множества, таких, что ни одно состояние из первого множества не может быть преобразовано в состояние из второго множества, даже с применением сколь угодно большого количества ходов. {Подсказка. См. [102].) Разработайте процедуру, позволяющую узнать, к какому множеству относится данное состояние, и объясните, для чего нужно иметь под рукой такую процедуру, формируя состояния случайным образом.
3.5. Рассмотрите задачу с п ферзями, используя "эффективную" инкрементную формулировку, приведенную на с. 119. Объясните, почему размер пространства состояний равен по меньшей мере Ifc, и оцените наибольшее значение л, для которого является осуществимым исчерпывающее исследование. {Подсказка. Определите нижнюю границу коэффициента ветвления, рассматривая максимальное количество клеток, которые ферзь может атаковать в любом столбце.)
3.6. Всегда ли наличие конечного пространства состояний приводит к получению конечного дерева поиска? А что можно сказать о конечном пространстве состояний, которое является деревом? Можете ли вы указать более точно, применение пространств состояний каких типов всегда приводит к получению конечных деревьев поиска? {Адаптировано из [99].)
3.7. Укажите для каждой из следующих задач ее компоненты: начальное состояние, проверку цели, функцию определения преемника и функцию стоимости. Выберите формулировку, которая является достаточно точной, чтобы ее можно было успешно реализовать.
а) Необходимо раскрасить плоскую карту, используя только четыре цвета, таким образом, чтобы никакие два смежных региона не имели один и тот же цвет.
б) Обезьяна, имеющая рост 3 фута, находится в комнате, где под потолком,
на высоте 8 футов, подвешено несколько бананов. Обезьяна хочет полу-
чить бананы. В комнате находятся две проволочные корзины высотой по
3 фута каждая, которые можно передвигать, ставить друг на друга и на ко-
торые можно залезать.
в) Некоторая программа выводит сообщение "недопустимая входная запись"
после передачи ей некоторого файла, состоящего из входных записей. Из-
вестно, что обработка каждой записи происходит независимо от других за-
писей. Требуется обнаружить, какая запись является недопустимой.
г) Имеются три кувшина, с емкостью 12 галлонов, 8 галлонов и 3 галлона,
а также водопроводный кран. Кувшины можно заполнять или опорож-
нять, выливая воду из одного кувшина в другой или на землю. Необходи-
мо отмерить ровно один галлон.
3.8. Рассмотрите пространство состояний, в котором начальным состоянием яв-
ляется число 1, а функция определения преемника для состояния п возвраща-
ет два состояния: числа 2п и 2п+1.
а) Нарисуйте часть пространства состояний, которая относится к состояни-
ям 1-15.
б) Предположим, что целевым состоянием является 11. Перечислите последо-
вательности, в которых будут посещаться узлы при поиске в ширину, поиске
с ограничением глубины, с пределом 3, и поиске с итеративным углублением.
в) Будет ли подходящим для решения этой задачи двунаправленный поиск?
Если да, то опишите подробно, как действовал бы этот метод поиска.
г) Каковым является коэффициент ветвления в каждом направлении дву-
направленного поиска?
д) Не подсказывает ли вам ответ на вопрос упр. 3.8, что нужно найти дру-
гую формулировку этой задачи, которая позволила бы решить проблему
перехода из состояния 1 в заданное целевое состояние почти без поиска?
3.9. ЙЁ) Задача с миссионерами и каннибалами обычно формулируется следующим
образом. Три миссионера и три каннибала находятся на одной стороне реки,
где также находится лодка, которая может выдержать одного или двух человек.
Найдите способ перевезти всех на другой берег реки, никогда не оставляя где-
либо группу миссионеров, которую превосходила бы по численности группа
каннибалов. Это — известная задача в искусственном интеллекте, поскольку
она была темой первой статьи, в которой был применен подход к формули-
ровке проблемы с аналитической точки зрения [24].
а) Точно сформулируйте эту задачу, определяя только те различия, которые
необходимы для обеспечения правильного решения. Нарисуйте схему
полного пространства состояний.
б) Реализуйте и решите эту задачу оптимальным образом, используя соот-
ветствующий алгоритм поиска. Действительно ли имеет смысл проверять
наличие повторяющихся состояний?
в) Почему, по вашему мнению, люди сталкиваются с затруднениями при
решении этой головоломки, несмотря на то, что пространство ее состоя-
ний является чрезвычайно простым?
3.10. dfe Реализуйте следующие две версии функции определения преемника для задачи игры в восемь. Первая из них должна формировать сразу всех преемников, копируя и редактируя структуру данных игры в восемь, а вторая при каждом ее вызове должна формировать по одному новому преемнику и действовать по принципу непосредственной модификации родительского состояния (отменяя эти модификации в случае необходимости). Напишите версии процедуры поиска в глубину с итеративным углублением, в которых используются эти функции, и сравните данные об их производительности.
3.11. dfe На с. 135 упоминался поиск с итеративным удлинением, итеративный аналог поиска по критерию стоимости. Его идея состоит в том, что должны использоваться увеличивающиеся пределы стоимости пути. Если сформирован узел, стоимость пути для которого превышает текущий предел, этот узел немедленно отбрасывается. При каждой новой итерации предел устанавливается равным самому низкому значению стоимости пути для любого узла, отвергнутого в предыдущей итерации.
а) Покажите, что этот алгоритм является оптимальным применительно к
общим методам определения стоимости пути.
б) Рассмотрите однородное дерево с коэффициентом ветвления Ь, глубиной
решения d и единичными стоимостями этапов. Какое количество итера-
ций требуется при итеративном удлинении?
в) Рассмотрите стоимости этапов, взятые из непрерывного диапазона
[0,1] с минимальной положительной стоимостью 8. Сколько итераций
потребуется в самом неблагоприятном случае?
г) Реализуйте этот алгоритм и примените его к экземплярам задачи игры в
восемь и задачи коммивояжера. Сравните производительность этого ал-
горитма с производительностью алгоритма поиска по критерию стоимо-
сти и прокомментируйте полученные результаты.
3.12. Докажите, что поиск по критерию стоимости и поиск в ширину с постоянными значениями стоимости этапа являются оптимальными при их использовании с алгоритмом Graph-Search. Продемонстрируйте такое пространство состояний с постоянными значениями стоимости этапа, в котором алгоритм Graph-Search с использованием итеративного углубления находит неоптимальное решение.
3.13. Опишите пространство состояний, в котором поиск с итеративным углублением характеризуется гораздо более низкой производительностью по сравнению с поиском в глубину (например, О(п2), в отличие от О(п)).
3.14. 1ж) Напишите программу, которая принимает в качестве входных данных URL-локаторы двух Web-страниц и находит путь от одной к другой, состоящий из ссылок. В чем состоит подходящая для этого стратегия поиска? Действительно ли имеет смысл применять двунаправленный поиск? Можно ли использовать для реализации функции определения предшественника машину поиска?
3.15. dfe Рассмотрите задачу определения кратчайшего пути между двумя точками на плоскости, на которой имеются препятствия в виде выпуклых многоугольников, как показано на рис. 3.14. Это — идеализация задачи, которую должен решать робот, прокладывая свой путь через среду, в которой очень мало свободного места.
а) Предположим, что пространство состояний состоит из всех позиций
(х,у) на плоскости. Каково количество состояний в этом пространстве?
Каково в нем количество путей к цели?
б) Объясните в нескольких словах, почему в этой двухмерной сцене
кратчайший путь от одной вершины многоугольника до любой другой
должен состоять из прямолинейных отрезков, соединяющих некоторые
вершины многоугольников. Теперь определите более приемлемое про-
странство состояний. Насколько велико это пространство состояний?
в) Определите функции, необходимые для реализации решения этой задачи
поиска, включая функцию определения преемника, которая принимает в
качестве входных данных координаты любой из вершин и возвращает
множество вершин, достижимых по прямой линии от данной вершины.
(Не забывайте при этом о соседних вершинах того же многоугольника.)
Используйте в качестве значения эвристической функции расстояние
между указанными точками по прямой,
г) Примените для решения ряда задач из этой области один или несколько
алгоритмов, представленных в настоящей главе, и прокомментируйте
данные об их производительности.
3.16. Определение задачи обеспечения навигации робота, приведенной в упр. 3.15, можно преобразовать в определение среды следующим образом.
• Акт восприятия будет представлять собой список позиций видимых вершин, сформированный относительно агента. Акт восприятия не предусматривает определение позиции робота! Робот должен определять свою собственную позицию по карте; на данный момент можно предположить, что каждое местоположение имеет другое "представление".
• Каждое действие должно быть вектором, описывающим прямолинейный путь, по которому будет следовать робот. Если путь свободен, то действие выполняется успешно; в противном случае робот останавливается в той точке, где его путь впервые сталкивается с препятствием. Если агент возвращает нулевой вектор движений и находится в целевой позиции (которая является постоянной и известной), то среда должна телепортировать этого агента в случайно выбранное местоположение (не находящееся в пределах препятствия). • Показатель производительности предусматривает штрафование агента на 1 пункт за каждую единицу пройденного расстояния и награждение его 1000 пунктами каждый раз после достижения цели. Ниже перечислены предлагаемые задания.
а) Реализуйте описанную среду и агента, решающего задачи для этой среды.
После каждой телепортации агент должен будет сформулировать новую
задачу, которая предусматривает также определение его текущего место-
положения.
б) Зарегистрируйте данные о производительности предложенного вами
агента (для этого предусмотрите выработку агентом соответствующих
комментариев по мере его передвижения в среде) и составьте отчет о его
производительности поданным, охватывающим больше 100 эпизодов.
в) Модифицируйте среду так, чтобы в 30% случаев движение агента закан-
чивались в не предусмотренном им месте назначения (выбранном слу-
чайным образом среди других видимых вершин, если таковые имеются,
а в противном случае соответствующем ситуации, в которой вообще не
было выполнено никакого движения). Это — грубая модель ошибок при
выполнении движений реального робота. Доработайте определение аген-
та так, чтобы при обнаружении указанной ошибки он определял, где на-
ходится, а затем создавал план возвращения в то место, где он находился
прежде, и возобновлял выполнение прежнего плана. Помните, что ино-
гда попытка возвращения в прежнее место также может оканчиваться не-
удачей! Продемонстрируйте пример агента, который успешно преодоле-
вает две последовательные ошибки движения и все равно достигает цели.
г) Опробуйте две различные схемы возобновления работы после ошибки: во-
первых, отправиться к ближайшей вершине из первоначального маршрута
и, во-вторых, перепланировать маршрут к цели от нового местоположения.
Сравните производительность всех схем возобновления работы. Влияет ли
на результаты такого сравнения включение затрат на поиск?
д) Теперь предположим, что есть такие местоположения, представления
среды из которых являются идентичными. (Например, предположим, что
мир — это решетка с квадратными препятствиями.) С какой проблемой
теперь сталкивается агент? Как должны выглядеть решения?
3.17. На с. 115 было указано, что мы не будем принимать во внимание задачи с отрицательными значениями стоимости пути. В данном упражнении эта тема рассматривается немного более подробно.
а) Предположим, что действия могут иметь произвольно большие отрицатель-
ные стоимости; объясните, почему такая ситуация может вынудить любой
оптимальный алгоритм исследовать полное пространство состояний.
б) Удастся ли выйти из этого положения, потребовав, чтобы стоимости эта-
пов были больше или равны некоторой отрицательной константе с? Рас-
смотрите и деревья, и графы.
в) Предположим, что имеется множество операторов, образующих цикл, так
что выполнение операторов этого множества в определенном порядке не
приводит к какому-либо чистому изменению состояния. Если все эти
операторы имеют отрицательную стоимость, то какие выводы из этого
следуют применительно к оптимальному поведению агента в такой среде?
г) Можно легко представить себе, что операторы с высокой отрицательной
стоимостью имеются даже в таких проблемных областях, как поиск мар-
шрута. Например, некоторые участки дороги могут оказаться настолько
живописными, что стремление ознакомиться с ними намного перевесит
обычные здравые рассуждения о стоимости, измеряемой в терминах затрат
времени и топлива. Объясните, применяя точные термины, принятые в
контексте поиска в пространстве состояний, почему все же люди не ведут
свои автомобили неопределенно долго по живописным циклическим уча-
сткам пути, и укажите, каким образом нужно определить пространство со-
стояний и операторы для задачи поиска маршрута, чтобы агенты с искусст-
венным интеллектом также могли избежать попадания в цикл.
д) Можете ли вы придумать пример такой реальной проблемной области, в
которой стоимости этапов таковы, что могут вызвать возникновение
цикла?
3.18. Рассмотрим мир пылесоса без датчиков, с двумя местоположениями, подчиняющийся закону Мэрфи. Нарисуйте пространство доверительных состояний, достижимых из начального доверительного состояния {1,2,3,4,5,6,7,8}, и объясните, почему эта задача неразрешима. Покажите также, что если бы этот мир был полностью наблюдаемым, то существовала бы последовательность решения для каждого возможного начального состояния.
3.19. Ш Рассмотрим задачу в мире пылесоса, который определен на рис. 2.2.
а) Какой из алгоритмов, определенных в этой главе, был бы подходящим
для решения этой задачи? Должен ли этот алгоритм проверять наличие
повторяющихся состояний?
б) Примените выбранный вами алгоритм для вычисления оптимальной после-
довательности действий в мире с размером 3x3, в начальном состоянии кото-
рого в трех верхних квадратах имеется мусор, а агент находится в центре.
в) Сконструируйте агента, выполняющего поиск в этом мире пылесоса, и оце-
ните его работу в множестве миров с размером 3x3, характеризующемся ве-
роятностью наличия мусора в каждом квадрате, равной 0.2. Включите в со-
став показателя производительности не только стоимость поиска, но и стои-
мость пути, используя для них подходящий "курс обмена".
г) Сравните вашего лучшего поискового агента с простым рандомизированным
рефлексным агентом, который всасывает мусор, если последний имеется,
а в противном случае выполняет случайно выбранные перемещения.
д) Рассмотрите, что произошло бы, если ли бы мир расширился до размеров
пхп. Как производительность данного поискового агента и рефлексного
агента зависит от л?







Материалы

Яндекс.Метрика