Discussion :

[nicolas66]

Bonjour,

Pour un projet universitaire, je dois implémenter l'algorithme de Bellman permettant de trouver le plus court chemin dans un graphe ou les arcs sont valués de deux paramètres (distance et temps) qui sont liés ensemble. Le but est de donner l'ensemble des chemins non-dominés pour chaque sommet du graphe.

J'ai réussi à l'implémenter sur un graphe avec des arcs à un seul paramètre mais je ne vois pas trop comment faire pour prendre en compte le second paramètre. Est-ce que quelqu'un pourrait me filer un petit coup de pouce ? Merci d'avance .


Nico.

[progfou]

Peut-être peux-tu essayer de faire deux graphes, chacun ayant son paramètre (l'un la distance, l'autre le temps). Ensuite tu appliques l'algo, puis tu corrèles.
Je n'ai jamais implémenté celà, mais fais des essais avec ça

[nicolas66]

J'ai pas essayé mais normalement on doit prendre en compte les deux paramètres sur le même graphe dans le même temps. D'après mon prof, une fois que l'algo de Bellman est implémenté, il ne reste plus grand chose à faire ... Bref, c'est un peu flou cette histoire.

[FrancisSourd]

Le problème d'avoir les chemins non-dominés est un problème NP-complet. Donc si tu les veux tous il faudra passer par une méthode d'énumération.

Tu peux quand même trouver facilement les chemins qui minimisent une combinaison linéaire des coûts...

Enfin, tu peux peut être utilisée la corrélation distance/temps si tu as des informations dessus. Dans le cas extrême où le temps est proportionel à la distance, il n'y a qu'un seul chemin qui domine tous les autres!

[hansaplast]

je ne sait pas vous, mais je n'ai aucune idée de cet algo, donc, essaie de le donner, ca pourrait ptet en aider a t'aider ^^


(enfin, si c po trop dur a mettre au format HTML... totu depend des formules )

[nicolas66]

En fait je n'arrive pas à trouver l'idée permettant de garder l'ensemble des chemins non-dominés et selon quelles règles je peux comparer le temps et la distance. Notre prof nous a par ailleurs indiqué ceci :



Sur cet exemple, les trois chemins doivent être gardés car on ne peut pas décider si l'un est meilleur que l'autre.

Pour l'algo de Bellman, voici un lien qui l'explique assez clairement je crois ici

[FrancisSourd]

En fait je n'arrive pas à trouver l'idée permettant de garder l'ensemble des chemins non-dominés et selon quelles règles je peux comparer le temps et la distance.

Pour les problèmes bicritères, on remarque que lorsque les solutions non dominées sont triées selon le premier critère croissant, elles sont triées dans l'ordre décroissant du second critères. Une telle liste triée est donc une structure naturelle pour stocker les solutions non dominées.

[nicolas66]

J'ai effectivement vérifié cette propriété sur papier et elle se révèle vraie. Voici un court exemple que notre prof nous a donné.

A un moment donné sur un graphe, on retient 3 arcs dominants parmi ceux-ci :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
 
<Coût | Temps>
<5 | 13>
<6 | 14>
<11 | 9>
 
Le prof nous a dit que l'on ne retenait ici que ces deux solutions :
 
<5 | 14>
<11 | 9>
 
Pourquoi celles-ci et selon quelles règles le choix s'effectue ?

Voici ma structure de données :

Une classe Vertex qui possède une liste d'arcs entrants et sortants, un label, un entier pour la longueur de chemin (utilisée pour Bellman version classique) et un sommet qui indique le prédécesseur de ce sommet (utilisée pour Bellman version classique).
Une classe Arc qui possède les sommets source et destination.
Une classe Graph qui possède une liste de sommets et d'arcs.

Voici l'algorithme de Bellman que j'ai écrit et qui fonctionne sans problèmes (en Java) :

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
 
public void BellmanAlgorithm( Vertex Source )
{
	for( int i=0; i<this.m_Vertices.size(); i++ )
	{
		((Vertex)this.m_Vertices.get(i)).m_Predecessor = null;
 
		if( Source.GetLabel() == ((Vertex)this.m_Vertices.get(i)).GetLabel() )
			((Vertex)this.m_Vertices.get(i)).m_PathLength = 0;
		else
			((Vertex)this.m_Vertices.get(i)).m_PathLength = 32000;
	}
 
	for( int i=0; i<this.m_Vertices.size(); i++ )
	{
		for( int j=0; j<this.m_Arcs.size(); j++ )
		{
			Arc A    = (Arc)this.m_Arcs.get(j);
			Vertex S = (Vertex)A.GetAscendant();
			Vertex D = (Vertex)A.GetDescendant();
 
			if( D.m_PathLength > S.m_PathLength + A.GetDistance() )
			{
				D.m_PathLength  = S.m_PathLength + A.GetDistance();
				D.m_Predecessor = S.GetLabel();
			}
		}
	}
}

Selon vous, quels changements faut-il grossièrement apporter à la structure de données que je possède et l'algorithme que j'ai écrit ? Merci beaucoup à ceux qui pourront me filer un coup de pouce

[nicolas666]

Juste pour info, il est demandé de proposer et d'implémenter une combinaison linéaire des deux critères afin d'obtenir des solutions les plus proches possibles de celles obtenues avec l'algorithme exact. Par contre je ne vois pas du tout comment minimiser une combinaison linéaire des des deux critères ...

[FrancisSourd]

Juste pour info, il est demandé de proposer et d'implémenter une combinaison linéaire des deux critères afin d'obtenir des solutions les plus proches possibles de celles obtenues avec l'algorithme exact. Par contre je ne vois pas du tout comment minimiser une combinaison linéaire des des deux critères ...

C'est aussi l'indication que je te donnais dans mon premier message. Pour t'aider un peu plus, remarque que la longueur d'un chemin est une somme (c'est donc une fonction linéaire). Pour être moins évasif, si tu remplaces le coût (c1,c2) de chaque arc par une combinaison x.c1 + (1-x)c2, tu obtiens un pb mono-critère. Le plus court chemin pour ces nouveaux coûts minimise la combinaison linéaire des deux critères.

Pour adapter Ford-Bellman, il faut remarquer qu'il n'y a pas qu'un seul chemin optimal mais un ensemble de solutions non dominées. L'idée est donc de remplacer ton réel m_PathLength par la structure stockant les solutions non-dominées.

Je n'en dis pas plus, d'autant que je devine que ton prof est un proche collègue...

[nicolas666]

Une question : est-il nécessaire de réaliser un parcours en profondeur puis d'obtenir la numérotation suffixe inverse avant d'appliquer Bellman ?

[demido]

Moi, je suis à la recherche d'un algorithme qui recherche un plus court chemin dans un graphe qui peut comporter des circuits de valeurs négatives.

Si quelqu'un pourra m'aider

Merci d'avance