Admissible et pourtant non monotone

Distances exactes : $d(G)=0$, $d(B)=2$, $d(A)=3$, $d(S)=4$ (par $S\to A\to B\to G$, car $S\to B\to G$ coûte $5$).

Admissible : $h(A)=3=d(A)$, et $h=0\le d$ partout ailleurs. Aucune surestimation.

Non monotone : la monotonie exige $h(u)\le c(u,v)+h(v)$ sur chaque arc. Sur l'arc $A\to B$ : $h(A)=3$ et $c(A,B)+h(B)=1+0=1$. On a $3>1$ : l'inégalité triangulaire est violée.

Le déroulement, mesuré, avec un ensemble fermé :

Avec $h(A)=3$ : on extrait $S$, on engendre $A$ ($f=1+3=4$) et $B$ ($f=3+0=3$) ; on extrait donc $B$ avant $A$, avec $g(B)=3$, et on le ferme. Puis on extrait $A$ ($f=4$), qui offre à $B$ un chemin à $g=2<3$ : $B$ doit être rouvert et développé une seconde fois. Le coût final est correct — l'admissibilité garantit l'optimum —, mais on a payé un développement de plus.

Ce que la monotonie achète, exactement. Elle assure que $f$ est croissante le long de tout chemin : $f(v)=g(u)+c(u,v)+h(v)\ge g(u)+h(u)=f(u)$. Les sommets sortent donc de la file par $f$ croissante, et quand on en ferme un, son $g$ est déjà minimal — aucune réouverture n'est possible. C'est la deuxième ligne du tableau du cours, et cet exercice en montre la contraposée : sans monotonie, un sommet fermé peut redevenir ouvert.

La conséquence de génie logiciel. Une implémentation qui suppose la monotonie — et donc ignore tout sommet déjà fermé — rendrait ici $g(B)=3$, puis $g(G)=5$ au lieu de $4$. Le même code est correct ou faux selon une propriété de l'heuristique qu'il ne vérifie pas. On documente donc la précondition, comme le cours le fait dans le commentaire de a_etoile.