Utilisateur:Fm4911/Brouillon

• Gérer mon brouillon
• Demander une relecture (voir les demandes)
• Publier mon brouillon

Cette page est un brouillon appartenant à Fm4911

Conseils de rédaction

• → N'hésitez pas à publier sur le brouillon un texte inachevé et à le modifier autant que vous le souhaitez.
• → Pour enregistrer vos modifications au brouillon, il est nécessaire de cliquer sur le bouton bleu : « Publier les modifications ». Il n'y a pas d'enregistrement automatique.

Si votre but est de publier un nouvel article, votre brouillon doit respecter les points suivants :

• Respectez le droit d'auteur en créant un texte spécialement pour Wikipédia en français (pas de copier-coller venu d'ailleurs).
• Indiquez les éléments démontrant la notoriété du sujet (aide).
• Liez chaque fait présenté à une source de qualité (quelles sources  – comment les insérer).
• Utilisez un ton neutre, qui ne soit ni orienté ni publicitaire (aide).
• Veillez également à structurer votre article, de manière à ce qu'il soit conforme aux autres pages de l'encyclopédie (structurer – mettre en page).

• → Si ces points sont respectés, pour transformer votre brouillon en article, utilisez le bouton « publier le brouillon » en haut à droite. Votre brouillon sera alors transféré dans l'espace encyclopédique.

Cube de Rubik : représentations et algorithmes optimaux

Le Rubik's Cube est un casse-tête très populaire depuis 1980. Il a aussi donné lieu à de nombreuses recherches mathématiques et algorithmiques. On s'intéresse ici aux algorithmes optimaux (ou sous-optimaux) de résolution par calculateur d'une position quelconque du cube. On précise les représentations mathématiques du groupe $G$ des états du cube et de ses sous-groupes, nécessaires pour la mise en œuvre effective sur calculateur. Pour l'essentiel, il s'agit des représentations par coordonnées introduites par Kociemba. Les algorithmes optimaux sont ceux qui peuvent calculer, pour un état arbitraire du cube, le mouvement de taille minimale permettant de revenir à l'état initial du cube (rangé).

Rubik's cube : représentations de base

Notations et abréviations

On fixe la position du cube dans l'espace. La notation standard (anglo-saxonne) des faces et des manœuvres associées (quart de tour dans le sens des aiguilles d'une montre) est $U,D,L,R,F,B$. Les notations françaises équivalentes sont $H,B,G,D,A,P$ pour Haut, Bas, Gauche, Droite, Avant, Postérieure. On utilisera souvent la notation anglo-saxonne, qui est la plus répandue.

