Probleme – A* : ce que l'admissibilité et la monotonie achètent

1. Monotone $\Rightarrow$ admissible. Soit $v$ un sommet et $v=v_0\to v_1\to \cdots \to v_p=\text{but}$ un chemin optimal, de coût $d(v)$. La monotonie donne $h(v_i)\le c(v_i,v_{i+1})+h(v_{i+1})$ pour tout $i$. En sommant de $i=0$ à $p-1$ et en simplifiant les termes qui se télescopent :

$$h(v)\le \sum _{i=0}^{p-1}c(v_i,v_{i+1})+h(\text{but})=d(v)+0=d(v).$$

Donc $h$ ne surestime pas : elle est admissible. La réciproque est fausse, et l'exercice 27.8 en donne le contre-exemple minimal — quatre sommets suffisent.

2. Ce que la monotonie garantit.

(a) $f$ ne décroît pas le long d'un chemin. Si $v$ est atteint depuis $u$ par un arc, alors $g(v)=g(u)+c(u,v)$, donc

$$f(v)=g(u)+c(u,v)+h(v)\ge g(u)+h(u)=f(u),$$

par la monotonie. La valeur $f$ est donc croissante le long de tout chemin engendré.

(b) Un sommet extrait a son $g$ définitif. Supposons qu'on extraie $u$ avec $g(u)>d^{\ast }(u)$, où $d^{\ast }(u)$ est le coût optimal depuis la source. Soit $w$ le premier sommet non extrait sur un chemin optimal vers $u$. Alors $g(w)=d^{\ast }(w)$ — son prédécesseur sur ce chemin a été extrait, donc a relâché l'arc — et

$$f(w)=d^{\ast }(w)+h(w)\le d^{\ast }(u)+h(u)<g(u)+h(u)=f(u),$$

la première inégalité étant (a) appliquée le long du chemin optimal de $w$ à $u$. La file aurait donc extrait $w$ avant $u$ : contradiction.

(c) Aucune réouverture. Un sommet n'est rouvert que si son $g$ diminue après extraction ; par (b), il était déjà minimal. Donc jamais. C'est ce que la deuxième ligne du tableau du cours résume en cinq mots, et l'économie est réelle : sans monotonie, un sommet peut être développé plusieurs fois, et dans le pire cas un nombre exponentiel de fois.

3. La grille, mesurée. Grille $30\times 30$ sans obstacle, de $(0,0)$ à $(29,29)$, déplacements orthogonaux de coût $1$ ; le plus court chemin coûte $58$.

*Avec $h=0$, A développe la grille entière** : $900$ sommets pour un chemin de $58$. Il explore par distance croissante depuis la source, en « disque », et le but est le point le plus éloigné.

Avec Manhattan, il en développe $900$ ou $59$ selon la seule manière de servir les égalités — et c'est le résultat qui surprend. La raison est arithmétique : pour un sommet $(i,j)$ de cette grille, $g=i+j$ et $h=(29-i)+(29-j)$, donc $f=58$ partout. Tout sommet de la grille est sur un plus court chemin, et A ne dispose d'aucune* information pour les départager : les $900$ sommets sont ex æquo. Servis en file, ils sont tous développés avant le but ; servis en pile, la recherche plonge et n'en développe que $59$, soit la longueur du chemin plus un.

La leçon, et elle n'est pas dans le tableau du cours : une heuristique exacte ne garantit pas une exploration courte. Elle garantit qu'aucun sommet de $f$ supérieur à $d^{\ast }$ n'est développé ; s'il y a $\Theta (n^2)$ sommets à $f=d^{\ast }$, ils peuvent tous l'être. Le départage des égalités est un troisième ingrédient, à côté de l'admissibilité et de la monotonie, et il vaut ici un facteur $15$.

4. Heuristique monotone et exacte. Alors $f(v)=g(v)+d(v,\text{but})$ vaut $d^{\ast }$ sur tout sommet d'un chemin optimal, et strictement plus ailleurs : A* n'extrait que des sommets optimaux, et ne se trompe jamais de direction. Le nombre d'extractions est celui des sommets optimaux — $\ell +1$ si le chemin est unique, et la question 3 vient de montrer que ce peut être bien davantage s'il ne l'est pas.

Et c'est un raisonnement circulaire, qu'il faut savoir énoncer : $h=d$ suppose de connaître $d$, c'est-à-dire d'avoir résolu le problème. Toute la conception d'une heuristique consiste à s'en approcher à un coût moindre que le calcul exact — typiquement en résolvant un problème relâché. La distance de Manhattan au taquin est exactement cela : c'est le nombre de coups si les pièces pouvaient se traverser. Un problème plus simple, dont l'optimum minore celui du vrai — et l'admissibilité est alors gratuite.