Discussion :

[piotrr]

J'ai un graphe, je veux aller d'un point A à un point B.
Je veux alors dresser la liste de tous les chemins possibles entre ces deux sommets.
J'imagine qu'il faut une fonction récursive mais la récursivité et moi ...

Est ce que quelqu'un connaitrait - il un algo tout fait ?

merci

[cha0s]

tu peut utiliser l'algo de Dijkstra.

[piotrr]

Ok mais je ne veux pas trouver le plus court chemin, je veux juste parcourir tous les chemins possibles.

Merci

[pseudocode]

Tu peux calculer les puissance successives de la matrice d'adjacence, afin de connaitre le nombre de chemins de longueur 'n' entre 2 sommets donnés.

Pour identifier précisement chaque chemin tu peux soit faire le calcul inverse, soit conserver les éléménts de la matrice qui ont servis aux calculs intermédiaires.

[Ulmo]

J'ai un graphe, je veux aller d'un point A à un point B.
Je veux alors dresser la liste de tous les chemins possibles entre ces deux sommets.
J'imagine qu'il faut une fonction récursive mais la récursivité et moi ...

Est ce que quelqu'un connaitrait - il un algo tout fait ?

merci

Il va falloir préciser, parce que si il y a un cycle dans ton graphe, il y aura une infinité de chemins...

[piotrr]

J'ai un graphe non orienté avec des cycles.
Je veux trouver tous les chemins d'un point A à un point B sans passer deux fois par le même sommet.
je veux avoir à la fin une liste de tous les chemins possibles.

merci

[pseudocode]

J'ai un graphe non orienté avec des cycles.
Je veux trouver tous les chemins d'un point A à un point B sans passer deux fois par le même sommet.
je veux avoir à la fin une liste de tous les chemins possibles.

merci

Dans ce cas tu peux faire une exploration complète des chemins, avec une recherche taboo.

[piotrr]

Dans ce cas tu peux faire une exploration complète des chemins, avec une recherche taboo.

Qu'est ce que la recherche "taboo"?
Je n'ai rien trouvé à ce propos.

Merci

[pseudocode]

Qu'est ce que la recherche "taboo"?
Je n'ai rien trouvé à ce propos.

Houla... c'est exxxxxtremement compliqué.

Non, je plaisante. Ca consiste a poser des petits cailloux le long du chemin pour éviter de passer 2 fois au meme endroit. Un petit exemple:

On modélise le graphe

Code java :

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

1
2
3
4
5
6
7
8
9
10
11
// nombre de sommets dans le graphe
int n=5;
 
// matrice d'adjacence du graphe 
int[][] adjacencymatrix = new int[][] {
	new int[] {1,1,1,0,0}, //    1
	new int[] {1,1,1,1,0}, //  / | \
	new int[] {1,1,1,1,0}, // 0  |  3 - 4
	new int[] {0,1,1,1,1}, //  \ | /
	new int[] {0,0,0,1,1}, //    2
};

On définit les quelques variables utilisées par notre algorithme:

Code java :

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

1
2
3
4
5
6
7
8
9
// stockage du chemin pendant l'exploration recursive
int[] path = new int[n];
 
// verrou pour la recherche taboo (tous initialisés à "false" par défaut)
boolean[] taboo = new boolean[n];
 
// sommets de départ/arrivé souhaités
int source=0;
int target=4;

Et enfin l'algorithme de parcours recursif:

Code java :

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
void explore(int position, int depth) {
	path[depth]=position;
 
	// on est sur le sommet d'arrivé -> fini
	if (position==target) {
		// affiche la solution
		for(int i=0;i<=depth;i++) System.out.print(path[i]+" ");
		System.out.print("\n");
		return;
	}
 
	// sinon...
 
	taboo[position]=true; // on pose un caillou
 
	// on explore les chemins restants
	for(int i=0;i<n;i++) {
		if (adjacencymatrix[position][i]==0 || taboo[i]) continue;
		explore(i,depth+1);
	}
 
	taboo[position]=false; // on retire le caillou
}

on appelle l'algorithme avec "explore(source,0);" pour lui dire de commencer à explorer à partir du noeud 'source'. Ce qui nous donne les 4 chemins possibles entre les sommets "0" et "4":

0 1 2 3 4
0 1 3 4
0 2 1 3 4
0 2 3 4

[piotrr]

Tout d'abord merci pour ce code très clair et très instructif !

Je l'ai essayé chez moi et je n'ai pas de problème.
J'ai ensuite essayé de l'adapter à mon cas et je suis sur un problème que je n'arrive pas à résoudre.

Dans certains cas l'algo boucle sur le dernier sommet(quand j'affiche ma liste de sommets j'ai plusieurs fois le dernier sommet dans mon tableau).

Une idée d'où cela peut venir?

Autre chose :

J'ai un graphe avec 36 sommets. Puis - je raisonnablement lancer l'algo dessus et attendre la fin ou est ce que c'est beaucoup trop long ?

merci

[pseudocode]

Dans certains cas l'algo boucle sur le dernier sommet(quand j'affiche ma liste de sommets j'ai plusieurs fois le dernier sommet dans mon tableau).

Une idée d'où cela peut venir?

Fait attention lors de l'affichage a afficher seulement les "depth" premiers élements du tableau.

J'ai un graphe avec 36 sommets. Puis - je raisonnablement lancer l'algo dessus et attendre la fin ou est ce que c'est beaucoup trop long ?

