В рамках проекта я пытаюсь реализовать A * в контексте игры pacman (см. Проект UC Berkley pacman ai). Там нет призраков или капсул, только лабиринт и «фрукты». Однако у меня возникают проблемы с пониманием взаимосвязи между моей эвристической функцией и моей функцией стоимости.
В соответствии с проектом, при определении проблемы поиска нам необходимо указать стоимость шага, которая получается из: score = -Nb Steps + 10*NbOfEatenDots + 200*NbOfEatenGhosts + (-500*isLoss) + (500*isWin)Предполагается, что эта стоимость всегда будет положительной, поэтому для простоты я решил взять: 1.5 - (0.5*AteAFoodDot). Я проигнорировал призраков и капсулы, так как их не существует, и я дал преференциальный счет за ходы, которые в конечном итоге съедают точку. Я также проигнорировал шаги, которые приводят к потере (так как они не существуют) и шаги, которые приводят к выигрышному состоянию.
Теперь, что касается самого алгоритма A *, мы должны реализовать стоимостьфункция и наша эвристическая функция:
В качестве функции стоимости я выбрал: Cost = sum(step costs to current state) и в качестве эвристики: h = Manhattan distance between pacman and the dot closest to him + manhattan distance of this dot and another dot that is furthest away from it, as long as it exists, что является допустимой эвристикой. Я также реализовал эту эвристику, используя реальные лабиринтные расстояния вместо манхэттенских, но это казалось слишком трудоемким для лабиринтов с множеством точек питания.
Теперь, если я правильно понял, является ли g(n) моей функцией стоимости и h(n) моя эвристика, у меня всегда должно быть: g(n to goal) >= h(n), чтобы A * всегда возвращал оптимальный путь, и чем ближе значения g и h для узла n, тем меньше узлов будет раскрыто.
В этом отношении не в моих интересах игнорировать то, как вычисляется счет, игнорировать тот факт, что шаг приводит к употреблению пищевой точки или нет, и просто брать step_cost = 1 для всех шагов?
Так я получаю наилучшие результаты в отношении времени вычислений и расширенных узлов, но игнорирование функции стоимости в игре кажется неправильным.
Может кто-нибудь уточнить это для меня? Это вопрос отношения / выбора или существует объективный правильный ответ / лучший подход?