Discussion :

[acastel]

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.

[mach1974]

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

[tbc92]

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.

[acastel]

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

[tbc92]

J'ai employé le mot arbre, mais c'est une imprécision. Ca s'appliquait à un graphe quelconque (sans boucle)

[acastel]

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