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 ?

[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;
}

[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 ?