choix d'une* fonction heuristique

Question

J'essaie toujours de comprendre comment et pourquoi mes choix heuristiques affectent le temps de recherche de mon implémentation a*.

Ma carte est la suivante (taille non exacte) :

###########
#         #
# # # # # #
#         #
# # # # # #
#         #

J'ai choisi mes heuristiques comme

option 1: h = abs(n.x - target.x) + abs(n.y - target.y)
option 2: h = 2*(abs(n.x- target.x) + abs(n.y - target.y))

avec option 1 L'algorithme fonctionne relativement bien jusqu'à ce que je doive me déplacer de haut en bas, et dans ce cas, il met longtemps à trouver le chemin.

avec option 2 le option 1 est amélioré d'environ 90 %.

J'ai essayé de me documenter sur la surestimation et la sous-estimation, mais je n'ai pas trouvé d'explication claire.

Quelle pourrait en être la raison ? également, mes choix sont-ils raisonnables ?

Answer 1

Jetez un coup d'œil à ce réponse. Il existe une lien à un tutoriel sympa qui explique et donne règles d'or sur les heuristiques à choisir pour différents types de problèmes, suivi d'une explication conviviale de ces techniques.