Chaine de Markov et Python

a marqué ce sujet comme résolu.

Bonsoir,

Dans le cadre d’un projet, je souhaite répondre à la problématique suivant : en combien de coups, en mélangeant un Rubik’s Cube 2x2x2 de façon aléatoire, peut-on le considérer mélangé ? Il a déjà été démontré que 7 coups suffisent pour mélanger un jeu de 52 cartes (en définissant bien ce qu’est un coup).Je me suis appuyé notamment sur ce document. J’ai donc pensé à reprendre cette étude mais en l’adaptant à mon problème. J’ai vu qu’on pouvait utiliser les chaines de Markov pour cela , et j’ai donc penser à réaliser le traitement avec la matrice de transition sur Python. Seulement voilà mon problème, cette matrice fait la taille du cardinal de l’ensemble des positions possibles du 2x2x2 soit environ 3 millions. J’ai donc eu beaucoup de problème de mémoire et de temps de calcul. Finalement j’ai à peu près réussi à la générer, mais il me faudrait maintenant la mettre à une puissance suffisante pour pouvoir analyser les résultats (j’estime cette puissance à environ 20 ou 30). Sachant que sous Python j’ai des erreurs mémoire pour une aussi grande matrice, je n’arrive plus à avancer.

Je voudrais donc savoir si vous auriez des idées pour réaliser cette étude, peut-être repartir de zéro avec une autre théorie, mais j’ai quand même pas mal bossé sur celle-ci et j’ai l’impression de pas être si loin du but. J’espère avoir été clair, si vous avez besoin de plus d’information pour m’aider, n’hésitez pas.

Salut,

Ça ne me parait pas super tractable comme solution, surtout que c’est un problème facilement solvable par dénombrement. On sait qu’il faut maximum 14 quarts de tours (ou 11 mouvements si on compte qu’un demi-tour n’est qu’un mouvement) pour résoudre le cube. 14 quarts de tour suffisent donc à le mélanger.

Banni

@adri1 : Si j’ai bien compris, il faut qu’à partir de n’importe quelle position, effectuer $n$ coups au hasard donne une probabilité proche de l’uniforme. On sait donc qu’il faut au moins 14 coups, mais c’est peut-être plus.

Pour élever ta matrice à la puissance 32, tu peux simplement élever au carré 5 fois de suite. L’élévation au carré ne prend «que» le double de la mémoire requise pour ta matrice initiale. C’est peut-être gérable en procédant par blocs et en stockant le reste (les blocs déjà traités ou à traiter) sur le disque dur ? Peut-être qu’un langage prévu pour ça (Octave) sait gérer un truc pareil ?

J’imagine que ta matrice est plutôt dense ?

Autrement, il n’y a pas moyen de travailer à isomorphisme près ? De considérer que deux solutions sont équivalentes si on peut passer de l’une à l’autre par permutation des couleurs ?

EDIT : autre idée = essayer de diagonaliser la matrice avec un soft de calcul scientifique, et voir si ça passe… Si oui, tu pourras élever ta matrice diagonale à la puissance que tu veux sans souci, puis reconvertir dans la base canonique, quitte à laisser ton ordi tourner toute la nuit…

+0 -0
Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte