La distance de Manhattan est-elle monotone lorsqu'elle est utilisée comme fonction heuristique?

25

J'ai une carte carrée. Seuls les mouvements horizontaux et verticaux sont autorisés (pas de diagonales). Le coût de déplacement est toujours de 1.

J'implémente un algorithme A * sur cette carte, en utilisant la distance de Manhattan comme heuristique de distance. Cette heuristique est-elle cohérente? Puis-je éviter de vérifier les g(node)nœuds qui se trouvent dans l'ensemble FERMÉ?

Edit: Par cohérent, je veux dire monotone.

tiles path-finding geometry Emiliano
la source
1
Si votre coût de déplacement est uniforme sur chaque tuile, vous pouvez remplacer A * par Jump Point Search
Nick Caplinger
Hé, c'est bien!
Emiliano

Réponses:

10

Pour répondre à votre question: la distance de Manhatten est cohérente lorsque vous êtes contraint de vous déplacer verticalement / horizontalement le long d'une grille non pondérée (cela peut être facilement montré par la définition sur wikipedia) . Alors oui, dans votre cas, vous pouvez éviter de revérifier les nœuds dans l'ensemble fermé.

Cependant, une fois que vous autorisez le mouvement en diagonale ou dans n'importe quel angle, la distance brisée devient inadmissible car elle surestime les coûts diagonaux, ce qui signifie nécessairement qu'elle n'est pas cohérente.

BlueRaja - Danny Pflughoeft
la source
Oui, c'est exactement le genre de réponse que je cherchais. Ce serait bien de savoir ce qui se passe si la fonction heuristique est h(x) = min(manhattan(p1), manhattan(p2))(c'est-à-dire que p1 ou p2 sont un bon point de fin et que je veux atteindre le plus proche). Est-ce h(x)encore monotone?
Emiliano
1
@happy_emi: Oui, si h(x, p1)et h(x, p2)sont cohérents, ils min(h(x,p1), h(x,p2))seront également cohérents. Ceci est facile à montrer à partir de la définition sur wikipedia (nous aurions besoin de montrer que min(h(x, p1), h(x, p2)) <= distance(x,y) + min(h(y, p1), h(y, p2))pour tous les nœuds xet yavec un bord entre eux. Supposons maintenant que h(x, p1)c'est le minimum; pouvez-vous montrer que c'est certainement <=du côté droit, en utilisant le fait que les deux heuristiques sont cohérentes?)
BlueRaja - Danny Pflughoeft
31

Oui, la distance de Manhattan entre deux points est toujours la même, tout comme la distance régulière entre eux. Vous pouvez penser que la distance de Manhattan est les composantes X et Y d'une ligne passant entre les deux points.

Cette image ( de Wikipedia ) illustre bien cela:

Distances Manhattan

La ligne verte est la distance réelle.

Les lignes bleues , rouges et jaunes représentent toutes la même distance de Manhattan (12 unités). Quelle que soit la combinaison de mouvements vers le haut et vers la droite que vous dessinez du point en bas à gauche vers le bas à droite, vous obtiendrez la même distance totale de Manhattan.