Ça dépend du nombre de chemins possibles dans ton graphe, donc en gros du nombre de "1" dans la matrice d'adjacence. Mais effectivement ça risque de prendre beaucoup de temps !

[siham-gh]

J'ai besoin le meme code mais en C

je essaye le converter en C et bien, mais elle n'affiche qu'un seul chemin

je veux un ptite explication du code quand il exploite le 2 eme 3 eme chemin

merci d'avance

[pseudocode]

je essaye le converter en C et bien, mais elle n'affiche qu'un seul chemin

je veux un ptite explication du code quand il exploite le 2 eme 3 eme chemin

Il y a un appel récursif de la fonction "explore" dans la boucle "for", et une fin de récursion (return) dans le "if".

C'est cela qui provoque l'exploration de tous les chemins, les uns après les autres.

[siham-gh]

C'est bien maint,

je essaye le code en Java et marche sans problème,mais en C m'affiche qu'une seul chemin??? et quelles sont le travaille de taboo

Code C :

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
 
static void explore(int position, int depth) {
	chemin[depth]=position;
 
	// on est sur le sommet d'arrivé -> fini
	if (position==dest) {
		// affiche la solution
		for( i=0;i<=depth;i++ ) printf("%d",chemin[i]);
		printf("\n");
		return;
	}
 
	// sinon...
 
	taboo[position]=TRUE; // on pose un caillou
 
	// on explore les chemins restants
	for( i=0;i<n;i++) {
		if (Mat[position][i]==0 || taboo[i]) continue;
		explore(i,depth+1);
	}
 
	taboo[position]=FALSE; // on retire le caillou
}

[pseudocode]

je essaye le code en Java et marche sans problème,mais en C m'affiche qu'une seul chemin???

Il doit donc y avoir un problème dans le portage du code. Pourtant ton code me semble correct.

et quelles sont le travaille de taboo

Son rôle est de marquer les noeuds du chemin actuel, afin de ne pas repasser deux foix par le meme noeud.

[siham-gh]

Quand terminer parcoure le première chemin comment le variable position prendre le valeur de sommet de départ de nouvelle fois?

[pseudocode]

Il doit donc y avoir un problème dans le portage du code. Pourtant ton code me semble correct.

Ah. J'ai trouvé un truc curieux. la variable "i" n'est pas déclarée localement dans ta fonction. Je suppose que tu l'as déclarée en global, ce qui causerait le bug.

Code C :

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

1
2
3
4
5
6
7
8
9
 
static void explore(int position, int depth) {
 
	int i;  // <-- variable locale !!!
 
	chemin[depth]=position;
 
	// on est sur le sommet d'arrivé -> fini
	(...)

[siham-gh]

Ok, C'est bien...merci

[The Grey]

Bonjour,
pseudocode je viens d'adapter votre code à un algorithme de voyageur de commerce qui doit parcourir récursivement tout les chemins possible et choisir le meilleur et ceci marche bien, ... (j'ai fais ceci car moi et la récursivité on s'entend pas bien du tout !!! )
ce que je compte faire maintenant, c'est une amélioration de mon algorithme qui doit être récursif aussi, mais ne doit parcourir que les chemin qui ont un cout temporaire inférieur au cout optimal déjà parcouru... (cout temporaire: le cout des villes stockés dans path < n) .
voici ce que j'ai fais jusqu'à maintenant pour améliorer mais ça n'affiche que le premier chemin parcouru :
M[][] est une matrice symétrique contenant les couts entre villes,

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
30
31
32
33
34
35
36
37
38
39
 
public void Branch_Bound(int p[], int cheminOpt[], int position, int depth, int M[][]) 
	{
		    path[depth]=position;
			for(int u=0; u<M.length; u++)
				p[u]=path[u]; 
 
			// affiche la solution
			if((depth==n-1)&&elementDif(path))
			{
				for(int i=0;i<=depth;i++)					
					System.out.print(path[i]+" ");
 
				int c=calculCout(path, M);
				if(c<mCout)
				{
					mCout=c;
					Ctemp=c;					
					for(int k=0; k<M.length; k++)
					cheminOpt[k]=path[k];
				}					
				System.out.print("\tc="+c+"\tmCout="+mCout);
				System.out.println();				
			}	
 
		// sinon...
 
		taboo[position]=true; // on pose un caillou
 
		// on explore les chemins restants
		for(int i=0;i<n;i++) 
		{
			if (taboo[i]) continue;
			if(cout(p, M)<Ctemp)
				Branch_Bound(p, cheminOpt, i, depth+1, M); 
		}
 
	taboo[position]=false; // on retire le caillou
	}

Code :

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

1
2
3
4
5
6
7
8
 
	public int cout(int t[], int M[][])
	{
		int Cout=0;
		for(int i=1; i<t.length; i++)
			Cout+=M[t[i-1]][t[i]];
		return Cout; 
	}

Merci pour votre aide.

[pseudocode]

Bonjour,
pseudocode je viens d'adapter votre code à un algorithme de voyageur de commerce qui doit parcourir récursivement tout les chemins possible et choisir le meilleur et ceci marche bien, ... (j'ai fais ceci car moi et la récursivité on s'entend pas bien du tout !!! )

Déjà, il faudrait un "return" à la fin du bloc d'affichage de la solution : inutile de continuer l'exploration si on a trouvé une solution.

Ensuite, c'est quoi tous ces paramètres de la fonction ?