l'Algorithme de Thistlethwaite pour un Humain
Publié : Jeu 27/05/2021 13:41
Morwen Thistlethwaite
Vous avez peut-être entendu parler de l'algorithme de Thistlethwaite, et si vous le cherchez sur internet mais alors c'est vraiment mal expliqué ...
Voyons un peu:
Tout se passe vers les années 1980-1981, on s'est intéressé par la question suivante:
-Quel est le nombre maximum de rotations (nécessaire) pour restaurer le Rubik's Cube à partir d'un état quelconque ?
Soit m le nombre de rotations maximum nécessaire, m est alors compris entre a=minimum et b=maximum
a ≤ m ≤ b
il y a des états qu'on ne peut pas s'en sortir avec moindre de a rotations, a est minimum, en cherchant un peu par l'ordinateur
on trouve a=26 càd il y a des états qu'on ne peut pas restaurer le Cube avec 25 rotations ! par ex l'état SuperFlip4Spot, longueur=26.
donc 26 ≤ m ≤ b
il faut prend b = maximum nécessaire car si on prend b = 65256 c'est bien mais c'est beaucoup trop ...
C'est Thistlethwaite qui apportait une valeur raisonnable de b.
Pour cela il utilisait les groupes !!!
à chaque tour H de sous groupes de M (le groupe des formules) on associe une tour de sous ensembles E de G (ensemble des états) .
Thistlethwaite proposait la tour suivante:
H0 = M = <H,B,A,P,G,D> ==> E0 = G
H1 = <H,B,A²,P²,G,D> ==> E1
H2 = <H,B,A²,P²,G²,D²> ==> E2
H3 = <H²,B²,A²,P²,G²,D²> ==> E3
H4 = {I} ==> E4 = {e} e=état résolu
Et il démontrait que :
0) ∀s=s0∈E0 ∃V0∈H0 et |V0| ≤ 14 telle que s0•V0 = s1∈E1
1) ∀s1∈E1 ∃V1∈H1 et |V1| ≤ 26 telle que s1•V1 = s2∈E2
2) ∀s2∈E2 ∃V2∈H2 et |V2| ≤ 30 telle que s2•V2 = s3∈E3
3) ∀s3∈E3 ∃V3∈H3 et |V3| ≤ 34 telle que s3•V3 = e
e état résolu
on pose
V = V0V1V2V3
et
s.V = e
donc au maximum b = 14+26+30+34 = 104 rotations
Ce que Thistlethwaite prouve :
1) On peut toujours restaurer le Cube à partir de n'importe quel état.
2) Le nombre maximum de rotations dans la résolutions serait 104.
Durant les années on diminue b et finalement en 2014 , b=26, autrement dit on restaure le Rubik's Cube au maximum 26 rotations.
On dit que le diamètre du Rubik's Cube est 26.
La méthode de Thistlethwaite donne un algorithme de résolution (à 4 étapes) .
Le problème de cet algorithme est que les formules Vi sont trouvées par l'ordinateur.
Lorsqu'on change s , Vi change !!! s étant donné, l'ordinateur cherche V0 parmi 43 252 003 274 489 856 000 formules !
avec un peu d'astuce il cherche V0 parmi 2048 formules et une plus courte (il y a beaucoup de plus courtes formules) , tout cela est impossible pour un être humain.
L'algorithme de Thistlethwaite (AT) est un algorithme théorique, il est pratiquement impossible
qu'un être humain peut l'appliquer sur un état quelconque s, seuls les ordinateurs peuvent le faire.
L' AT se décompose en 4 étapes et à chaque étape la formule utilisée Vi doit
vérifier un certains nombre de contraintes.
étape 0 = Orienter les arêtes : V0 dans <H,B,A,P,G,D> et |V0| <= 14
étape 1 = Orienter les sommets : V1 dans <H,B,A²,P²,G,D> et |V1| <= 26
étape 2 = Placer les sommets : V2 dans <H,B,A²,P²,G²,D²> et |V2| <= 30
étape 3 = Placer les arêtes : V3 dans <H²,B²,A²,P²,G²,D²> et |V3| <= 34
V = V0.V1.V2.V3 ===> |V| <= 104
s•V = e
Pour un état quelconque s, l'ordinateur fournit les Vi, il est pratiquement impossible
qu'un être humain trouve les Vi manuellement.
Par contre si l'état s est particulier, il est possible qu'on trouve les Vi manuellement
en raisonnant un peu.
Voici deux exemple :
==================
1) L'état particulier t1:
t1 = (HAG)+(HDA)-(BAD)+(BGA)-
(HG)+(HD)+(BD)+(BG)+
(t1 = B² P² G² B' P² G² P² H G² P² B G² A' H² G' A' G' P' D' P' D' B)
algorithme:
V0 = G H B' P² D² A G². (10)
V1 = P² H B' G B² G D² B D' B² D B D. (17)
V2 = H' A² B' A² P² B² P² H' G² H P² H'. (19)
V3 = H² B² D² B² G² B² P² A² D² A² B² A² B² A² (28)
V = V0.V1.V2.V3 ===> |V| = 74
t1•V = e
-------------
2) L'état particulier t2:
t2 = 4 sommet-avant+
4 sommet-postérieur-
12 arêtes inversées
(t2 = P² G² A² G² B' P² B' A² H² G² P B' G² P G' A' H D' B G² A' G')
algorithme:
V0 = P D G A B' H' P. (7)
V1 = H² G² P² G H² B² G' B' D B² D' B' D'. (19)
V2 = H² D² A² H A² G² H² G² H' D² H D² H'. (22)
V3 = B² A² B² P² G² A² D² P² G² D² H² D² H² D² (28)
V = V0.V1.V2.V3 ===> |V| = 76
t2•V = e
=================
Vers les années 2002, Ryan Heise a une idée de convertir l'AT (Algorithme de Thistlethwaite) en un ATH (Algorithme de Thistlethwaite Humain), mais alors il a vraiment un esprit tordu !! compliqué !!
On ne comprend pratiquement rien de ses explications !!! ce qui fait que l'exécution de son algorithme est vraiment tiré par les cheveux ...
Puis quelques années plus tard en 2008 une autre personne reproduisait l'ATH de Ryan Heise en vidéo, mais lui aussi, a un esprit tordu !!
au lieu de filmer par derrière (le caméra est derrière lui) il laisse le caméra devant lui, ce qui fait que les repérages des rotations
sont tous renversés !! parfois il tords ses mains pour montrer les rotations !!!
et ses explications sont comme Ryan Heise, compliqués incompréhensibles ....
Et pour tant les choses ne sont pas incompréhensibles et si compliquées que ça ......
Vous avez peut-être entendu parler de l'algorithme de Thistlethwaite, et si vous le cherchez sur internet mais alors c'est vraiment mal expliqué ...
Voyons un peu:
Tout se passe vers les années 1980-1981, on s'est intéressé par la question suivante:
-Quel est le nombre maximum de rotations (nécessaire) pour restaurer le Rubik's Cube à partir d'un état quelconque ?
Soit m le nombre de rotations maximum nécessaire, m est alors compris entre a=minimum et b=maximum
a ≤ m ≤ b
il y a des états qu'on ne peut pas s'en sortir avec moindre de a rotations, a est minimum, en cherchant un peu par l'ordinateur
on trouve a=26 càd il y a des états qu'on ne peut pas restaurer le Cube avec 25 rotations ! par ex l'état SuperFlip4Spot, longueur=26.
donc 26 ≤ m ≤ b
il faut prend b = maximum nécessaire car si on prend b = 65256 c'est bien mais c'est beaucoup trop ...
C'est Thistlethwaite qui apportait une valeur raisonnable de b.
Pour cela il utilisait les groupes !!!
à chaque tour H de sous groupes de M (le groupe des formules) on associe une tour de sous ensembles E de G (ensemble des états) .
Thistlethwaite proposait la tour suivante:
H0 = M = <H,B,A,P,G,D> ==> E0 = G
H1 = <H,B,A²,P²,G,D> ==> E1
H2 = <H,B,A²,P²,G²,D²> ==> E2
H3 = <H²,B²,A²,P²,G²,D²> ==> E3
H4 = {I} ==> E4 = {e} e=état résolu
Et il démontrait que :
0) ∀s=s0∈E0 ∃V0∈H0 et |V0| ≤ 14 telle que s0•V0 = s1∈E1
1) ∀s1∈E1 ∃V1∈H1 et |V1| ≤ 26 telle que s1•V1 = s2∈E2
2) ∀s2∈E2 ∃V2∈H2 et |V2| ≤ 30 telle que s2•V2 = s3∈E3
3) ∀s3∈E3 ∃V3∈H3 et |V3| ≤ 34 telle que s3•V3 = e
e état résolu
on pose
V = V0V1V2V3
et
s.V = e
donc au maximum b = 14+26+30+34 = 104 rotations
Ce que Thistlethwaite prouve :
1) On peut toujours restaurer le Cube à partir de n'importe quel état.
2) Le nombre maximum de rotations dans la résolutions serait 104.
Durant les années on diminue b et finalement en 2014 , b=26, autrement dit on restaure le Rubik's Cube au maximum 26 rotations.
On dit que le diamètre du Rubik's Cube est 26.
La méthode de Thistlethwaite donne un algorithme de résolution (à 4 étapes) .
Le problème de cet algorithme est que les formules Vi sont trouvées par l'ordinateur.
Lorsqu'on change s , Vi change !!! s étant donné, l'ordinateur cherche V0 parmi 43 252 003 274 489 856 000 formules !
avec un peu d'astuce il cherche V0 parmi 2048 formules et une plus courte (il y a beaucoup de plus courtes formules) , tout cela est impossible pour un être humain.
L'algorithme de Thistlethwaite (AT) est un algorithme théorique, il est pratiquement impossible
qu'un être humain peut l'appliquer sur un état quelconque s, seuls les ordinateurs peuvent le faire.
L' AT se décompose en 4 étapes et à chaque étape la formule utilisée Vi doit
vérifier un certains nombre de contraintes.
étape 0 = Orienter les arêtes : V0 dans <H,B,A,P,G,D> et |V0| <= 14
étape 1 = Orienter les sommets : V1 dans <H,B,A²,P²,G,D> et |V1| <= 26
étape 2 = Placer les sommets : V2 dans <H,B,A²,P²,G²,D²> et |V2| <= 30
étape 3 = Placer les arêtes : V3 dans <H²,B²,A²,P²,G²,D²> et |V3| <= 34
V = V0.V1.V2.V3 ===> |V| <= 104
s•V = e
Pour un état quelconque s, l'ordinateur fournit les Vi, il est pratiquement impossible
qu'un être humain trouve les Vi manuellement.
Par contre si l'état s est particulier, il est possible qu'on trouve les Vi manuellement
en raisonnant un peu.
Voici deux exemple :
==================
1) L'état particulier t1:
t1 = (HAG)+(HDA)-(BAD)+(BGA)-
(HG)+(HD)+(BD)+(BG)+
(t1 = B² P² G² B' P² G² P² H G² P² B G² A' H² G' A' G' P' D' P' D' B)
algorithme:
V0 = G H B' P² D² A G². (10)
V1 = P² H B' G B² G D² B D' B² D B D. (17)
V2 = H' A² B' A² P² B² P² H' G² H P² H'. (19)
V3 = H² B² D² B² G² B² P² A² D² A² B² A² B² A² (28)
V = V0.V1.V2.V3 ===> |V| = 74
t1•V = e
-------------
2) L'état particulier t2:
t2 = 4 sommet-avant+
4 sommet-postérieur-
12 arêtes inversées
(t2 = P² G² A² G² B' P² B' A² H² G² P B' G² P G' A' H D' B G² A' G')
algorithme:
V0 = P D G A B' H' P. (7)
V1 = H² G² P² G H² B² G' B' D B² D' B' D'. (19)
V2 = H² D² A² H A² G² H² G² H' D² H D² H'. (22)
V3 = B² A² B² P² G² A² D² P² G² D² H² D² H² D² (28)
V = V0.V1.V2.V3 ===> |V| = 76
t2•V = e
=================
Vers les années 2002, Ryan Heise a une idée de convertir l'AT (Algorithme de Thistlethwaite) en un ATH (Algorithme de Thistlethwaite Humain), mais alors il a vraiment un esprit tordu !! compliqué !!
On ne comprend pratiquement rien de ses explications !!! ce qui fait que l'exécution de son algorithme est vraiment tiré par les cheveux ...
Puis quelques années plus tard en 2008 une autre personne reproduisait l'ATH de Ryan Heise en vidéo, mais lui aussi, a un esprit tordu !!
au lieu de filmer par derrière (le caméra est derrière lui) il laisse le caméra devant lui, ce qui fait que les repérages des rotations
sont tous renversés !! parfois il tords ses mains pour montrer les rotations !!!
et ses explications sont comme Ryan Heise, compliqués incompréhensibles ....
Et pour tant les choses ne sont pas incompréhensibles et si compliquées que ça ......
