Vous avez une carte de carreaux carrés où vous pouvez vous déplacer dans l'une des 8 directions. Étant donné que vous avez une fonction appelée coût (carreaux1, carreaux2) qui vous indique le coût de passer d'une tuile adjacente à une autre, comment trouvez-vous une fonction heuristique H (y, but) qui est à la fois admissible et cohérent? Une méthode de recherche de l'heuristique peut-elle être généralisée compte tenu de ce paramètre ou de varier différemment en fonction de la fonction ?
3 Réponses :
Le tutoriel d'Amit est l'un des meilleurs que j'ai vus sur un * ( Page d'Amit) . Vous devriez trouver un indice très utile sur les heuristiques sur cette page.
Voici la citation sur votre problème:
sur une grille carrée qui permet 8 directions de mouvement, utilisez la distance diagonale (L∞).
Cela dépend toujours de votre fonction de coût pour passer à un carré adjacent.
Cela dépend de la fonction de coût.
Il y a quelques heuristiques communes, telles que Distance Euclidean (la distance absolue entre deux tuiles sur un avion 2D) et Distance Manhattan (la somme des Deltas absolus x et y). Mais ceux-ci supposent que le coût réel n'est jamais inférieur à une certaine quantité. La distance de Manhattan est exclue si votre agent peut se déplacer efficacement en diagonale (c'est-à-dire que le coût de la déménagement à une diagonale est inférieur à 2). La distance euclidienne est exclue si le coût de déménagement dans une tuile voisine est inférieur à la distance absolue de ce mouvement (par exemple, si la tuile adjacente était "en descente" de celle-ci).
Quelle que soit votre fonction de coût, vous avez toujours une heuristique admissible et cohérente dans h (t1, t2) = -∞ . Ce n'est tout simplement pas un bon.
Oui, l'heuristique dépend de la fonction de coût, à quelques égards. Tout d'abord, il doit être dans les mêmes unités. Deuxièmement, vous ne pouvez pas avoir un chemin de coût inférieur à travers des nœuds réels que le coût de la heuristique.
Dans le monde réel, utilisé pour des choses telles que la navigation sur un réseau routier, votre heuristique pourrait être "l'heure d'une voiture prendrait sur un chemin direct à 1,5 fois la limite de vitesse". Le coût de chaque segment de route utiliserait la limite de vitesse réelle, ce qui donnera un coût plus élevé.
Alors, quelle est votre fonction de coût entre les tuiles? Est-ce basé sur des propriétés physiques ou définies en dehors de votre graphique?
Une meilleure heuristique est «le temps qu'une voiture prendrait s'il y avait une autoroute (route avec la limite de vitesse la plus élevée) en ligne droite jusqu'à la destination». Il n'est pas nécessaire d'appliquer le facteur de 1,5.