Cette page permet de tester différents algorithmes de parcours afin de résoudre un taquin. Ces algorithmes, leurs enjeux d'optimalité, de complexité temporelle et d'utilisation de la mémoire, sont largement détaillés sur cette page.
Un taquin est un jeu, où, étant donné une position comme celle ci-dessous, on doit atteindre une position cible en faisant glisser les pièces.
Pour un taquin $n\times n$, le nombre d'états possibles est $(n^2)!$ - dont seulement la moitié permettent d'atteindre la position cible (cela se montre à coup d'étude de groupes de permutations). Pour $n=3$, on obtient $181\;440$ états accessibles - et il est encore possible de les loger en mémoire (un état est une suite de 9 chiffres entre $0$ et $8$, et peut donc être codé sur $9\times 4=36$ bits, ce qui donne environ 800Ko pour stocker l'ensemble des états). Pour $n=4$, le nombre d'états accessibles est environ $10^{13}$ et il faudrait environ $50 To$ pour stocker ces états, ce qui commence à être moins raisonnable.
Pour un taquin à 15 pièces (donc $4\times 4$), où la case vide est initialement l'une des cases centrales, le tableau suivant donne le nombre de positions accessibles au plus court en exactement $n$ coups :
| $n$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | … |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 4 | 10 | 20 | 38 | 80 | 174 | 372 | 762 | 1540 | 3072 | 6196 | 12356 | 24516 | 48179 | 94356 | 183432 | 355330 | 682250 | … |
Vous trouverez en dessous de l'application des précisions sur son implémentation.
Nouvelle position :
(Vous pouvez également permuter des cases de la position en cliquant dessus.)
Résoudre :
Positions possibles : 181 440
Cible :
Algorithme :
Itérations :
Temps :
Mémoire utilisée :
Longueur du chemin trouvé :
| Algorithme | Itérations | Temps | Mémoire | Longueur du chemin |
|---|
- Tout coup «vaut» 1 : dans le graphe des configurations, les arêtes sont toutes de poids 1. L'algorithme de Dijkstra n'apparait donc pas, puisqu'il revient à un parcours en largeur.
- S'il y a plusieurs possibilités de même coût lors du déroulement d'un algorithme, l'une d'elles est choisie au hasard. Cela explique que les résultats puissent être différents lorsqu'on lance plusieurs fois le même algorithme depuis la même configuration.
- «$4\times 4$ (solution $\leq$ 15)» désigne un taquin $4\times 4$ où la configuration choisie peut se ramener à la configuration cible en moins de 15 coups.
- De même pour «solution $\leq$ 25, 35…».
- Dans les algorithmes guidés, l'heuristique «distance» consiste à évaluer la distance d'une position à la cible comme la somme des distances de chaque pièce à sa position dans la cible (on prend les distances de Manhattan - qui correspondent au nombre de coups minimal permettant de mettre une pièce en bonne position). On obtient ainsi clairement une minoration de la distance réelle à la cible - et cette heuristique est monotone pour A*Si vous ne comprenez rien à cet item, une lecture de la page pointée ci-dessus sur les parcours vous sera utile !.
-
L'heuristique «motifs» utilise une bibliothèque précalculée, contenant des entrées telle que celle-ci (quoique codées différemment pour diminuer la taille mémoire de la bibliothèque)
???? ???? E??? D?F? -> 5
qui signifie que, depuis la position indiquée, il faut 5 déplacements de E, D et F pour les placer dans leur position correcte. On peut faire de même pour d'autres ensembles de pièces (par exemple $\{1,2,3\}$, $\{4,5,6\}$, $\{7,8,9\}$, $\{A,B,C\}$). En sommant les nombres de déplacements minimaux pour remettre en place chacun de ces ensembles de pièces (qui forment une partition de l'ensemble des pièces), on obtient un minorant du nombre de mouvements nécessaire à la résolution complète de la position. Voir cette page pour plus de précisions et résultats concernant cette méthode. Sur cette page, j'utilise 21 partitions différentes (4-4-4-3 ou 5-5-5) - pour un total d'environ $17$ millions d'entrées dans la bibliothèque - et l'heuristique est le maximum des minorants obtenus. Un stockage semi-naïf donne environ 50Mo pour le dictionnaire (ce qui peut expliquer que cette page mette un peu de temps à se charger …). - L'implémentation propre des parcours en profondeur ou largeur est un excellent exercice de programmation. Pour atteindre performances raisonnables, on peut utiliser une table de hachage pour retrouver rapidement les configurations déjà rencontrées.
Répartition empirique du nombre de coups minimal pour résoudre un taquin $4\times 4$ (sur ~300 tirés au hasard). La moyenne empirique obtenue est proche de 52. Les trois quarts des positions tirées ont une distance à la position cible comprise entre 47 et 57.
Nombre d'itérations de l'algorithme A* (avec l'heuristique «motifs») en fonction de la distance à la position cible (sur ~100 exemples tirés au hasard).
Références
- Algorithmique, de Cormen et al.
- Intelligence artificielle 3e édition : Avec plus de 500 exercices, chapitre 3, de Russel et Norvig
- A Formal Basis for the Heuristic Determination of Mimimum Cost Paths (pour A*), de Hart, Nilsson et Raphael