l'Algorithme de Thistlethwaite pour un Humain

Les articles autour des twists
Avatar de l’utilisateur
morphocode
Megaminx
Megaminx
Homme
Balance
Messages : 654
Inscription : Lun 25/11/2013 17:06
Localisation : Paris
Contact :

l'Algorithme de Thistlethwaite pour un Humain

Message non lupar morphocode » Jeu 27/05/2021 13:41

Vous avez peut-être entendu parler de l'algorithme de Thistlethwaite, et si vous le chercher 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 necessaire, m est alors compris entre a=minimal et b=maximal
a ≤ m ≤ b
il y a des états qu'on ne peut pas s'en sortir avec moindre de a rotations, a est minimum, on 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 nessesaire car si on prend b = 65256 c'est bien mais c'est trop ...
C'est Thistlethwaite qui apportait une valeur raisonnable de b.
Pour cela il utilisait les groupes !!!

à chaque tour H de sous groupe de M (le groupe des formule) on associe une tour de sous ensemble E de G (ensemble des états) .
Thistlethwaite proposait la tour suivante:
M = <H,B,A,P,G,D> ==> G
M ⊃ H1 = <H,B,A²,P²,G,D> ==> E1 ⊂ G
H1 ⊃ H2 = <H,B,A²,P²,G²,D²> ==> E2 ⊂ E1
H2 ⊃ H3 = <H²,B²,A²,P²,G²,D²> ==> E3 ⊂ E2
H3 ⊃ H4 = {I} ==> E4 = {e} état résolu ⊂ E3

Il démontrait que :
1) ∀s∈G ∃V∈M tel que s•V = t1∈E1
càd pour passer de G à E1 on utilise V, et le maxi |V| = 14
2) ∀t1∈E1 ∃V1∈H1 tel que t1•V1 = t2∈E2
càd pour passer de E1 à E2 on utilise V1, et le maxi |V1| = 26
3) ∀t2∈E2 ∃V2∈H2 tel que t2•V2 = t3∈E3
càd pour passer de E2 à E3 on utilise V2, et le maxi |V2| = 30
4) ∀t3∈E3 ∃V3∈H3 tel que t3•V3 = t4∈E4 , t4=e état résolu
càd pour passer de E3 à l'état résolu on utilise V4, et le maxi |V4| = 34

donc au total 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) car on part d'un état mélangé s et on arrive à l'état résolu e.
Le problème de cet algorithme est que les formules Vi sont trouvées par ordinateur.
Lorsqu'on change s , V1 change !!! s étant donné l'ordinateur cherche V1 parmi 43 252 003 274 489 856 000 formules !
avec un peu d'astuce il cherche V1 parmi 2048 formules et la plus courte , tout celà est impossible pour un être humain.

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 toudu !! compliqué !!
On ne comprend pratiquement rien de ses explications !!! ce qui fait que l'execution de son algorithme est vraiment tiré par les cheveux ...
Puis quelque année plus tard en 2008 une autre personne disons Solotop, Solotop reproduit 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 répèrages des rotations
sont tous renversés !! parfois il tords les mains pour montrer les rotations !!!
et ces explications sont comme Ryan Heise, compliqués incompréhensibles ....
Et pour tant , les explications serons compréhensibles si on nous répond 3 questions ci-dessous:

-Q1: Quel est le but de premier étape ? (et pourquoi?)
-Q2: Quelle sont les rotations autorisée (et pourquoi?) dans les formules ?
-Q3: Quel sont les formules utilisées ?


-Q1: Quel est le but du deuxième étape ? (et pourquoi?)
-Q2: Quelle sont les rotations autorisée (et pourquoi?) dans les formules ?
-Q3: Quel sont les formules utilisées ?

....

Et pour tant les choses ne sont pas incompréhensible et si compliquée que ça ......
Image

Avatar de l’utilisateur
morphocode
Megaminx
Megaminx
Homme
Balance
Messages : 654
Inscription : Lun 25/11/2013 17:06
Localisation : Paris
Contact :

Re: l'Algorithme de Thistlethwaite pour un Humain

Message non lupar morphocode » Jeu 27/05/2021 13:50

Voici ma version de l'Algorithme de Thistlethwaite pour un Humain.
Voyons la version origine pour l'ordinateur:
Algorithme:
M = <H,B,A,P,G,D> ==> 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} état résolu

Analyse de l'algorithme :
Algorithme se fait en 4 étapes:

étape 1 : Orienter toutes les arêtes.
=====================================
==> Cet étape nous dit qu'il faut orienter toutes les arêtes, en effet (à l'arrivé E1) les rotations {H,B,A²,P²,G,D} ne modifient pas
les orientations des arêtes, pour voir cela on doit connaitre la table des marquages et l'ordre des couleurs.
d'après la table des marquages et les couleurs dominantes on voit que les rotations H,B,G,D ne changent pas les orientations des arêtes,
seules les rotations A et P changent, mais si on fait A² ou P² les orientations reviennent à l'état initial donc A², P² ne changent pas non plus
les orientations des arêtes.
E1 est donc l'ensemble des états dont les arêtes sont bien orientées.

==> Donc pour passer de G à E1, il suffit de trouver une formule qui pivote 2 arêtes et la formule peut utiliser toutes les rotations de base
car on est dans G (==> formules dans M)
Ici on fait en 2 étapes:

