Le taquin, trois heuristiques

Sur l'instance

$$\left(\begin{array}{ccc}8& 6& 7\\ 2& 5& 4\\ 3& \square & 1\end{array}\right)\text{vers}\left(\begin{array}{ccc}1& 2& 3\\ 4& 5& 6\\ 7& 8& \square \end{array}\right)$$

les trois heuristiques valent respectivement $0$, $7$ et $21$ à l'état de départ. Mesures :

Les trois trouvent la même solution, en $31$ coups — c'est l'instance la plus difficile du taquin $3\times 3$.

Ce que les chiffres disent. Avec $h=0$, A développe $181439$ états, c'est-à-dire la totalité* de la composante accessible ($9!/2=181440$ configurations) : sans information, il faut tout voir. Les cases mal placées ne font gagner qu'un tiers — elles comptent les cases fautives mais ignorent leur éloignement, et sous-estiment donc massivement. La distance de Manhattan divise par $26$.

La règle de dominance, et pourquoi elle vaut. Si $h_1$ et $h_2$ sont admissibles et $h_1\le h_2$ partout, alors tout sommet développé avec $h_2$ l'est aussi avec $h_1$ : le tableau du cours dit qu'on prend, parmi les heuristiques admissibles, la plus grande. Ici $h_{\text{mal placeˊes}}\le h_{\text{Manhattan}}$ — chaque case mal placée contribue au moins $1$ à la somme de Manhattan —, d'où l'ordre observé, et il n'est pas un accident de l'instance.

Le tarif de l'information. Manhattan coûte neuf boucles élémentaires par état, contre neuf comparaisons pour les cases mal placées : le calcul est à peine plus cher, et il divise l'exploration par $26$. C'est le compromis habituel des heuristiques — on paie un peu par nœud pour en visiter beaucoup moins.