sur un autre site un intervenant propose en challenge de résoudre un problème qu'il appelle maxnoi : c'est les tours de hanoi mais au lieu de trouver la solution qui nécessite un minium de déplacements il demande celle qui en demande le plus avec la contrainte de ne jamais se retrouver dans une position déjà jouée pour éviter les cycles.
J'ai bien une solution qui consiste à construire un arbre avec toutes les positions possibles, deux nœuds étant connectés si la position de l'un peut atteindre la position de l'autre avec un déplacement valide. Je cherche ensuite un chemin hamiltonien entre la position de départ et d'arrivée. Ça fonctionne mais c'est pas optimal, trop lourd.
Alors je viens à vous pour savoir si vous aviez des idées différentes pour aborder le problème.
Merci à tous.
- Edité par AlineCastel 16 juillet 2021 à 10:04:11
et qui soit moins lourde que la recherche d'un chemin hamiltonien dans un graphe de positions, je me suis trompé dans ma description car le graphe n'est pas un arbre.
J'ai pensé à un arbre puisque tu en parlais, mais ça n'a pas de sens. Tu aurais de multiples instances de chaque état. La question n'est peut-être pas de trouver une autre alternative, mais de coder différemment cette alternative. Es-tu capable d'isoler le temps pris pour construire le graphe de celui pour trouver le chemin hamiltonien? En construisant ton graphe, comment sais-tu que tu n'as pas déjà rencontré l'état suivant? Comment représentes-tu chaque état? Par exemple, une séquence du genre: 54302010 avec 3 tours. Et tu chercherais dans une table de hachage ...
Le Tout est souvent plus grand que la somme de ses parties.
Pour info une solution a été proposée et validée. L'algorithme est simple comme bonjour :
faire le seul mouvement possible entre deux tours adjacentes qui ne défasse pas le mouvement joué au tour précédent
recommencer tant que c'est possible
c'est beaucoup plus simple que ma solution.
C'est ce que je cherchais à faire en demandant une idée différente pour aborder le problème. Mais merci quand même, je vais juste essayer de comprendre pourquoi cette solution fonctionne..
Le seul mouvement qui ne défait pas le précédent : Y a un problème pour le premier. Et pas l'ombre d'une preuve que ça fonctionne.
Bon, allez, sérieusement....
Il y a 3 tours et N disques. Et donc 3^N configurations possibles.
Et donc, si il existe une suite de mouvements qui passe une fois par toutes les configurations, elle est de taille T(N) = 3^N-1. (Les piquets, les intervalles...)
Avec un papier, on trouve facilement pour N=0 (0 mouvements !) N=1 (2), N=2 (8). C'est un peu plus de travail pour 3 (26).
Après on on remarque que T(N) = 3 T(N-1) + 2.
Ce qui laisse penser que pour faire le boulot avec N disques, on a
3 fois le boulot avec N-1 disques
2 déplacements du gros disque
Donc, pour déplacer N disques de A à B
On bouge les N-1 disques de A à B soit T(N-1) mouvements
On déplace le gros disque de A à C, +1
On bouge les N-1 disques de B à A, +T(N-1)
On déplace le gros disque de C à B, +1
On bouge les N-1 disques de A à B, +T(N-1)
Et hop, ça fait le compte(on voit assez facilement qu'on n'a pas pu passer deux fois par la même configuration)
PS: je ne donne pas le programme (parce que quand même), mais voila le résultat
$ ./a.out
test pour n = 0
test pour n = 1
Gauche -> Droite
Droite -> Milieu
test pour n = 2
Gauche -> Droite
Droite -> Milieu
Gauche -> Droite
Droite -> Milieu
Milieu -> Gauche
Droite -> Milieu
Gauche -> Droite
Droite -> Milieu
test pour n = 3
Gauche -> Droite
Droite -> Milieu
Gauche -> Droite
Droite -> Milieu
Milieu -> Gauche
Droite -> Milieu
Gauche -> Droite
Droite -> Milieu
Gauche -> Droite
Droite -> Milieu
Milieu -> Gauche
Droite -> Milieu
Milieu -> Gauche
Gauche -> Droite
Milieu -> Gauche
Droite -> Milieu
Milieu -> Gauche
Droite -> Milieu
Gauche -> Droite
Droite -> Milieu
Gauche -> Droite
Droite -> Milieu
Milieu -> Gauche
Droite -> Milieu
Gauche -> Droite
Droite -> Milieu
Y a le compte....
- Edité par michelbillaud 17 juillet 2021 à 22:33:01
Tu aurais du jouer. L'explication donne une preuve un peu plus complète que la tienne qu'il y a 3**n positions distinctes. Ensuite il y a une démo sur pourquoi les déplacements sur des tours adjacentes uniquement résout le problème. L'algo donné est presque identique au tien à ceci près que tu ordonnes tes tours en gauche droite milieu et lui en gauche milieu droite. Tu résous un problème légèrement différents du but des tours de Hanoi originel la position finale devant être positionnée sur la tour de droite.
L'explication de la version simple tient à la manière dont le graphe des positions est parcouru. Il peut être décrit par :
1. déplacer le plus petit disque vers la droite deux fois, aller en 6. si le jeu est terminé ; 2. effectuer le seul autre déplacement valide n’utilisant pas le plus petit disque ; 3. déplacer le plus petit disque vers la gauche deux fois ; 4. effectuer le seul autre déplacement valide n’utilisant pas le plus petit disque ; 5. recommencer en 1. 6. Sabler le champagne !
ce qui se simplifie finalement en
1. tant qu’il existe un déplacement valide entre deux tours adjacentes qui ne défasse pas le déplacement précédent ;
2. faire ce mouvement ;
3. sabler le champagne !
puisque après avoir joué le plus petit disque deux fois le seul autre déplacement possible implique de jouer les disques sur les autres tours qui seront nécessairement adjacentes, le plus petit étant obligatoirement à gauche ou à droite.
Tu n'as pas donné de lien vers le jeu, on ne peut pas deviner. "Un autre site", sur internet, y en a quand même plusieurs.
Le niveau d'explication dépend de ceux à qui elle est destinee : 3^N c'est la traduction directe du fait que chacun des n disques est sur une des 3 tours. Faut-il détailler ou pas ?
Le nom des tours n'a pas d'importance, c'est à une permutation près.
A partir de l'algo récursif, on peut démontrer (par récurrence) les propriétés de la suite de mouvements qui conduisent à l'algo itératif. C'est analogue aux tours de hanoi
- Edité par michelbillaud 18 juillet 2021 à 23:40:27
Le niveau d'explication dépend de ceux à qui elle est destinee : 3^N c'est la traduction directe du fait que chacun des n disques est sur une des 3 tours. Faut-il détailler ou pas ?
stp oui, mais bon c'est déjà fait sur le lien. Tu demandais un peu de preuve après tout
Tu aurais pu donner la même explication que le lien ou partir sur quelque chose de plus simple en tournant de 90 degrés le jeu. Je trouve que tu as le facilement facile
Le plus intéressant avec les problèmes c'est qu'on a une intuition directe de la solution mais c'est plus difficile de prouver, @michelbillaud a raison.
Le lien, il est apparu après que j'ai proposé un _début_ de construction raisonnée d'un algo pour résoudre ce problème.
Après, je ne trouve quand même pas le probleme trop passionnant, je n'ai pas la prétention d'élever le niveau, et ces jours-ci, j'ai d'autres occupations (distraction : taper sur des gens IRL :-))
.
- Edité par michelbillaud 18 juillet 2021 à 23:41:15
bah comme tu veux … mais la démo était intéressante, le nouveau challenge aussi.
algo variante hanoi
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Le Tout est souvent plus grand que la somme de ses parties.