a) Pivoter les 2 arêtes:
θ = (A[DH]A'H)
(HG)°(HP)° = θ²

b) Glisser les arêtes-équateur dans l'équateur (tranche d):
(HG)->(AD) = DH (D²H²)3H'D'
(HG)->(PD) = D'H (D²H²)3H'D

Le problème dans cet étape, c'est qu'il faut reconaitre les arêtes mal orientées !! ce qui n'est pas évident lorsqu'elles ne sont
pas dans leur emplacement origine (à l'état résolu).
Il faut donc connaitre par coeur la table des marquages et les couleurs dominantes.

Rappel: On fixe le Cube c'est-à-dire définir le Haut, le Bas, ... voici le marquage des facettes (à connaitre par coeur)
Image
couleur dominante :
L'ordre des couleurs : blanc > jaune > vert > klein > orange > rouge


étape 2 : Orienter toutes les sommets.
======================================
==> Cet étape nous dit qu'il faut orienter tous les sommets, en effet (à l'arrivé E2) les rotations {H,B,A²,P²,G²,D²} ne modifient pas
les orientations des sommets.
d'après la table des marquages et les couleurs dominantes on voit que les rotations H,B ne changent pas les orientations des sommets,
seules les rotations A,P,G,D changent, mais si on fait A²,P²,G²,D² les orientations reviennent à l'état initial donc A²,P²,G²,D² ne changent pas non plus
les orientations des sommets.
E2 est donc l'ensemble des états dont les arêtes sont bien orientées et les sommets sont bien orientés.

==> Donc pour passer de E1 à E2, il suffit de trouver une formule qui oriente les sommets (sans toucher les orientations des arêtes, si non on détruirait de ce qu'on a fait)
et la formule doit utiliser seulement les rotations <H,B,A²,P²,G,D>
car on est dans E1 (==> formules dans H1)
En voici une formule:
Pivoter les sommets
(HGP)- (HAG)+ = [DH]² G'[HD]²G

Là aussi , le problème dans cet étape, c'est qu'il faut reconaitre les sommets mal orientés !! mais ce n'est pas bien difficile
quand on connait par coeur la table des marquages et les couleurs dominantes.


étape 3 : Placer toutes les sommets.
======================================
==> Cet étape nous dit qu'il faut placer tous les sommets, en effet (à l'arrivé E3) les rotations {H²,B²,A²,P²,G²,D²} ne modifient pas
les orientations des arêtes, ni les orientations des sommets.
E3 est donc l'ensemble des états dont les arêtes sont bien orientées et les sommets sont bien rangés.

==> Donc pour passer de E2 à E3, il suffit de trouver une formule qui place les sommets (sans toucher les orientations des arêtes ni les orientations des sommets, si non on détruirait de ce qu'on a fait)
et la formule doit utiliser seulement les rotations <H,B,A²,P²,G²,D²>
car on est dans E2 (==> formules dans H2)
Ici on a besoin deux formules :
a) Ranger les sommets-Bas
(HDA)->(BAD) = A²H'A²HA²
b) Ranger les sommets-Haut
(HDA)<->(HPD) = D²H(D²H')² .B D²H'D²HD² .B'


étape 4 : Placer toutes les arêtes.
======================================
==> Cet étape nous dit qu'il faut placer tous les arêtes, en effet (à l'arrivé E4) la rotation {I} laisse le Cube invariant
E4 est donc l'état résolu.

==> Donc pour passer de E3 à E4, il suffit de trouver une formule qui place les arêtes
(sans toucher les orientations des arêtes ni les orientations des sommets et ne déplace pas les sommets, si non on détruirait de ce qu'on a fait)
et la formule doit utiliser seulement les rotations <H²,B²,A²,P²,G²,D²>
car on est dans E3 (==> formules dans H3)
Ici on a besoin 3 formules :

a) Ranger les arêtes-Bas :
(HD)->(BD) = B²A²B² (D²P²)3 B²A²B²

b) Ranger les arêtes-équateur :
(AD)<->(PD) = (D²H²)3

c) Ranger les arêtes-Haut:
(HG)->(HD)->(BD) = B²A²G²A²B²P²D²P²
(HA,HP)(HG,HD) = G²A²B² (D²P²)3 B²A²G²
Image

Avatar de l’utilisateur
morphocode
Megaminx
Megaminx
Homme
Balance
Messages : 654
Inscription : Lun 25/11/2013 17:06
Localisation : Paris
Contact :

Re: l'Algorithme de Thistlethwaite pour un Humain

Message non lupar morphocode » Dim 30/05/2021 12:00

Voici un résumé
Image
Image

Avatar de l’utilisateur
morphocode
Megaminx
Megaminx
Homme
Balance
Messages : 654
Inscription : Lun 25/11/2013 17:06
Localisation : Paris
Contact :

Re: l'Algorithme de Thistlethwaite pour un Humain

Message non lupar morphocode » Lun 31/05/2021 09:09

Commentaires
============
Il y a des différences entre l'AT et l'ATH

1) à l'étape 1 par ex, dans l'AT la formule V oriente toutes les mauvaises arêtes en même temps ! alors que dans l'ATH la formule θ² pivote seulement deux arêtes ce qui fait que pour pivoter toutes les mauvaises arêtes il faut utiliser les conjugaisons Xθ²X' (X=formule) donc au final on aura une grosse grosse formule : C = θ² Xθ²X' Yθ²Y' ...
2) Si on change s, V change, alors que dans l'ATH on utilise toujours θ² (mais les conjugés changent, les X changent)
3) l'ordinateur trouve V minimal , mais C n'est pas minimal .
Image