| Auteur |
Message |
naruto70
Traîne ici, comme d'hab'
Inscrit le: 30 Oct 2006
Messages: 215
Localisation: Haute-Saône
|
 Posté le: Sam Avr 07, 2007 1:27 pm Sujet du message: Rubik's cube en moins de mouvements possibles |
 |
|
Un rubik's cube peut être fait en moins de 22 mouvements. Il me semble que la démonstration était de 28 mais qu'il y a de forte chance pour que se soit 22 le nombre minimale.
Enfin voila ma question : ce lien http://perso.orange.fr/RubikUbik/cubexp15.zip
propose un logiciel qui permet de résoudre le rubik's cube en moins de 22 mouvements. Il fonctionne bien. Mais j'aimerais savoir comment il fait. Est ce que c'est possible de trouver les formules de résolutions à la main avec simplement un papier et un crayon ?
_________________Moyenne 3*3*3 : 17 sec 74
Record unlucky : 14 sec 53
Record lucky : 12 sec 35 |
|
| Revenir en haut de page |
|
 |
|
|
brebis
Traîne ici, comme d'hab'
Inscrit le: 09 Jan 2007
Messages: 182
Localisation: Montreuil (93)
|
| Posté le: Sam Avr 07, 2007 1:40 pm Sujet du message: |
|
|
Bluffant ce logiciel. Mais à mon avis, tu auras beau prendre le meilleur crayon et le meilleur papier, tu ne pourrais pas arriver au même résultat. Les algos (au sens informatique du terme) à l'interieur du programme doivent être incompréhensible, l'ordi doit à mon avis tester beaucoup de solutions avant de trouver la bonne. Tu pourrais refaire la même méthode dans ton coin, mais à mon avis il faudrait des heures et des heures, si ce n'est des années. Un mec calé en informatique te renseignera mieux que moi en tout cas.
_________________OOOOoOooOoOoooOOOOOOOOOOOoooo
Le langage SMS est à la langue française,
ce que Kyo est au Rock'n Roll
oOOOooOoOOoOoOOoooOoOOOOoOOOo |
|
| Revenir en haut de page |
|
|
naruto70
Traîne ici, comme d'hab'
Inscrit le: 30 Oct 2006
Messages: 215
Localisation: Haute-Saône
|
| Posté le: Sam Avr 07, 2007 1:56 pm Sujet du message: |
|
|
ok mais comment il est programmer ce logiciel alors ?
ils ne doit pas tester plein de possibilité comme sa dans le vide, il doit bien y avoir une structure
_________________Moyenne 3*3*3 : 17 sec 74
Record unlucky : 14 sec 53
Record lucky : 12 sec 35 |
|
| Revenir en haut de page |
|
|
brebis
Traîne ici, comme d'hab'
Inscrit le: 09 Jan 2007
Messages: 182
Localisation: Montreuil (93)
|
| Posté le: Sam Avr 07, 2007 2:03 pm Sujet du message: |
|
|
Une structure bien sur, mais qui utilise les formidables possibilités de l'ordinateur pour faire des centaines de milliers de calculs et/ou de tests par seconde. Pour info, le programme fait 296 Ko ce qui équivaut à 296 000 caractères pour le programmer. Donc bon courage si tu veux le comprendre. Mais pourquoi n'envoies-tu pas un mail au créateur ?
_________________OOOOoOooOoOoooOOOOOOOOOOOoooo
Le langage SMS est à la langue française,
ce que Kyo est au Rock'n Roll
oOOOooOoOOoOoOOoooOoOOOOoOOOo |
|
| Revenir en haut de page |
|
|
naruto70
Traîne ici, comme d'hab'
Inscrit le: 30 Oct 2006
Messages: 215
Localisation: Haute-Saône
|
|
| Revenir en haut de page |
|
|
deadalnix
Unix Cube
Inscrit le: 11 Nov 2006
Messages: 3102
Localisation: Par GPS
|
| Posté le: Sam Avr 07, 2007 2:33 pm Sujet du message: |
|
|
| brebis a écrit: | | Une structure bien sur, mais qui utilise les formidables possibilités de l'ordinateur pour faire des centaines de milliers de calculs et/ou de tests par seconde. Pour info, le programme fait 296 Ko ce qui équivaut à 296 000 caractères pour le programmer. Donc bon courage si tu veux le comprendre. Mais pourquoi n'envoies-tu pas un mail au créateur ? |
Ca n'est pas tres exact ca dis moi, car le programme est compilé (ca m'ettonerais fortement que le monsieur il ai programmé ca en assembleur).
Mais le secret de ce programme se trouve dans l'algorhytme IDA*, combiné a une heuristique precalculée.
En gros, le programme teste toutes les possibilités de coups en n mouvements au debut de la recherche ou au premier lancement du programme. Si l'optique est ici les 22 mouvements, un profondeur de 11 est suffisante. on part ici du cube fini. C'est le precalcul de l'heuristique.
La nombre de possibilité generée est trop grande pour pouvoir tout stocker dans le pc, en fait on associe juste au combinaisons de coins par exemple le nombre de coups minimum qu'on aura a faire pour resoudre le cube, ou alors la position des f2l, etc . . .
Ensuite on part sur une recherche en profondeur, avec une profondeur maximum. a partir du cube que l'on a a resoudre. On estime en combien de coups minimum on peut resoudre le cube dans cette branche, ce qui correspond au nombre de coup qu'on a fait + a l'heuristique precalculé en fonction de la position de certaines pieces comme expliqué precedement.
Si ce cout depasse le cout maximal qu'on s'est fixé, on coupe la branche. faire un precalcul a 11 coups permet de couper tres rapidement les branches, et evite donc au pc de se perdre dans des rehcerches inutiles.
Pour optimiser la chose, et etre sur de trouver le meilleur resultat du premier coup, on fait uen recherche en profondeur, avec une profondeur maximum iterative.
C'est a dire qu'on commence par exemple avec une profondeur max de 15 coups. On va couper des qu'une brache est sure de ne pas finir en 15 coups, et si c'est le cas, on va stocker le cout estimé, qu'on va appeler c. Ainsi de suite jusqu'a etre sur qu'on ne va pas avoir de soluce en 15 coups. A chaque fois qu'on coupe une branche, on remplace le cout enregistré en c par ce cout s'il est inferieur a c, on au ra ainsi en c le cout minimal de la recherche, en dessous duquel on est sur qu'il n'y a pas de soluce.
Si on a pas de soluce en 15, il faut donc relancer une recherche des soluces, mais avec une profondeur c.
En esperant avoir ete le plus clair possible, meme si ce type d'algorhytme est pas simple 
_________________ |
|
| Revenir en haut de page |
|
|
naruto70
Traîne ici, comme d'hab'
Inscrit le: 30 Oct 2006
Messages: 215
Localisation: Haute-Saône
|
|
| Revenir en haut de page |
|
|
cyril
A domicile
Inscrit le: 30 Juin 2005
Messages: 1685
Localisation: lausanne, suisse
|
| Posté le: Mar Avr 10, 2007 9:39 am Sujet du message: |
|
|
En fait, le programme ne vient pas de ce site, mais du site d'Herbert Kociemba, qui l'a écrit. Il décrit les deux phases de son algorithme de recherche (qui fonctionne comme l'a décrit Deadalnix), dont la première consiste à ramener le cube dans une des configurations que l'on peut résoudre en utilisant uniquement U, D, R2, L2, F2, B2, où les coins ET les arêtes sont orientées. Toutes ces configurations sont stockées dans des tables et à partir de là le programme pond la solution la plus courte (phase 1 + phase 2).
Kociemba l'explique bien mieux que moi ici |
|
| Revenir en haut de page |
|
|
naruto70
Traîne ici, comme d'hab'
Inscrit le: 30 Oct 2006
Messages: 215
Localisation: Haute-Saône
|
|
| Revenir en haut de page |
|
|
|
FAQ
Rechercher
Liste des Membres
Groupes d'utilisateurs
S'enregistrer
Profil
Se connecter pour vérifier ses messages privés
Connexion
Merci pour l'idée
sa fait juste un moi que je m'y suis mis. Mais j'ai a peû près compris l'essentiel 
