Discussion :

[David Fleury]

Bonjour,

peut-on paralléliser la résolution du problème des tours de hanoi ?

ou a-t-on un algorithme qui permet de passer d'une position donnée à une autre ?

Cordialement.

[hiko-seijuro]

Salut,

qu'est ce que tu voudrais paralléliser ?

[O( N )]

Bonjour,

Trés bon problème pour découvrir les complexités les tours de Hanoï...

Paralléliser, je ne sais pas
Tu ne veux pas la position d'arrêt ! Tu veux les étapes de construction, c'est çà ?
Si tu choisies de découper en positions choisies:
Position 1 :
-
--
---
----

Position 2 :
--- | -
---- | --

Position 3 :
| -
| --
---- | ---

Position finale :
| -
| --
| ---
|----

Tu appelles plusieurs séquences avec chacune des conditions d'arrêt différentes
(correspondant à chacune des positions données, par exemple...)

Comme il existe un alogrithme d'une position initiale à la fin je crois qu'il passera par une position et
traversera une autre position donnée jusqu'à la position finale.

Je ne sais pas si en changeant les conditions d'arrêt
tu peux lui dire de terminer sur une position voulue ?

[David Fleury]

Salut,
qu'est ce que tu voudrais paralléliser ?

Le calcul de toutes les étapes pour arriver de la position de départ à celui d'arrivée.

Comme on sait définir le n ième coup de la solution optimale,
on pourrait utiliser 1 processus pour la partie 1 - n ième coup et
l'autre pour n ième coup + 1 et le coup final.

[Zavonen]

Un des meilleurs exemples de la notion de récursivité

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
int other (int p1, int p2)
{ int u=10*p1+p2;
	switch (u)
	{
	case 12: return 3;
	case 21: return 3;
	case 13:return 2;
	case 31: return 2;
	default: return 1;
	}
}
 
void hanoi (int NombreDeDisques, int PiquetSource, int PiquetBut)
{
	if (NombreDeDisques==1)
		printf("De %d vers %d \n",PiquetSource, PiquetBut);
	else
	{
		hanoi(NombreDeDisques-1, PiquetSource, other(PiquetSource,PiquetBut));
		printf("De %d vers %d \n",PiquetSource, PiquetBut);
		hanoi(NombreDeDisques-1, other(PiquetSource,PiquetBut),PiquetBut);
	}
}
 
 
void main ()
{ 
	hanoi(3,3,1);
}

[David Fleury]

En fait, je n'ai ni besoin de la solution récursive ou itérative.
J'ai déjà des implémentations.

Je veux juste savoir s'il existe un algo qui puisse paralléliser une de ces solutions.

En fait, je n'ai pas trouvé grand chose pour le moment sur ce sujet.

[Gwylom]

Bonjour,

je pense qu'il est possible de paralléliser l'algorithme des tours de hanoi (récursif).
A chaque fois que l'on passe dans la fonction hanoi, on effectue 2 calculs :

• déplacer tous les anneaux au dessus de celui que l'on veut bouger vers l'autre piquet
• déplacer tous les anneaux déplacés précédemment au dessus de l'anneau que l'on a bougé.

Comme on connait l'état des piquets et des anneaux à chacun des appels récursifs, on peut appeler en parallèle la fonction hanoi récursivement au lieu de le faire séquentiellement.


Au passage, Zavonen, ta fonction other pourrait être :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
int other (int p1, int p2)
{
   return 6-P1-p2;
}

[Zavonen]

Au passage, Zavonen, ta fonction other pourrait être :
Code :

int other (int p1, int p2) { return 6-P1-p2; }

Bien vu !

[Jean-Marc.Bourguet]

