IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Algorithme pour une variante des tours de Hanoi


Sujet :

Algorithmes et structures de données

  1. #1
    Candidat au Club
    Femme Profil pro
    Directeur de projet
    Inscrit en
    juillet 2021
    Messages
    3
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Âge : 43
    Localisation : France, Seine et Marne (Île de France)

    Informations professionnelles :
    Activité : Directeur de projet

    Informations forums :
    Inscription : juillet 2021
    Messages : 3
    Points : 2
    Points
    2
    Par défaut Algorithme pour une variante des tours de Hanoi
    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.

  2. #2
    Membre régulier
    Profil pro
    Inscrit en
    février 2010
    Messages
    84
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : février 2010
    Messages : 84
    Points : 109
    Points
    109
    Par défaut graphe planaire
    Peut-être comme pour le voyageur de commerce , faire un test de planarité en cherchant les cliques de K3 3 et 5 et prendre les klicques 5 pour les majeurs au lieu des mineurs .
    faire un algo de recherche en profondeur avec https://fr.wikipedia.org/wiki/Test_de_planarit%C3%A9 la méthode d'addition des arrêtes ou des sommets

  3. #3
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    décembre 2013
    Messages
    3 268
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : décembre 2013
    Messages : 3 268
    Points : 7 494
    Points
    7 494
    Par défaut
    De manière générale, quand on cherche un arbre pour aller d'un point A à un point B, j'aime bien travailler avec 2 arbres.
    Un arbre qui part du point A et un autre qui part de B.
    Illustration :
    Imaginons une tour de 5 éléments, et 3 emplacements.
    A chaque étape, on a en moyenne 3 mouvements possibles, à peu près.
    J'estime que la solution est un chemin de 1200 étapes.
    Si on explore toutes les configurations partant de A, on a un arbre de 3^1200 éléments ( probablement beaucoup moins ... avec les histoires de doublons ...)
    En explorant toutes les configurations partant de A , et toutes celles partant de B, on a en gros 2 arbres de 3^600 , bénéfice énorme.
    Et dès qu'une feuille de l'arbre n°1 coïncide avec une feuille de l'arbre n°2, on a un parcours.
    Avec ici l'avantage que les 2 arbres sont identiques, si on le souhaite.

    A voir comment adapter ça pour la recherche d'un plus long chemin. Rien d'évident.
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  4. #4
    Candidat au Club
    Femme Profil pro
    Directeur de projet
    Inscrit en
    juillet 2021
    Messages
    3
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Âge : 43
    Localisation : France, Seine et Marne (Île de France)

    Informations professionnelles :
    Activité : Directeur de projet

    Informations forums :
    Inscription : juillet 2021
    Messages : 3
    Points : 2
    Points
    2
    Par défaut
    @mach1974, je ne comprends pas trop ce que tu veux faire. Une recherche de chemin hamiltonien est déjà lours et là tu m'orientes vers un test de planarité ? mon graphe est par construction planaire.

    @tbc92 désolé, le graphe des positions est un graphe et non un arbre. J'y cherche un chemin hamiltonien car à priori il existe toujours même si je n'ai pas pu le prouver. Ce que je cherche ici est une autre approche que la recherche de chemin hamiltonien dans un graphe, dans le cadre des tours de Hanoi.

  5. #5
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    décembre 2013
    Messages
    3 268
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : décembre 2013
    Messages : 3 268
    Points : 7 494
    Points
    7 494
    Par défaut
    J'ai employé le mot arbre, mais c'est une imprécision. Ca s'appliquait à un graphe quelconque (sans boucle)
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  6. #6
    Candidat au Club
    Femme Profil pro
    Directeur de projet
    Inscrit en
    juillet 2021
    Messages
    3
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Âge : 43
    Localisation : France, Seine et Marne (Île de France)

    Informations professionnelles :
    Activité : Directeur de projet

    Informations forums :
    Inscription : juillet 2021
    Messages : 3
    Points : 2
    Points
    2
    Par défaut
    Pour info, la solution de ce problème est relativement plus simple et ne nécessitait pas l'artillerie lourde que j'ai déployée. L'auteur a d'abord prouvé que résoudre hanoi en n'utilisant que des déplacements entre tours adjacentes résolvait aussi le probleme qu'il posait. Cela donne une solution récursive ressemblant à un hanoi classique.
    Ensuite il remarque que le parcours du graphe revient à :

    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.


    Ce qu'un autre participant a résumé 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



    merci à tt le monde

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. algorithme pour l'extraction des minuties d'une empreinte digital
    Par hanou88 dans le forum Traitement d'images
    Réponses: 1
    Dernier message: 18/03/2011, 19h36
  2. Des idées d'algorithme pour une tâche de planification
    Par laureat dans le forum Intelligence artificielle
    Réponses: 1
    Dernier message: 22/08/2009, 14h39
  3. algorithme pour pousser/réduire des rectangles
    Par zuzuu dans le forum Algorithmes et structures de données
    Réponses: 4
    Dernier message: 15/04/2008, 17h25
  4. Quel langage pour une gestion des stocks-client-caisse ?
    Par plex dans le forum Langages de programmation
    Réponses: 2
    Dernier message: 07/04/2007, 18h56
  5. Réponses: 7
    Dernier message: 12/10/2006, 01h23

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo