Partage
  • Partager sur Facebook
  • Partager sur Twitter

algo variante hanoi

Sujet résolu
    16 juillet 2021 à 9:34:33

    Bonjour,
    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

    • Partager sur Facebook
    • Partager sur Twitter
      16 juillet 2021 à 21:27:56

      Une solution minimale ne passe pas deux fois par la meme position...
      • Partager sur Facebook
      • Partager sur Twitter
        16 juillet 2021 à 23:03:47

        merci pour cette remarque, mais ce n'est pas ma question.
        • Partager sur Facebook
        • Partager sur Twitter
          16 juillet 2021 à 23:34:16

          Ah pardon, j'ai mal lu. Il s'agissait de trouver une suite de mouvements

          • qui résoud le problème (trimballer tous les disques d'une tour à une autre)
          • qui ne passe pas 2 fois par le même position
          • qui soit maximale
          • Partager sur Facebook
          • Partager sur Twitter
            16 juillet 2021 à 23:56:32

            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.
            • Partager sur Facebook
            • Partager sur Twitter
              17 juillet 2021 à 4:36:22

              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 ...
              • Partager sur Facebook
              • Partager sur Twitter

              Le Tout est souvent plus grand que la somme de ses parties.

                17 juillet 2021 à 9:13:14

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

                • Partager sur Facebook
                • Partager sur Twitter
                  17 juillet 2021 à 18:05:34

                  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

                  • Partager sur Facebook
                  • Partager sur Twitter
                    18 juillet 2021 à 8:33:40

                    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.
                    • Partager sur Facebook
                    • Partager sur Twitter
                      18 juillet 2021 à 23:12:11

                      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

                      • Partager sur Facebook
                      • Partager sur Twitter
                        18 juillet 2021 à 23:30:32

                        michelbillaud a écrit:

                        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 :p

                        Si tu veux augmenter le niveau tu peux venir jouer aussi https://zestedesavoir.com/forums/sujet/15504/marathon-dalgorithmes/?page=3#p236111 :ange: y a un nouveau challenge.

                        Je pense que je vais y aller :) on s'y rejoint Michel ?

                        -
                        Edité par White Crow 18 juillet 2021 à 23:31:14

                        • Partager sur Facebook
                        • Partager sur Twitter
                          18 juillet 2021 à 23:37:02

                          lol il y a de la testostérone ici !

                          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.

                          • Partager sur Facebook
                          • Partager sur Twitter
                            18 juillet 2021 à 23:38:43

                            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

                            • Partager sur Facebook
                            • Partager sur Twitter
                              18 juillet 2021 à 23:45:29

                              bah comme tu veux … mais la démo était intéressante, le nouveau challenge aussi.
                              • Partager sur Facebook
                              • Partager sur Twitter

                              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.
                              • Editeur
                              • Markdown