* Heuristique, la surestimation/sous-estimation?
je suis confus au sujet des termes surestimation/sous-estimation. Je comprends parfaitement comment fonctionne un algorithme*, mais je ne suis pas sûr des effets d'avoir un heuristique qui surestime ou sous-estime.
la surestimation est-elle lorsque vous prenez le carré de la ligne directe de birdview? Et pourquoi l'algorithme serait incorrect? La même heuristique est utilisée pour tous les nœuds.
est-ce que la sous-estimation est quand vous prenez le squareroot de la ligne directe de birdview? Et pourquoi l'algorithme toujours correct?
Je n'arrive pas à trouver un article qui l'explique clairement et gentiment donc j'espère que quelqu'un ici a une bonne description.
4 réponses
vous surestimez lorsque l'estimation heuristique est plus élevée que le coût réel du sillon final. Vous sous-estimez quand il est plus bas (vous n'avez pas à sous-estimer, vous avez juste à ne pas surestimer; correct les estimations sont très bien). Si les coûts de bord de votre graphe sont tous 1, alors les exemples que vous donnez fourniraient des surestimations et des sous-estimations, bien que la distance de coordonnée simple fonctionne également peachy dans un espace cartésien.
la surestimation n'est pas exactement rendez l'algorithme "incorrect"; cela signifie que vous n'avez plus de recevable heuristique