A * heuristique, surestimation / sous-estimation?

Question

Je suis confus quant aux termes surestimation / sous-estimation. Je comprends parfaitement comment fonctionne l'algorithme A *, mais je ne suis pas sûr des effets d'une heuristique qui surestime ou sous-estime.

La surestimation survient-elle lorsque vous prenez le carré de la ligne de vision directe des oiseaux? Et pourquoi rendrait-il l'algorithme incorrect? La même heuristique est utilisée pour tous les nœuds.

Est-ce une sous-estimation lorsque vous prenez la racine carrée de la ligne d'observation directe des oiseaux? Et pourquoi l’algorithme est-il toujours correct?

Je ne trouve pas d’article qui explique tout cela de manière claire et nette, et j’espère que quelqu'un ici a une bonne description.

Answer 1

Vous surestimez le moment où l'estimation de l'heuristique est supérieure au coût réel du trajet final. Vous sous-estimez quand il est inférieur (vous ne devez pas sous-estimer, vous ne devez pas surestimer; les correctes estimations sont correctes). Si les coûts marginaux de votre graphique sont tous égaux à 1, les exemples que vous donnez fourniraient des surestimations et des sous-estimations, bien que la distance de coordonnées simples fonctionne également dans un espace cartésien.

La surestimation ne rend pas exactement l'algorithme "incorrect" ;; cela signifie que vous n'avez plus d'heuristique admissible , ce qui est une condition pour que A * soit garanti de produire un comportement optimal. Avec une heuristique inadmissible, l’algorithme peut mener à des tonnes de travaux superflus en examinant des chemins qu’il devrait ignorer et éventuellement en trouvant des chemins non optimaux en raison de leur exploration. Que cela se produise ou non dépend de votre espace de problème. Cela se produit parce que le coût du chemin est "en décalage" avec le coût estimé, ce qui donne essentiellement à l’algorithme des idées fausses sur les chemins les meilleurs.

Je ne suis pas sûr que vous l'ayez trouvé, mais vous voudrez peut-être consulter la Wikipedia Un * article . Je mentionne (et le lien) principalement parce qu'il est presque impossible de Google pour cela.

Answer 2

Dans l'article Wikipedia , la partie pertinente de la description de l'algorithme est la suivante:

  

L'algorithme continue jusqu'à ce qu'un noeud d'objectif ait une valeur f inférieure à celle de tout noeud de la file d'attente (ou jusqu'à ce que la file d'attente soit vide).

L'idée principale est que, avec la sous-estimation, A * cessera d'explorer un chemin potentiel vers l'objectif une fois qu'il sait que le coût total du chemin dépassera le coût d'un chemin connu vers l'objectif. Puisque l'estimation du coût d'un chemin est toujours inférieure ou égale au coût réel du chemin, A * peut ignorer un chemin dès que le coût estimé dépasse le coût total d'un chemin connu.

Avec la surestimation, A * n’a aucune idée du moment où il peut arrêter d’explorer un chemin potentiel, car il peut exister des chemins dont le coût réel est inférieur mais le coût estimé supérieur au meilleur chemin actuellement connu vers l’objectif.

Answer 3

Autant que je sache, vous voulez généralement sous-estimer pour pouvoir toujours trouver le chemin le plus court. Vous pouvez trouver une réponse plus rapidement en surestimant, mais vous risquez de ne pas trouver le chemin le plus court. C’est pourquoi la surestimation est "incorrecte", alors que la sous-estimation peut toujours fournir la meilleure solution.

Je suis désolé de ne pouvoir vous donner aucune indication sur les lignes d'observation d'oiseaux ...

Answer 4

Réponse courte

@chaos answer is imminente mais trompeuse (peut être mise en surbrillance)

  

La surestimation ne rend pas exactement l'algorithme "incorrect" ;; ce que cela signifie, c'est que vous n'avez plus d'heuristique admissible, ce qui est une condition pour que A * soit garanti de produire un comportement optimal. Avec une heuristique inadmissible, l’algorithme peut aboutir à des tonnes de travaux superflus

comme @AlbertoPL l'indique

  

Vous pouvez trouver une réponse plus rapidement en surestimant mais vous risquez de ne pas trouver le chemin le plus court.

Au final (à côté de l'optimum mathématique), la solution optimale dépend fortement de savoir si vous prenez en compte les ressources informatiques, le temps d'exécution, des types spéciaux de "Cartes" / Espaces d'état, etc.

Réponse longue

A titre d'exemple, je pourrais penser à une application en temps réel dans laquelle un robot se rapproche plus rapidement de la cible en utilisant une heuristique surestimée, car le gain de temps en démarrant plus tôt est supérieur à l'avantage de temps en prenant le chemin le plus court mais en attendant plus longtemps pour le calculer. solution.

Pour vous donner une meilleure impression, je partage quelques résultats exemplaires que j'ai rapidement créés avec Python. Les résultats proviennent du même algorithme A *, seule l'heuristique diffère. Chaque nœud (cellule de la grille) a des bords pour tous les huit voisins sauf les murs. Les bords diagonaux coûtent sqrt (2) = 1,41

La première image montre les chemins renvoyés de l’algorithme pour un exemple simple. Vous pouvez voir des chemins sous-optimaux issus de la surestimation des heuristiques (rouge et cyan). D'autre part, il existe plusieurs chemins optimaux (bleu, jaune, vert) et cela dépend de l'heuristique de laquelle on se trouve en premier.

Les différentes images montrent tous les nœuds développés lorsque la cible est atteinte. La couleur indique le coût estimé du chemin en utilisant ce nœud (en considérant également le chemin "déjà emprunté" du début à ce nœud; mathématiquement, il s'agit du coût jusqu'à présent, plus de l'heuristique pour ce nœud). À tout moment, l’algorithme élargit le noeud avec le coût total estimé le plus bas (décrit précédemment).

>

1. Zéro (bleu)

• correspond à l'algorithme de Dijkstra
• Nœuds développés: 2685
• Longueur du chemin: 89.669

2. À vol d'oiseau (jaune)

• Nœuds développés: 658
• Longueur du chemin: 89.669
• https://i.stack.imgur.com/75eFV.png

3. Idéal (vert)

• Le chemin le plus court sans obstacles (si vous suivez les huit directions)
• Estimation la plus élevée possible sans surestimation (d'où "idéal")
• Noeuds développés: 854
• Longueur du chemin: 89.669
• https://i.stack.imgur.com/VqMtF.png

4. Manhattan (rouge)

• Le chemin le plus court sans obstacle (si vous ne vous déplacez pas en diagonale; autrement dit, le coût du "déplacement en diagonale" est estimé à 2)
• surestime
• Nœuds développés: 562
• Longueur du chemin: 92.840
• https://i.stack.imgur.com/gD9t4.png

5. À vol d'oiseau dix (cyan)

• surestime
• Nœuds développés: 188
• Longueur du chemin: 99.811
• https://i.stack.imgur.com/SZuFH.png