Chaîne de Markov et Python

[invite31e4232f]

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.
-----

[invite1c6b0acc]

Bonsoir,

cette matrice fait la taille du cardinal de l’ensemble des positions possibles du 2x2x2 soit environ 3 millions.

Il y a 8 pièces.
Pour la première, 8 position, pour la deuxième, 7, ... C'est à dire 7! = 40320 positions en tout.

Donc, tu ne doit pas parler du Rubik’s Cube 2x2x2 ...

[invite31e4232f]

C'est un peu plus compliqué que ca, il faut prendre en compte les orientations de chaque pièce. On trouve facilement (par toi même ou sur le net) ce chiffre de 3 millions environ.

[invite1c6b0acc]

Ah oui, pardon, chaque pièce a 3 orientations, c'est vrai.
Désolé.

[A voir en vidéo sur Futura]

[inviteeecca5b6]

Hello,

Quand tu dis que la matrice a une taille de 3 millions, c'est 3 millions x 3 millions ?

Après, étant donné (si j'ai bien compris) que c'est une matrice de changements d'états et que les états sont somme toute en nombre très limités, la matrice doit avoir peu d'éléments non nuls (puisque partant d'une position donnée tu ne peut prendre que N nouvelles positions).

A mon avis, si tu utilises les matrices "sparses", tu ne devrais plus avoir de problème de mémoire.
https://docs.scipy.org/doc/scipy-0.1...ce/sparse.html

[invite31e4232f]

Oui c'est une matrice 3 millions x 3 millions. J'ai bien essayé de prendre une matrice dans le module sparse mais le soucis c'est la matrice est creuse au debut mais est censée tendre vers une matrice avec tous les coefficients non nuls puisqu'on se rapproche de l'uniformité. Il me faudrait donc pouvoir mettre une matrice à une puissance suffisante sans compter sur le fait qu'elle soit pleine de zéro ou non.

[inviteeecca5b6]

Ok je vois, tu listes tous les états possibles à chaque instant, ce qui en général est juste... infaisable.

A mon avis, tu pourrais utiliser une approche quasi identique d'un point de vue théorique avec une marche aléatoire répétée... Ca ajoute forcement l'aspect stochastique mais puisque tu ne peux pas lister tous les états possibles, avec suffisamment de répétitions tu arriverais à une estimation assez solide.

Si tu veux vraiment jouer avec la grosse matrice, tu peux essayer les techniques de memory mapping
https://docs.python.org/2/library/mmap.html

Il faut voir s'il existe des fonctions dédiées à ce genre de techniques, et surtout ça va énormément ralentir les calculs à tels point que tu n'auras peut-être pas la réponse de ton vivant

[invite6c250b59]

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.

Le problème est intéressant et le défi aussi. Personnellement je crois que tu peux continuer dans cette voie au prix d'un peu de travail sur tes fonctions sans que le coût en temps devienne impossible. Je suppose que la fonction qui te manque le plus est la multiplication de matrice. Ce que tu pourrais faire, c'est remplacer la fonction numpy par une autre fonction spécialement adapté à la limitation de ton hardware.

Exemple: supposons que tu as (en mémoire morte) deux matrices de 100*100=10000 éléments, et que ta mémoire vive ne te permet qu'un millier, et que tu as besoin de les multiplier quand même. Tu peux 1) changer le codage de tes matrices pour les remplacer par un codage de lignes et de colonne (cela double l'espace disque, mais l'espace disque n'est pas un problème dans ton cas) 2) définir une nouvelle fonction qui va diviser le travail de multiplication en plusieurs étapes et ne charger que les données nécessaires pour chaque étape (c'est pour cela que c'est utile de changer l'adressage des matrices en un adressage de lignes/colonnes). En pseudocode pour une multiplication de matrice cela donnerait quelque chose comme:
1) divise la matrice résultat en b blocs en fonction de la mémoire vive disponible et de la taille des matrices a multiplier
2) pour chaque bloc
a- charge les n lignes de la matrice 1 nécessaires au calcul du bloc en cours
b- charge les n colonnes de la matrice 2 blabla (dans l'espace mémoire des lignes/colonnes utilisé pour le bloc précédent)
c- multiplie les et sauve le résultat sous forme de n lignes et n colonnes en mémoire morte
d- met a jour un compteur indiquant que tu n'as pas encore crashé et qui permettra au besoin de relancer le programme au point qui était en cours plutôt qu'au début

Une fois que toutes tes fonctions seront faites, il sera très facile pour toi de les utiliser dans n'importe quel programme, simplement en remplaàcant les fonctions numpy par tes propres fonctions adapté èa ton hardware. Si tu es sympa, tu paramètres et tu rends le tout disponible en tant que nouvelle libraries python. Si tu es futé, tu vérifies avant que quelqu'un ne l'a pas déjà fait.

[invite9dc7b526]

Si la question est: à combien de coups de la position initiale se trouve n'importe quelle configuration? la réponse est connue, et met en jeu la théorie des groupes, pas besoin de simulations.