Une heuristique qui surestime

Les distances exactes au but sont $d(S)=2$, $d(A)=1$, $d(B)=5$, $d(G)=0$. L'heuristique proposée vérifie $h(S)=0\le 2$, $h(B)=0\le 5$, $h(G)=0$ — mais $h(A)=6>1=d(A)$ : elle n'est pas admissible, et le seul sommet où elle échoue est $A$, celui qui est sur le chemin optimal.

Le déroulement, mesuré :

• On extrait $S$ ($f=0$). On engendre $A$ avec $g=1$, $f=1+6=7$, et $B$ avec $g=1$, $f=1+0=1$.
• On extrait $B$ ($f=1$). On engendre $G$ avec $g=6$, $f=6$.
• On extrait $\mathbf{G}$ ($f=6<7$) : l'algorithme s'arrête et rend $6$.

Or le coût optimal est $2$, par $S\to A\to G$. *A a rendu un chemin trois fois trop cher**, et il ne le sait pas.

Le mécanisme. La surestimation en $A$ a repoussé $A$ au fond de la file. Quand $G$ est arrivé avec $f=6$, le seul concurrent restant affichait $f=7$ — un chiffre faux, gonflé par $h$. La file a donc extrait $G$ en croyant qu'aucun meilleur chemin ne restait possible. C'est exactement l'endroit où la démonstration du cours s'effondre : elle repose sur $f(v)=g(v)+h(v)\le g(v)+d(v,\text{but})=d^{\ast }$, inégalité qui n'est plus vraie.

Le contraste des trois cas, mesuré sur le même graphe :

La leçon est celle de la dernière ligne du tableau du cours : une heuristique trop optimiste — comme $h=0$ — ne coûte que du temps ; une heuristique trop pessimiste coûte la correction, et le silence avec. Aucun avertissement n'accompagne le $6$.