1
La définition d'une heuristique admissible est celle qui "ne surestime pas le chemin d'un but particulier". J'essaye d'écrire une heuristique Pac-Man pour trouver la méthode la plus rapide pour manger des points, dont certains sont dispersés aléatoirement dans la grille. Cependant, il échoue mon test d'admissibilité. Voici les étapes de mon algorithme:Comment puis-je savoir si une heuristique particulière est admissible et pourquoi la mienne ne l'est pas?
sum = 0, list = grid.getListofDots()
1. Find nearest dot from starting position (or previous dot that was removed) using manhattan distance
2. add to sum
3. Remove dot from list of possible dots
4. repeat steps 1 - 3 until list is empty
5. return the sum
Depuis que je suis en utilisant la distance manhattan, ne devrait pas être recevable ce? Si non, y a-t-il des suggestions ou d'autres approches pour rendre cet algorithme admissible?
vous considérer la distance de l'endroit où vous êtes, mais les changements en mouvement toutes les distances. – njzk2
Mais si j'utilise la distance de manhattan du point que je viens d'atteindre, est-ce que cela ne signifie pas que c'est toujours recevable? – Quinty
vous considérez quelques distances deux fois. considérez ceci: '* ___ * C_ *' (il y a 3 espaces). Pacman est 'C',' *' sont les points, '_' est un espace vide. votre algorithme compte 11. (gauche, droite, gauche). Le meilleur rapport qualité/prix est 9 (allez à droite en premier). – njzk2