A * эвристика: кратчайший путь, проходящий один раз в нескольких точках

Question

Я пытаюсь найти хорошую и быструю эвристику для игры pacman с ясной картой.

Моя эвристика пытается рассчитать наименьшее возможное расстояние, которое должен пройти пакман, чтобы пройти к каждой точке с едой на карте. Мой текущий алгоритм - это, по сути, MST Prim, который дает мне время выполнения O (n logn), но не учитывает ситуации, когда pacman должен следовать за ребром и возвращаться к предыдущей вершине ...

Есть что-нибудь лучше?

Говоря по-другому: какова минимальная стоимость соединения нескольких точек без подъема пера?

Спасибо

Answer 1

После запуска алгоритма поиска всех пар по кратчайшему пути и определения вершин с едой это становится проблемой коммивояжера . Вы не можете решить это эффективно, но вы можете построить сколь угодно хорошие приближения к решению за полиномиальное время. Возможно, вы захотите использовать приближение, если вы не можете предварительно вычислить все. Если вы можете предварительно вычислить вещи (или иным образом гарантировать, что у вас есть достаточно времени, чтобы найти точное решение), то, получив все пары всех кратчайших путей, вы можете просто найти минимальную общую длину пути по всем возможным Перестановки порядка, в котором вы едите кусочки пищи. Этот метод грубой силы, вероятно, можно несколько улучшить, следя за тем, чтобы кратчайший путь между двумя кусочками пищи пересекался с другим кусочком еды.