3. Поедая все гранулы

Теперь решим трудно решаемую задачу поиска – задачу поедания Пакманом всей еды за минимальное количество шагов. Для этого нам потребуется новая постановка задачи поиска, которая формализует проблему «зачистки уровня от еды»: FoodSearchProblem в листинге searchAgents.py (уже реализовано за вас).

Решение данной задачи определяется как путь, который проходит через все объекты еды в мире (лабиринте) Пакмана. Для текущего проекта, решение не принимает во внимание встречу с призраками или эффекты особых гранул; решение зависит лишь от расположения стен, обычной еды и Пакмана. (Конечно же, призраки могут испортить исполнение найденного пути). Если вы реализовали ваш метод общего поиска корректно, то A* с нулевой эвристикой (что эквивалентно поиску по критерию стоимости) должен быстро найти оптимальное решения для лабиринта testSearch без каких либо изменений в коде с вашей стороны (общая стоимость такого пути равна 7).

python pacman.py -l testSearch -p AStarFoodSearchAgent

Примечание: AStarFoodSearchAgent – сокращение для опций -p SearchAgent -a fn=astar, prob=FoodSearchProblem,heuristic=foodHeuristic.

Вы должны заметить, что поиск по критерию стоимости начинает замедляться даже для такого, простого на первый взгляд, лабиринта как tinySearch. Для примера, наша реализация вычисляла путь длиной 27 в течение 2.5 секунд, раскрыв 5057 узлов.

3.1. Задание № 7: поедая все гранулы – а* и эвристика (4 балла)

Внимание: Убедитесь, что вы завершили задание №4, прежде чем приступать к заданию №7, поскольку задание №7 основывается на результатах работы над заданием №4.

Заполните foodHeuristic в searchAgents.py монотонной эвристикой для задачи FoodSearchProblem. Испытайте разработанного агента на поле trickySearch:

python pacman.py -l trickySearch -p AStarFoodSearchAgent

Наш агент на основе поиска по критерию стоимости находит оптимальное решение примерно за 13 секунд, исследуя при этом более 16000 узлов.

Любая нетривиальная неотрицательная монотонная эвристика обеспечит вам 1 балл. Дополнительные баллы начисляются в зависимости от количества развернутых узлов:

Число раскрытых узлов	Оценка
более 15 000	1/4
не более 15 000	2/4
не более 12 000	3/4
не более 9 000	4/4 (полные баллы; средняя сложность)
не более 7 000	5/4 (экстра балл; сложно)

Помните: Если ваша эвристика немонотонна, то вы получите 0 баллов, будьте внимательны! Если вы можете решить лабиринт mediumSearch за короткое время, то либо мы будем сильно впечатлены, либо ваша эвристическая функция немонотонна.

3.2. Задание № 8: субоптимальный поиск (2 балла)

Иногда, даже при использовании А* с хорошей эвристикой, найти оптимальный путь через все точки может быть трудным. В таких случаях, все же хотелось бы найти, если не оптимальный, то достаточно хороший путь, и сделать это быстро. В данном разделе вам предстоит написать агента, который всегда жадно ест ближайшую точку. ClosestDotSearchAgent уже реализовано за вас в searchAgents.py, но в реализации не хватает ключевой функции, которая находит путь до ближайшей точки.

Реализуйте функцию findPathToClosestDot в searchAgents.py. Наш агент решает данный лабиринт (субоптимально!) менее чем за секунду и со стоимостью пути равной 350:

python pacman.py -l bigSearch -p ClosestDotSearchAgent -z .5

Подсказка: Самый быстрый способ реализовать findPathToClosestDot – использовать код AnyFoodSearchProblem, в котором не хватает проверки цели. А затем использовать соответствующую функцию поиска. Решение должно быть очень коротким!

Ваш агент ClosestDotSearchAgent не всегда будет находить самый короткий из возможных путей через лабиринт. Убедитесь, что вы понимаете, почему так происходит. Постарайтесь привести простой пример, в котором результатом стратегии «идти к ближайшей точке» является не самый короткий путь для поедания всех точек.