Un* heuristique, la surestimation/sous-estimation?
Je suis confus au sujet de l'termes surestimation/sous-estimation. J'ai parfaitement comment algorithme A* fonctionne, mais je ne suis pas sûr de les effets de l'existence d'une heuristique qui surestimer ou sous-estimer.
Est surestimation lorsque vous prenez la place de l'direct birdview ligne? Et pourquoi serait-il faire l'algorithme incorrect? La même heuristique est utilisée pour tous les nœuds.
Est la sous-estimation lorsque vous prenez la racine carrée de la direct birdview ligne? Et pourquoi l'algorithme reste correct?
Je ne peux pas trouver un article qui explique agréable et clair, donc j'espère que quelqu'un ici a une bonne description.
Vous devez vous connecter pour publier un commentaire.
Vous êtes à la surestimation lors de l'heuristique de l'estimation est supérieure à la finale du coût du chemin. Vous êtes à sous-estimer lorsqu'il est inférieur (vous n'avez pas à sous-estimer, vous avez juste à ne pas surestimer; corriger estimations sont très bien). Si votre graphique de bord coûts sont tous des 1, les exemples que vous donnez donnerait la surestimation et la sous-estime, bien que la plaine de coordonner à distance fonctionne aussi peachy dans un espace Cartésien.
Surestimation n'est pas exactement l'algorithme de "incorrect"; ce que cela signifie, c'est que vous n'avez plus de recevable heuristique, qui est la condition d'une* doivent être garantis à produire un comportement optimal. Avec un irrecevable heuristique, l'algorithme peut se retrouver à faire des tonnes de travail superflu l'examen des chemins qu'il devrait être ignorant, et, éventuellement, de trouver des sous-optimale des chemins en raison de l'exploration de celles-ci. Si ce fait se produit dépend de votre problème de l'espace. Cela se produit parce que le coût du chemin est "hors commune" avec l'estimation du coût, ce qui donne l'algorithme foiré idées sur les itinéraires qui sont mieux que d'autres.
Je ne suis pas sûr de savoir si vous avez trouvé, mais vous pouvez regarder le Wikipédia Un article* . Je mentionne (et lien), principalement parce qu'il est presque impossible de Google pour cela.
De la Wikipédia Un article* , la partie de la description d'algorithme est:
L'idée clé est que, avec understimation, Un* ne cesser d'explorer un chemin possible à l'objectif une fois qu'il sait que le coût total de la voie ne peut excéder le coût d'un chemin du but. Depuis l'estimation d'un chemin de coût est toujours inférieur ou égal au chemin du coût réel, Un* peuvent jeter un chemin dès que le coût estimatif dépasse le coût total d'un sentier connu.
Avec la surestimation, A* n'a aucune idée de quand il peut cesser d'explorer un chemin possible comme il peut y avoir des chemins à moindre coût réel, mais plus élevé coût estimé que le meilleur actuellement connus chemin du but.
Pour autant que je sais, vous voulez généralement à sous-estimer, de sorte que vous pouvez toujours trouver le chemin le plus court. Vous pouvez trouver une réponse plus rapide par la surestimation, mais vous ne pouvez pas trouver le chemin le plus court. Donc pourquoi surestimation est "incorrect", alors que la sous-estimation peut toujours fournir la meilleure solution.
Je suis désolé que je ne peux fournir aucune indication quant à la birdview lignes...
Réponse courte
@chaos réponse est un peu trompeur de l'omi (peut doit être mis en évidence)
comme @AlbertoPL insinue
À la fin (à côté de la mathématique optimale), la solution optimale dépend fortement si vous envisagez de ressources de calcul, de l'exécution, des types spéciaux de "Maps"/État des Espaces, etc.
Réponse longue
Comme un exemple de ce que je pouvais penser en temps réel de l'application où un robot devient plus rapide de la cible à l'aide d'une surestimation heuristique parce que l'avantage de temps en commençant tôt est plus grand que l'avantage de temps pour prendre le chemin le plus court, mais d'attendre plus longtemps pour le calcul de cette solution.
Pour vous donner une meilleure impression, je partage certains des résultats exemplaires que j'ai rapidement créé avec Python. Les résultats de la tige à partir de la même algorithme A*, seulement l'heuristique diffère. Chaque nœud de la grille de la cellule) a obtenu les bords à l'ensemble des huit voisins à l'exception des murs. Des bords de diagonale coût sqrt(2)=1.41
La première photo montre les chemins renvoyés de l'algorithme pour un exemple simple cas. Vous pouvez voir quelques sous-optimale des chemins de la surestimation de l'heuristique (rouge et cyan). De l'autre côté, il y a plusieurs chemins optimaux (bleu, jaune, vert) et il dépend de l'heuristique, qui est trouvé en premier.
Les différentes images afficher tous les nœuds développés lorsque la cible est atteinte. La couleur montre l'estimation du coût du chemin à l'aide de ce nœud (en considérant le "déjà pris" chemin d'accès de départ pour ce nœud; mathématiquement, c'est le coût jusqu'à présent, plus l'heuristique de ce nœud). À tout moment, l'algorithme se développe le nœud avec les plus bas coût total estimé (décrit précédemment).
1. Zéro (bleu)
2. Comme l'oiseau (jaune)
3. Idéal (vert)
4. Manhattan (rouge)
5. Comme l'oiseau fois dix (cyan)