Hierarchia heurystyczna *: Najkrótsza ścieżka przechodząca raz w wielu punktach.

Question

Próbuję wymyślić dobrą i szybką heurystykę dla gry pacman z wyraźną mapą.

Moja heurystyka próbuje obliczyć najmniejszą możliwą odległość, jaką pacman musi podróżować, aby przejść do każdego punktu z jedzeniem na mapie. Mój obecny algorytm to podstawowy MST dla Prim, który daje mi czas działania O (n logn), ale nie uwzględnia sytuacji, w których pacman musi podążać za krawędzią do zjedzenia, a powrót do poprzedniego wierzchołka ...

Czy jest coś lepszego?

Mówiąc w inny sposób: Jaki jest minimalny koszt połączenia kilku kropek bez podnoszenia pióra?

Dzięki

Answer 1

Po uruchomieniu algorytmu, par-najkrótszej ścieżki i określenie wierzchołków z jedzeniem, staje się traveling salesman problem. Nie można go rozwiązać skutecznie, ale można konstruować dowolnie dobre przybliżenia rozwiązania w czasie wielomianowym. Prawdopodobnie będziesz chciał użyć przybliżenia, chyba że możesz wstępnie obliczyć wszystko. Jeśli możesz wstępnie obliczyć rzeczy (lub w inny sposób zagwarantować, że masz wystarczająco dużo czasu, aby znaleźć dokładne rozwiązanie), po znalezieniu najkrótszych ścieżek wszystkich par, możesz po prostu znaleźć minimalną całkowitą długość spaceru nad wszystkimi możliwymi permutacje porządku, w którym jesz kawałki jedzenia. Ta metoda brutalnej siły może zostać nieco poprawiona, gdy patrzy się, kiedy najkrótsza droga między dwoma kawałkami jedzenia przechodzi przez inny kawałek jedzenia.