Si tu connais la solution iterative, il est relativement facile de la transformer en une solution absolue (a partir d'une configuration initiale etre capable de donner quel sera le mouvement du n^ieme coup et a quelle configuration il arrivera en temps constant par rapport a n)

[droggo]

Dae,

Une première idée est, pour 2 processeurs par exemple, avec n disques, n°1 est le plus grand

- proc 1 s'occupe des disques 1 à n/2 (donc une petite tour)
- proc 2 s'occupe des disques n/2 +1 à n (donc une autre petite tour)

à la sortie, on reconstitue le total en mettant dans l'ordre les résultats proc 2 puis proc 1.

Ça me paraît viable en tout cas ?

[Gwylom]

Je ne crois pas que l'on puisse faire avec n/2.
Si on enlève les n/2 plus petits disques pour les mettre sur un piquet, on ne pourra pas mettre les plus grands sur l'autre, puisque les petits gènent le passage. En gros, couper à la moitié des disques ne rend pas 2 tâches indépendantes.

Je pensais plus à un processeur qui dépile les disques (tous sauf le plus gros), et un qui les rempile.

[David Fleury]

Si tu connais la solution iterative, il est relativement facile de la transformer en une solution absolue (a partir d'une configuration initiale etre capable de donner quel sera le mouvement du n^ieme coup et a quelle configuration il arrivera en temps constant par rapport a n)

(Je déteste la relativité, j'ai l'impression d'être stupide quand je ne trouve pas...)

J'ai du mal à voir comment ça pourra paralléliser le calcul en ayant un temps constant sur n ?
Si j'ai bien compris, ça voudrait dire que je dois calculer à partir d'une situation de départ, la situation suivante au n ième coup pour la fournir à un autre thread. Ce n'est pas censé être parallélisable si on peut fournir la situation finale en o(1) à partir d'un thread1 vers un autre thread2 et calculer ensuite le chemin dans le thread1.
Le thread2 faisant ensuite la même chose à un autre thread.

Mais je vais essayer pour voir s'il y a un gain en utilisant ta méthode avec la formules de codage des positions (pour le moment, je ne vois que ça qui puisse aider)

Ca me donne mal à la tête...

[droggo]

Fio,

Je ne crois pas que l'on puisse faire avec n/2.
Si on enlève les n/2 plus petits disques pour les mettre sur un piquet, on ne pourra pas mettre les plus grands sur l'autre, puisque les petits gènent le passage. En gros, couper à la moitié des disques ne rend pas 2 tâches indépendantes.

Oui, vu, Il est vrai que j'ai écrit ça sans trop y réfléchir.

[Zavonen]

Je ne sais pas démontrer formellement qu'un processus n'est pas parallélisable.
Cependant j'ai la conviction que celui-ci ne l'est pas, et qu'il est foncièrement récursif même si on peut en donner une description itérative.
En effet, pour résoudre le pb avec n disques, il faut bouger le plus gros, pour bouger le plus gros, il faut qu'il soit seul sur un piquet et que tous les autres soient empilés dans l'ordre sur le troisième, on est OBLIGE de passer par cette étape. Or cette étape correspond ni plus ni moins au pb de hanoï d'ordre n-1.
Si on essaie avec 3 disques, à la main, on constate que chaque mouvement qui fait avancer réellement le processus, ne peut arriver qu'à un moment précis, tout dérangement de l'ordre naturel des mouvements, ne fait qu'allonger le processus car c'est un pas en avant qui sera suivi d'un pas en arrière.
Si on passe à 4, compte tenu de la remarque précédente, il faut commencer avec 3 disques. Bref j'ai le sentiment qu'on ne peut pas procéder à des échanges simultanés sous peine de ralentir la résolution globale.
Ce n'est qu'une impression.

[droggo]

Zie,

Je ne sais pas démontrer formellement qu'un processus n'est pas parallélisable.
Cependant j'ai la conviction que celui-ci ne l'est pas, et qu'il est foncièrement récursif même si on peut en donner une description itérative.
En effet, pour résoudre le pb avec n disques, il faut bouger le plus gros, pour bouger le plus gros, il faut qu'il soit seul sur un piquet et que tous les autres soient empilés dans l'ordre sur le troisième, on est OBLIGE de passer par cette étape. Or cette étape correspond ni plus ni moins au pb de hanoï d'ordre n-1.
Si on essaie avec 3 disques, à la main, on constate que chaque mouvement qui fait avancer réellement le processus, ne peut arriver qu'à un moment précis, tout dérangement de l'ordre naturel des mouvements, ne fait qu'allonger le processus car c'est un pas en avant qui sera suivi d'un pas en arrière.
Si on passe à 4, compte tenu de la remarque précédente, il faut commencer avec 3 disques. Bref j'ai le sentiment qu'on ne peut pas procéder à des échanges simultanés sous peine de ralentir la résolution globale.
Ce n'est qu'une impression.

Je pense que tu as raison.

[pseudocode]

En effet, pour résoudre le pb avec n disques, il faut bouger le plus gros, pour bouger le plus gros, il faut qu'il soit seul sur un piquet et que tous les autres soient empilés dans l'ordre sur le troisième, on est OBLIGE de passer par cette étape.

Ce qui implique que l'on a un état intermediaire obligatoire connu. Donc on peut séparer le processus "etat initial -> état intermediaire obligatoire" et le processus "état intermediaire obligatoire -> etat final". Et donc paralleliser ces 2 processus.

On peut meme aller bcp plus loin avec le hanoi classique (3 piquets) et paralleliser le calcul de tous les mouvements car la sequence est cyclique:
- Il y a 2^n - 1 mouvements a effectuer
- On bouge le plus petit disque (taille 1) tous les 2 coups (1,3,5,...)
- On bouge le disque moyen (taille 2) tous les 4 coups (2,6,10,...)
- ... et d'une maniere génerale, on bouge le disque de taille k tout les 2^k coups (2^(k-1), 2^(k-1)+2^k, ...)

Il reste a calculer le mouvement (piquet source->target) du disque de taille "k", au coup "i", sachant qu'il y a "n" disques. Je vous laisse chercher...

[Zavonen]

- On bouge le plus petit disque (taille 1) tous les 2 coups (1,3,5,...)
- On bouge le disque moyen (taille 2) tous les 4 coups (2,6,10,...)
- ... et d'une maniere génerale, on bouge le disque de taille k tout les 2^k coups (2^(k-1), 2^(k-1)+2^k, ...)

Qu'est-ce que ce parallélisme là où un processus est obligé d'attendre qu'un autre aie fait son job pour intervenir ?
C'est simplement mettre Pierre et Paul à travailler alternativement, là où Jacques aurait pu faire le boulot seul dans le même temps.
C'est efficace pour résorber le chômage, mais pas pour accélérer la manoeuvre.
Je ne vois nulle part la notion de simultanéité (parallélisme vrai).

[droggo]

Kau,

Qu'est-ce que ce parallélisme là où un processus est obligé d'attendre qu'un autre aie fait son job pour intervenir ?
C'est simplement mettre Pierre et Paul à travailler alternativement, là où Jacques aurait pu faire le boulot seul dans le même temps.
C'est efficace pour résorber le chômage, mais pas pour accélérer la manoeuvre.
Je ne vois nulle part la notion de simultanéité (parallélisme vrai).

J'allais le dire.

[pseudocode]

Qu'est-ce que ce parallélisme là où un processus est obligé d'attendre qu'un autre aie fait son job pour intervenir ?
C'est simplement mettre Pierre et Paul à travailler alternativement, là où Jacques aurait pu faire le boulot seul dans le même temps.
C'est efficace pour résorber le chômage, mais pas pour accélérer la manoeuvre.
Je ne vois nulle part la notion de simultanéité (parallélisme vrai).

lol. bon j'ai peut-etre été un peu vite dans l'explication.

Dans un hanoi classique, on connait les mouvements a priori => Le calcul de CHAQUE COUP est indépendant des précedents ou des suivants. Ce calcul dépend uniquement du n° du coup et du nombre total de disque.

Par exemple, je sais que le mouvement n° 1234567 consiste a bouger le petit disque (puisque c'est un nombre impair).

On peut donc paralleliser entierement le calcul. Pour un hanoi classique avec n disques, on peut lancer (2^n)-1 thread en parallele (une par coup), chacune s'occupant de calculer un coup.

[David Fleury]

Ce qui implique que l'on a un état intermediaire obligatoire connu. Donc on peut séparer le processus "etat initial -> état intermediaire obligatoire" et le processus "état intermediaire obligatoire -> etat final". Et donc paralleliser ces 2 processus.

On peut meme aller bcp plus loin avec le hanoi classique (3 piquets) et paralleliser le calcul de tous les mouvements car la sequence est cyclique:
- Il y a 2^n - 1 mouvements a effectuer
- On bouge le plus petit disque (taille 1) tous les 2 coups (1,3,5,...)
- On bouge le disque moyen (taille 2) tous les 4 coups (2,6,10,...)
- ... et d'une maniere génerale, on bouge le disque de taille k tout les 2^k coups (2^(k-1), 2^(k-1)+2^k, ...)

Il reste a calculer le mouvement (piquet source->target) du disque de taille "k", au coup "i", sachant qu'il y a "n" disques. Je vous laisse chercher...

Ok.
Bon ça devrait aller avec ça.

[HS]J'ai trouvé un truc rigolo lié au triangle de sierpinski (http://www.cut-the-knot.org/triangle/Hanoi.shtml)