Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#1 07-01-2018 01:06:34

Milos
Membre
Inscription : 11-07-2013
Messages : 94

Solution généralisée des tours de Hanoï (ou Toronto : 4 tours)

Bonsoir à tous et bonne année,

Je cherche à retrouver une solution qu'un mathématicien (Olivier S., dont j'ai perdu les coordonnées) m'avait donnée vers 1988 à l'occasion de l'écriture d'un mémoire sur les aptitudes cognitives, notamment la résolution d'un casse-tête - celui de Hanoï.

Je pense que presque tout le monde le connaît : il s'agit de disques de taille décroissante, pouvant s'enfiler sur 3 tiges, et il faut depuis la position de départ où tous sont empilés sur la tige de gauche, les empiler sur celle de droite, sans jamais déplacer plus d'un disque à la fois, ni placer un disque plus grand au-dessus d'un plus petit. La position de départ est un empilement de 5 disques par ordre décroissant et donc toutes les positions suivantes n'ont que des disques empilés par taille décroissante sur chacune des 3 tiges (ou aucun disque comme les tiges du milieu et celle de droite au début).

Olivier S. m'avait fourni une méthode permettant, à partir d'une position quelconque, de trouver quel est le meilleur coup (au sens de celui donnant le chemin le plus court) pour atteindre une autre position quelconque.

L'algorithme qui en découlait était itératif et assez court, on lui passait la position codée de départ et celle de destination, et la fonction renvoyait le coup à effectuer. Il n'explorait rien, il ne s'agissait pas d'un algorithme récursif mis à plat, il ne faisait que considérer le codage de la position de départ et celle d'arrivée pour trouver le coup à jouer.
J'ai naturellement perdu les sources..
Il me semble, je n'en suis plus très sûr, que les positions faisaient l'objet d'un calcul rattaché à l'écriture de Gros-Gray, mais c'était peut-être autre chose : en tout cas, le code était compact.

Si ça peut aider, j'ai toujours par contre le graphe qui contient toutes les positions avec 4 disques en tout et permettait en fin d'expérimentation, de tracer en quelque sorte les errances des sujets testés au fur et à mesure de leurs essais.

En effet il n'y avait que 4 disques au lieu de 5, le casse-tête est alors surnommé les tours de Toronto et c'est cette variante qui a fait l'objet d'expérimentations sur des volontaires sains dans pas mal d'études sur les effets de médicaments ou placebo sur la mémoire. Il y a eu aussi quelques études sur des patients mais uniquement comparatives, pour tenter de trouver un pattern d'altérations cognitives rattachables à différentes pathologies. Ce test faisait naturellement partie d'une quantité d'autres tests et n'était pas effectué seul.

Le graphe est d'allure fractale, en forme de triangle dont ici les côtés font 15 longueurs, soit le chemin de résolution le plus court. La position du haut, avec les 4 tours à gauche est numérotée 0(0) sur mon graphe, celle du bas à gauche avec les 4 tours au milieu 121(1) et à l'opposé en bas à droite, celle avec les 4 tours à droite 242(2). Tous les nombres entre parenthèses sont entre 0 et 2.

Est-ce que vous pourriez m'aider à retrouver ce qu'Olivier m'avait indiqué ? (je vous préviens honnêtement que je suis totalement incapable de voir en quoi l'écriture de Gros-Grey peut aider, ou pourquoi il y a une similitude entre ce casse-tête et un baguenaudier : en somme que si je sais que ça ne se fait pas de demander des solutions toutes faites, je me permets une exception en espérant que vous me pardonnerez cette demande inspirée par la nostalgie autant que par le désir de réécrire un test cognitif sur les tours de Toronto).

J'espère donc que la question vous intéressera suffisamment pour chercher à retrouver ce que Olivier avait pu me dire..

Bien cordialement

Milos

Dernière modification par Milos (07-01-2018 02:10:50)

Hors ligne

#2 28-01-2018 15:05:19

Choukos
Membre
Inscription : 26-12-2010
Messages : 148
Site Web

Re : Solution généralisée des tours de Hanoï (ou Toronto : 4 tours)

Bonjour Milos,
Si j'ai bien compris, tu représentes le jeu par un graphe comme décrit dans https://fr.wikipedia.org/wiki/Tours_de_Hano%C3%AF dans la section "Tours de Hanoï et Triangle de Pascal" ?
Là y'a une image pour trois disques, mais avec 4 (resp. 5) ça donne une image similaire de trois triangles représentant un jeu à trois (resp. quatre) disque (on touche pas au plus gros disque dans chacun de ces sous triangles).

Aller d'une configuration à une autre c'est trouver un chemin entre deux noeuds de ce graphe, autrement que rechercher un plus court chemin entre ces deux noeuds (en utilisant ça ? https://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra ?) je ne vois pas comment être plus malin.

Hors ligne

#3 28-01-2018 19:33:40

Milos
Membre
Inscription : 11-07-2013
Messages : 94

Re : Solution généralisée des tours de Hanoï (ou Toronto : 4 tours)

Bonsoir Choukos,

Merci de ta réponse. Le graphe ressemble bien à celui qui est visible dans le lien que tu donnes.
Par contre je ne comprends pas très bien l'algorithme de Dijkstra, et en tout cas il est suffisamment complexe pour que ce ne soit pas celui que j'avais implémenté selon les indications d'Olivier S. (je ne donne pas son nom de famille par souci de discrétion, et évidemment si j'avais son adresse je lui aurais posé directement la question)

De mémoire, tout tenait à la façon de coder une position, et à un calcul du genre addition bit à bit sans retenue, ou quelque chose de ce genre, pour trouver le premier coup du chemin menant à la position finale à atteindre.
Sauf bêtise de ma part, il n'y a que 3 coups possibles, deux déplacements possibles du plus petit disque et un déplacement d'un autre disque éventuellement (si nous ne sommes pas à une extrémité du graphe où tous les disques sont sur une seule tige).
Le calcul devait se faire sur les nombres représentant les positions immédiatement proches, et un de ces nombres devait avoir une particularité permettant de le reconnaître comme étant sur le chemin conduisant à la position finale.

C'est pour ça que je donnais les nombres représentant les sommets du triangle avec entre parenthèses ce qui semble être un reste modulo 3 de je ne sais quelle opération.

J'ai beau chercher, je ne vois pas comment on obtenait ce nombre représentant une position du triangle. Si tu veux je peux scanner la feuille où j'avais imprimé le graphe, mais il faudrait vraiment que je le fasse avec une haute résolution et je ne suis pas sûr que ça reste lisible comme il y a une minuscule représentation des 4 disques et de leur disposition sur les 3 tiges à chaque noeud du graphe, en plus du nombre et du 0..2 entre parenthèses.

Merci beaucoup de t'intéresser à ma question, je n'arrive pas à retrouver cette méthode et en plus d'être agaçant, ça m'arrangerait bien de la retrouver pour réécrire quelques tests cognitifs comme celui-ci.

Bien amicalement,

Milos

Hors ligne

#4 06-03-2018 22:13:40

hilbert poincarré
Membre
Inscription : 06-03-2018
Messages : 1

Re : Solution généralisée des tours de Hanoï (ou Toronto : 4 tours)

c'est un probleme de nature recursive

Hors ligne

Pied de page des forums