Discussion :

[ADSL[fx]]

bonjour, je fais en ce moment un programme (en Java) pour determiner le plus court chemin dans le metro. j'ai alors utilisé dijkstra. jusque la tout va bien ca fonctionne.
mais je dois aussi donner la possibilité de donner tous les plus courts chemins en cas d'egalité, et dijktra n'en donne qu'un. et pour compliquer encore plus, il faut introduire une marge possible (par exemple : chercher tous les chemins de meme longueur que le plus courts trouvé, a +5% de trajet en plus pres). j'ai alors programmé la chose suivante :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
public void autresChemins(Vector sommets,int T[][],int matriceArcs[][],int d,
    										int p,int m,Vector tousLesChemins) {
    	for (int i=0; i<sommets.size(); i++)
    if ((matriceArcs[i][p]!=-1)&& (T[0][i]+matriceArcs[i][p])<=(T[0][p]+m))
    	    		    {
    			tousLesChemins.insertElementAt(sommets.elementAt(i),0);
    			if (i!=d) {
    				m=m+T[0][i]+matriceArcs[i][p]-T[0][p];
    				autresChemins(sommets,T,matriceArcs,d,i,m,tousLesChemins);    				
    			}
    		}
    }

cela marche bien dans les cas favorables, mais il y a des cas ou il me sort l'erreur : "stack overflow"
si un arc est a 0 dans les 2 sens; ou si la marge est trop grande

T[][] est le tableau récupéré dans dijstra : cela donne la distance au sommet de depart, et le sommet precedent. d est le depart, p l'arrivée; m la marge, tousLesChemins le tableau de resultats; matriceArcs[][] le tableau de spoids des arcs.

voyez vous comment faire ?

[KiLVaiDeN]

Salut,

Je te propose une idée : utiliser dijkstra, mais enlever certaines correspondances, afin d'obtenir des plans parallèles;

Par exemple tu calcules dijkstra sur un premier trajet, ça te trouve le chemin. Tu enlèves alors la première correspondance ( si il y en a une ) et tu repasses dijkstra !

[ADSL[fx]]

ah tu veux dire qu'on enleve un arc a chaque fois ?
mais comment savoir lequel, et si on en enleve un, ca va annuler des chemins valables qui passaient par cet arc, ou si cet arc n'etait pas sur le trajet on va retrouver le meme chemin.

pour en revenir a mon stack overflow, ca veux dire quoi , qu'il y a trop d'appels recursifs donc memmoire saturée ?

[KiLVaiDeN]

C'était une idée que je proposais : tu utilises dijkstra, et tu enlèves une correspondance du chemin trouvé, ça force au prochain passage de prendre un autre chemin !

Peut-être y-a-t-il un moyen plus propre et normalisé pour résoudre ce problème, mais je ne le connais pas...

Sinon, yes stack overflow c'est exactement ce que tu dis : la pile est pleine car trop d'appel consécutive de ta méthode récursive, sans retour.

[scr]

Enlever un arc ! Tu risques de perdre des chemins !

Pour le problème de stack overflow, si tu veux traiter un arbre d'une taille importante, il faut eviter les fonctions recursives.

Le mieux je pense c'est de modifier un peu l'algo de dijkstra afin de stocker une liste de chemins valables plutot que de ne conserver que le meilleur.

[ADSL[fx]]

ça semble bon en effet, mais a la fin pour lire tous ces chemins, il faudra bien parcourir toutes les listes renvoyant sur d'autres listes, ... , on risque de revenir au meme probleme non ?

[scr]

Des listes renvoyant sur d'autres listes ? Je ne vois pas bien ce que tu veuix dire.

Retomber sur le même problème ? de stack overflown ?

[FrancisSourd]

Il existe effectivement des graphes de n sommets avec 2^n chemins de même longueur. En pratique, il y en a toutefois moins.

Une solution pour éviter tout stockage exponentiel consiste à calculer le plus court chemin puis à faire un algorithme de type branch-and-bound qui énumérerait tous les chemins. La borne inférieure est simplement le coût du plus court chemin. Evidemment, le fichier de sortie peut être très gros!

[ADSL[fx]]

re,
j'ai trouvé une solution pour eviter ce stack overflow : ne faire un appele recursif que quand on change de chemin, et sinon on suit le tableau du plus court chemin deja calculé par dijkstra. on n'a donc pas plus d'appels recursifs que de plus court chemin, ça marche deja mieux. voila le code de la procedure :

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
public void autresChemins(Vector sommets,int T[][],int d,int p,int m,Vector v,
    																	int prec) {
    	Vector chemin=new Vector();
    	for (int i=0; i<v.size(); i++) // on recopie le chemin deja parcouru
    		chemin.add(v.elementAt(i));
 
        while(p!=d) {
        	chemin.insertElementAt(sommets.elementAt(p),0);
        	for (int i=0; i<sommets.size(); i++) 
        	// un chemin secondaire ne doit pas revenir sur le sommet precedent, ni 
        	// suivre le plus court chemin, et avoir un poids pas trop elevé	
        		if (matriceArcs[i][p]!=-1 && i!=T[1][p] && i!=prec &&	
        		   (m>(T[0][i]+matriceArcs[i][p]-T[0][p])))
				   	{
        					m=m-T[0][i]-matriceArcs[i][p]+T[0][p];
        					autresChemins(sommets,T,d,i,m,chemin,p); 
				   	}        		
        	  // cas du cul de sac : si on est revenu en arriere, on arrete
        	  // le parcours et efface le chemin parcouru
        	  if (chemin.size()>2 && chemin.elementAt(0)==chemin.elementAt(2)) {
        	  	chemin.removeAllElements();
        	  	break;
        	  }
        	  prec=p;	
              p=T[1][p];
        }
        chemin.insertElementAt(sommets.elementAt(p),0);
        if (chemin.size()>1)
        	for (int i=0;i<chemin.size();i++)
        		tousLesChemins.add(chemin.elementAt(i));
    }

lancé dans le programme a partir de cette commande :

Code :

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

1
2
autresChemins(sommets,T,pDepart,pArrivee,m*5*T[0][pArrivee]/100,bidon,
          																pArrivee);

je crois que j'ai defini toutes les variables plus haut sinon demandez moi.


alors LE PROBLEME :
il ne trouve pas les chemins a parcourir "a contresens", c'est a dire parcourir les branches telles que pour chaque point de la branche, on devrais normalement aller en sens inverse pour aller au point de depart. vous voyez ce que je veux dire ?
apres avoir essayé plein de trucs, je n'ai pas trouvé, ca ne faisait que poser d'autres problemes.[/quote]

[scr]

L'algo doit fonctionner en utilisant des arcs orientés. Cad que tu n'as le droit de parcourir l'arc que dans un sens.

Pour résoudre ton problème, il faut que tu définisses tes arcs dans les deux sens !