MichaelHouse
la source
2
Grande réponse: courte, douce, précise et avec une jolie photo.
Tom 'Blue' Piddock
1
Cette réponse est proche, mais incorrecte. Cette image ne montre pas que la distance de Manhattan est cohérente (en fait, si vous considérez la ligne verte comme la distance, elle n'est pas cohérente!) , Et le raisonnement selon lequel il n'a pas besoin de revérifier les nœuds car "la distance de Manhattan entre deux points est toujours le même " ne tient pas (l'énoncé est également vrai de h(x) = 1000, ce qui n'est évidemment pas cohérent) . Il peut éviter de revérifier les nœuds, mais uniquement parce que la distance Manhatten est cohérente, ce que cette réponse ne montre pas.
BlueRaja - Danny Pflughoeft
2
Je crois que d'après la définition que vous avez liée, la distance de Manhattan est cohérente. La distance de la ligne verte utiliserait une heuristique différente. Les lignes rouge, bleue et jaune montrent que la distance entre les deux nœuds reste la même (lors de l'utilisation de la même heuristique). Un rapprochement réduit l'heuristique et un éloignement augmente l'heuristique. Cela répond à l'exigence monotone de l'OP. Au fur et à mesure que le graphique est construit, avec un nœud à chaque "intersection", la distance de Manhattan est cohérente. S'il s'agissait d'un scénario différent (comme autoriser un mouvement diagonal), l'heuristique serait mauvaise.
MichaelHouse
2
J'ai déjà dit que Manhatten Distance est cohérent, mais pas pour les raisons que vous mentionnez. Votre réponse ne montre pas de cohérence, ni votre argument dans les commentaires. "Heuristique cohérente / monotone" a une définition précise (donnée dans mon lien ci-dessus) , qui n'est pas la même chose qu'une fonction monotone pour laquelle vous semblez la confondre. Dire «se rapprocher réduit l'heuristique et s'éloigner augmente l'heuristique» n'est pas suffisant pour montrer sa cohérence, par exemple. 2*manhattensatisfait cela, mais n'est pas cohérent.
BlueRaja - Danny Pflughoeft
3
Je ne sais pas pourquoi vous dites que c'est incorrect , vous semblez insister sur le fait que cette réponse est incomplète . La preuve dans votre réponse semble tout aussi faible: "la distance de Manhatten est cohérente ...", vous continuez ensuite à réitérer le cahier des charges initial de la question, en suivant comment elle serait non recevable si le scénario était différent . Je n'avais pas l'impression que la réponse justifiait une preuve mathématique complète. Si vous pensez que cette question l'exige, veuillez l'inclure dans votre réponse et je voterai. Merci pour les critiques constructives.
MichaelHouse
6

Dans le prolongement de la réponse de Byte56, je voudrais souligner que dans votre ensemble de données spécifique, l'utilisation de Manhattan Distance comme fonction heuristique sera en fait toujours une heuristique parfaite dans le sens où elle renverra toujours le coût réel du chemin (en supposant qu'il y ait rien "bloque" les chemins).

Vous devez également noter que tous les nœuds dans la bonne direction (horizontalement ou verticalement) produiront la même distance attendue (car il existe de nombreux chemins également courts vers l'objectif). Vous devez savoir que votre file d'attente prioritaire (ensemble ouvert) doit, en cas de priorités liées, retirer le dernier nœud ajouté en premier (LIFO - Last In First Out). Ce faisant, vous n'examinerez que les nœuds qui se retrouveront dans le chemin optimal . Si vous examinez des nœuds également appropriés d'une manière FIFO (First In First Out), vous examinerez efficacement tous les nœuds qui font partie d'un meilleur chemin. Ce problème se pose car il existe plusieurs chemins d'accès également bons vers le nœud cible.

Thorkil Holm-Jacobsen
la source
"(en supposant que rien ne bloque le chemin)" - c'est une hypothèse assez grande. S'il n'y a rien qui bloque le chemin, il n'y a pas besoin d'un algorithme de recherche de chemin pour commencer!
BlueRaja - Danny Pflughoeft
@ BlueRaja-DannyPflughoeft: C'est vrai, c'était juste une pensée surgissant en regardant l'image de Byte56. Le reste est néanmoins vrai.
Thorkil Holm-Jacobsen
4

Je ne sais pas ce que vous entendez par "toujours" cohérent. La distance de Manhattan sur une grille fixe est-elle indépendante du chemin emprunté? Oui, comme l'a dit la réponse de Byte56.

Cependant, par exemple, la distance de Manhattan n'est pas invariante lors des rotations. Par exemple, la distance de Manhattan ( norme L1 ) entre l'origine et un point (10,10)est |10-0| + |10-0| = 20. Cependant, si vous faites pivoter vos coordonnées de 45 degrés (alors votre point fixe se trouve maintenant dans l'une des directions de la grille), vous constaterez maintenant que le même point se trouve maintenant (10sqrt(2),0), ainsi que la distance de Manhattan à l'origine de 10sqrt(2)~14.14.

dr jimbob
la source
+1 pour l'avoir signalé; OTOH, la distance de Manhattan est invariante sous des rotations à 90 degrés, qui sont vraiment les seules qui peuvent être faites «de manière cohérente» sur une grille discrète.
Steven Stadnicki
1
Bonne prise, bien qu'il ait mentionné que seuls les mouvements horizontaux et verticaux sont autorisés.
Thorkil Holm-Jacobsen
1
La question initiale portait sur la cohérence comme en monotonie.
Emiliano