On note CA les cubes-arêtes, CS les cubes-sommets ou coins. On utilise les termes anglais de flip pour désigner le basculement d'un CA (valeur binaire 0 ou 1), et de twist pour désigner la rotation d'un CS ( valeurs 0, 1,2 en tiers de tours dans le sens des aiguilles d'une montre).

Du point de vue mathématique, on note $\mathbb {Z} _{n}\equiv \mathbb {Z} /n\mathbb {Z}$ l'ensemble des entiers modulo n, et $S_{n}$ le groupe symétrique des permutations de $[1..n]$. Son cardinal est $n!$. On convient ici de représenter une telle permutation par le vecteur d'entiers images $p=[p(1),\ldots ,p(n)]$.

Le groupe $G$ des mouvements, l'espace $E$ des états

Le groupe engendré par les mouvements de base est noté $G=<U,D,L,R,F,B>$.

Ces mouvements agissent sur l'état du cube, qui peut se représenter par une permutation $p\in S_{48}$ des 48 facettes mobiles du cube (les centres ne bougent pas). En notant $I=R_{0}$ l'état rangé du cube (permutation identité), on identifie de façon canonique un mouvement $m\in G$ à l'état $p=m(R_{0})\in E$. Une visualisation d'un mouvement comme permutation des facettes du cube se fait donc par un graphique du type suivant.

Etat initial --> Etat final : Superflip

Voici la permutation $p\in S_{48}$ décrite en cycles disjoints : on reconnait les 12 transpositions (2-cycles)=12 CA flipés (Cubes-Arêtes basculés).

pcycle={{2,36},{5,39},{8,37},{11,34},{13,20},{14,15},{16,17},{18,19},{22,44},{25,42},{28,45},{31,47}}

Ce Superflip est produit par le mouvement de taille 20 :

$\{H,D^{2},A,P,D,P^{2},D,H^{2},G,P^{2},D,H^{-1},B^{-1},D^{2},A,D^{-1},G,P^{2},H^{2},A^{2}\}$.

L'espace de toutes les permutations $S_{48}$ est de cardinal $48!=1.24139*10^{61}$, beaucoup plus vaste que l'espace des états possibles.

Décomposition canonique du cube

On peut caractériser l'état du cube au niveau des petits cubes CA (12 cubes arêtes) et CS (8 cubes sommets ou coins). On montre que tout état du cube se décompose de façon unique en un quadruplet (permutation des CA, orientation des CA ou flip, permutation des CS, orientation des CS ou twist) :

$(p,u,r,v)\in S_{12}\times \mathbb {Z} _{2}^{12}\times S_{8}\times \mathbb {Z} _{3}^{8}$

avec de plus les contraintes suivantes : signatures $s(p)=s(r)$, flip total $\sum _{1}^{12}u(i)=0\mod 2$, twist total $\sum _{1}^{8}v(i)=0\mod 3$.

Les permutations sont représentées par les vecteurs des images : $p=[p(1),\ldots ,p(12)]$, et de même $r=[r(1),\ldots ,r(8)]$.

La définition des orientations $(u,w)$ est dépendante d'un choix de marquage d'une facette + sur chacun des petits cubes. Quelque soit ce choix, on établit les règles suivantes de composition des états : pour deux mouvements $m_{1},m_{2}$, la composition dans cet ordre donne le mouvement $m=m_{1}m_{2}=(p,u,r,v)$ avec :

• Produit des permutations : $p=p_{1}*p_{2}\quad r=r_{1}*r_{2}$
• Composition des flips et twists : $u=u_{1}+p_{1}(u_{2})\quad v=v_{1}+r_{1}(v_{2})$

La notation $p(u)$ pour appliquer une permutation au vecteur u signifie $p(u)[i]=u[p^{-1}[i]]$.

On en déduit le cardinal du groupe $card(G)=12!8!2^{11}3^{7}/2=43252003274489856000\sim 43\times 10^{18}$.

Pour les démonstrations mathématiques détaillées, on se reportera à la référence, et au livre complet de théorie des groupes, de W.D. Joyner ici [1].

Coordonnées d'un état du cube

Pour effectuer des calculs rapides sur ces états, Kociemba a introduit une représentation par coordonnées entières, définies ainsi. On associe à une permutation $p\in S_{n}$ l'entier $n_{p}=rang(p)$, son rang dans l'ordre lexicographique de classement de toutes les permutations. Il faut construire les fonctions calculant le rang, et leurs inverses calculant la permutation associée à un entier donné.

Compte-tenu du total nul, le flip $u=(u_{1},\ldots ,u_{8})$ est représenté par l'entier $f_{u}=\sum _{1}^{7}u_{i}2^{i-1}$, et le twist est représenté par l'entier $t_{v}=\sum _{1}^{11}v_{i}3^{i-1}$ (bases 2 et 3). Donc le vecteur de coordonnées du mouvement $m=(p,u,r,v)$ est $coord(m)=(n_{p},f_{u},n_{r},t_{v})$. Les tailles maximales de ces entiers sont les constantes

$NPCA=12!=479001600,\quad NPCS=8!=40320,\quad NFLIP=2^{11}=2048,\quad NTWIST=3^{7}=2187$

Rubik's cube : algorithmes optimaux, sous-groupes

La recherche d'algorithmes de reconstruction optimaux (minimum de mouvements) a été entamée par le mathématicien anglais Thistlethwaite en 1981. Il utilise une démarche de décomposition du groupe en quatre sous-groupes $G\supset G_{1}\supset G_{2}\supset G_{3}\supset G_{4}=\{I\}$, en se limitant successivement à des carrés (demi-tours) sur les paires de faces opposées $FB,LR,UD$. Par exploration successive des classes à droite de ces sous-groupes $G_{i+1}\diagdown G_{i}$, il construit des tables de calcul permettant la résolution complète par une manœuvre de longueur maximale 52. Il bornait ainsi le diamètre du groupe de Rubik, c'était le début de la course pour déterminer ce diamètre et obtenir l' Algorithme de Dieu permettant, pour tout état du cube, de calculer le mouvement minimal de reconstruction. La description de cet algorithme est donnée ici.

L'algorithme à deux phases de Kociemba

Cet algorithme a été élaboré en 1992. Il utilise la sous-suite de Thistlethwaite $G\supset G_{2}\supset G_{4}=\{I\}$,avec le sous-groupe $G_{2}=<U,D,L^{2},R^{2},F^{2},B^{2}>$.

Kociemba utilise la caractérisation du groupe intermédiaire $G_{2}$ : il n'y a ni flip ni twist, et les CA de la tranche du milieu $UD$ y restent, on la notera $T_{ud}$. Donc

$e=(p,u,r,v)\in G_{2}\quad \Leftrightarrow \quad u=0,\;v=0,\;p(T_{ud})=T_{ud}$

La phase 1 consiste à ramener un état quelconque $g\in G$, par un mouvement $x\in G$, à un état $g_{2}\in G_{2}$. On a $g=g_{2}x^{-1}\in G_{2}x$, on travaille donc dans l'ensemble des classes à droite (right cosets en anglais) modulo $G_{2}$ : ensemble noté $G_{2}\diagdown G$.

Une classe est déterminée par un triplet $(p_{ud},u,v)$ et les coordonnées associées $(n_{ud},f_{u},t_{v})$ avec

• Tranche UD : $p_{ud}=(1<=i_{1}<i_{2}<i_{3}<i_{4}<=12)$, images de $T_{ud}$. Il y en a 412, la coordonnée est le rang dans la liste $n_{ud}\in [0..411]$
• Flip $u\in \mathbb {Z} _{2}^{11}$, coordonnée $f_{u}\in [0..2047]$,
• Twist $v\in \mathbb {Z} _{3}^{7}$, coordonnée $t_{v}\in [0..2186]$.

La taille de $G_{2}\diagdown G$ est donc $N_{1}=NFLIP\times NUD\times NTWIST=2217093120\sim 2.2\times 10^{9}$.

La phase 2 résout le groupe $G_{2}$. Un état est représenté par un triplet $(p_{cs},p_{ud},p_{sl})$ et les coordonnées associées $(n_{cs},n_{ud},n_{sl})$ avec

• Permutation CS : $p_{cs}\in \mathbb {Z} _{3}^{7}$, coordonnée $n_{cs}\in [0..40319]$
• Permutation CA de $T_{ud}$ : $p_{ud}\in S_{4}$, coordonnée $n_{ud}\in [0..23]$,
• Permutation CA hors $T_{ud}$ : $p_{sl}\in S_{8}$, coordonnée $n_{ud}\in [0..40319]$.

avec la contrainte de Signature totale=1. La taille de G2 est donc $N_{2}=8!8!4!/2=19508428800\sim 19\times 10^{9}$.

L'algorithme Cube Explorer réalise ces deux phases, soit de façon rapide sous-optimale, soit de façon exhaustive optimale et plus lente. Il retourne, pour tout état du cube, une manœuvre de résolution en général de longueur inférieure à 20. La version initiale de 1992 était sous-optimale et donnait en général des manœuvres de taille inférieure à 23 (mais pas de borne effective prouvée).

L'algorithme optimal (à deux phases) de Reid

La grande étape suivante, vers l'algorithme de Dieu, a été franchie par Michael Reid en 1997. Il implémente l'algorithme à deux phases de Kociemba, en utilisant une réduction de l'espace de recherche par utilisation de classes d'équivalence (des états ou classes à droite) par les 16 symétries du cube respectant l'axe U-D.

Reid optimal, phase 1

Pour ce faire, il utilise dans la phase 1, une fusion des deux coordonnées $(permUD=n_{ud},flip=n_{u})$, en une coordonnée unique $cl_{fud}\in [0..64429]$, représentant les classes de symétrie des couples (permUD,flip).

Un élément de $G_{2}\diagdown G$ est donc représenté par les coordonnées de symétrie (classe FLIPUD, twist)=$(cl_{fud},t_{v})$. La taille de l'espace à explorer est donc réduite à

$NSYMG1=NFLIPUD\times NTWIST=140908410$

avec NUDSLICE=64430 (*---Nombres de classes de symétrie de FLIP-UDslice--*).

Reid optimal, phase 2

Dans cette phase d'exploration complète du groupe G2, on calcul les classes d'équivalence de symétries et inversions des permutations de CS. Il reste 1672 classes. Les classes de symétrie de G2 sont représentées par un triplet de coordonnées $(cl,u,s)$ avec

• Classe de permutation des CS : $\quad cl\in [0..1671]$
• Permutation des CA hors $T_{ud}:\quad u\in [0..40319]$
• Permutation signée des CA de $T_{ud}:\quad s\in [0..11]$

La taille de l'espace des classes à explorer est donc

$NSYMG2=1672\times 40319\times 12=808980480$

Diamètre du cube et algorithme de Dieu

Puisque le groupe G est fini, il existe pour tout état g une manœuvre de taille minimale (nombre de mouvements élémentaires) qui le ramène à l'état initial $R_{0}$. Cette taille minimale est appelée la distance $d(g,R_{0})$. Le diamètre du groupe G est $d(G)=\max(d(g,R_{0}),g\in G)$.

Le diamètre est inférieur ou égal à 29

Par exploration exhaustive des deux espaces réduits de l'algorithme optimal défini ci-dessus, Mike Reid a établi en 1995 que toutes les classes sont résolues par un mouvement de taille maximale 29.

Le superflip est à distance 20 !

En recherchant de façon exhaustive des solutions dans l'algorithme optimal à deux phases, Reid démontre le premier, le 18 Janvier 1995, que le ''superflip'' (état du cube où tous les CS sont bien placés et orientés, tous les CA sont bien placés et ''flipés'') est à distance minimale 20 du cube initial. Il prouve ainsi que le diamètre du groupe G est supérieur ou égal à 20. Il n'y a pas de mouvement plus court que celui donné au début de l'article, pour réaliser le superflip.

Le diamètre est 20

La recherche de l'algorithme de Dieu et du diamètre effectif du groupe G s'est poursuivie de façon continue après 1995, alliant l'augmentation de puissance et taille mémoire des ordinateurs, l'amélioration de l'analyse mathématique du groupe et des algorithmes de recherche. Elle s'est conclue en Juillet 2010, par la démonstration du résultat fondamental :

Le diamètre du groupe de Rubik $R_{3}$ est 20

Ce résultat a été obtenu par un travail conjoint de Tomas Rokicki, Herbert Kociemba, Morley Davidson et John Dethridge. Il a nécessité un temps de calcul de 35 années-CPU, réparti sur un vaste réseau de machines. Il ne donne pas cependant l'algorithme de Dieu, car le programme a cherché pour tous les états (répartis en 2 217 093 120 ensembles de 19 508 428 800 positions chacun) une solution de taille inférieure ou égale à 20, et non une solution optimale.

Ainsi, le meilleur calcul des mouvements de taille minimale pour résoudre une position est donné par l'algorithme Cube Explorer , ou l'algorithme de Reid qui en est une variante antérieure. Ils sont sous-optimaux dans G, car ils utilisent une optimisation séparée en deux phases liées au sous-groupe G2 (mais aussi à ses variantes obtenues par les tranches LR et FB).

Livres et sites sur les mathématiques du cube

• Notes on Rubik's magic cube, David Singmaster. Enslow Pub Inc, 1981 (ISBN 0-8949-0043-9)
• Handbook of Cubik Math, David Singmaster and Alexander Frey. The Lutterworth Press, 1987 (ISBN 0-7188-2555-1)
• http://fan2cube.fr/rubikmaths1.php

Catégorie:Algorithmique Catégorie:Rubik's Cube Catégorie:Théorie des groupes