* 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.

18
demandé sur Michael Myers 2009-06-18 17:42:53

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