A * heuristique: le plus court chemin passant une fois en plusieurs points

Question

J'essaie de trouver une heuristique bonne et rapide pour un jeu pacman de clear-map. Mon heuristique essaye de calculer la plus petite distance possible que le pacman doit voyager pour aller à tous les points avec de la nourriture sur la carte. Mon algorithme actuel est fondamentalement MST de Prim qui me donne un O (n logn) temps de fonctionnement, mais ne compte pas les situations où le pacman doit suivre un bord à manger, et le retour au sommet précédent ...

Y a-t-il quelque chose de mieux? Dire d'une autre manière: Quel est le coût minimum de connexion de plusieurs points sans soulever mon stylo?

Merci

Answer 1

Après avoir exécuté un algorithme toutes les paires-chemin le plus court et en identifiant les sommets avec de la nourriture, cela devient la traveling salesman problem. Vous ne pouvez pas le résoudre efficacement, mais vous pouvez construire arbitrairement de bonnes approximations d'une solution en temps polynomial. Vous voudrez probablement utiliser une approximation, sauf si vous pouvez pré-calculer tout. Si vous pouvez pré-calculer des choses (ou garantir que vous avez assez de temps pour trouver une solution exacte), alors une fois que vous avez les chemins all-pairs-plus-courts, vous pouvez simplement trouver la longueur totale minimale de marche permutations de l'ordre dans lequel vous mangez les morceaux de nourriture. Cette méthode de force brute peut probablement être améliorée en faisant attention lorsque le chemin le plus court entre deux morceaux de nourriture traverse un autre morceau de nourriture.