Tip:
Highlight text to annotate it
X
Nous allons maintenant vous donner une intuition pour savoir pourquoi
une fonction heuristique optimiste, h, trouve le chemin à moindre coût.
Quand A-étoile termine, il retourne un chemin, p, avec un coût estimé, c.
Il apparait que c est aussi le véritable coût,
car à l'objectif la composante h vaut 0,
et ainsi le coût du chemin est le coût total comme estimé par la fonction.
Maintenant, tous les chemins du tiers de devant
ont un coût estimé plus grand que c,
et nous savons cela car le tiers de devant est exploré par ordre du moins coûteux d'abord.
Si h est optimiste, alors le coût estimé
est moins que le véritable coût,
donc le chemin p doit avoir un coût qui est moins que le véritable coût
de n'importe lequel des chemins du premier tiers.
N'importe quel chemin allant après le tiers de devant
doit avoir un coût qui est plus grand que cela
car nous sommes d'accord que le coût de marche est toujours 0 ou plus.
Donc cela signifie que ce chemin p doit être le chemin à coût minimal.
Maintenant, je devrais dire que cet argument ne tient
que pour le parcours d'arbre.
Pour le parcours de graphe, l'argument est déja un peu plus compliqué,
mais l'intuition générale est la même.