Parcours de tous les chemins d'un graphe
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
Précisions sur ce que je cherche à faire
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
voyageur de commerce recursivité
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, :zoubi: ... (j'ai fais ceci car moi et la récursivité on s'entend pas bien du tout !!! :calim2: )
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:
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:
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.
Algorithme de Little pour la resolution d'un TSP
voici un résumé de l'algorithme de Little pour la résolution de TSP:
soit la matrice des couts entre villes suivante:
Code:
1 2 3 4 5 6 7 8
|
A B C D E F
A ∞ 0(2) 3 2 13 1
B 2 ∞ 2 8 0(6) 23
C 3 11 ∞ 0(0) 4 0(1)
D 0(2) 1 0(2) ∞ 7 9
E 13 5 6 0(2) ∞ 2
F 16 1 6 0(1) 14 ∞ |
1*On soustrait de chaque ligne le plus petit élément et on fait de même pour les colonnes. D’ou une première évaluation minimale de la longueur du chemin : 16 = 13 + 3. (16= somme des min des lignes puis des colonnes ou minorant).
2*on choisit une arête aléatoirement BE par exemple et on explore la recherche avec une solution partielle de la branche droite contenant BE et une autre gauche ne contenant pas BE.
la modification de la matrice droite est celle obtenue en modifiant la ligne B par des infinies, et la colonne E par des infinies aussi.
par contre la matrice de l'exploration gauche consiste à modifier que l'élément BE de la matrice par l'infinie...
**on refait les étapes 1 et 2 pour chaque noeud de l'arbre d'exploration, et on n'explore que les branches ayant un minorant < a une solution déjà trouvé.
voici l'implémentation de cet algorithme en Java:
Code:
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
|
public void solveTSP(int M[][], ArrayList<Arete> Sp, int minorant, int Sm)
{
minorant+=calculMinorant(M);
if(Sp.size()==M.length-1) //condition d'arret
{
for(int i=0; i<Sp.size(); i++) //les solutions trouvées
{
System.out.print(Sp.get(i).l+" "+Sp.get(i).c+"\t");
}
System.out.print("cout="+minorant);
System.out.println();
if(minorant<Sm)
Sm=minorant;
}
ArrayList<Arete> SpD=Sp; //Solution partielle de l'exploration droite
ArrayList<Arete>SpG=Sp; //... gauche
int Mr[][]=updateMat(M); //Mr=M réduite en enlevant le min de
//chaque ligne puis des colonne
t=choixArete(Mr);
int MD[][]=new int[M.length][M.length]; //matrice d'exploration Droite
int MG[][]=new int[M.length][M.length]; //matrice d'exploration Guauche
MD=updateMatLC(t.l, t.c, Mr); //réduction de la matrice droite
MG=updateMatCase(t.l, t.c, Mr); // m-a-j ... gauche
SpD.add(t); //ajout de l'arete choisie à la solution partielle droite
if(minorant>Sm) return; //sortir si solution partielle de cout > Sm
solveTSP(MD, SpD, minorant, Sm ); //exploration droite
solveTSP(MG, SpG, minorant, Sm); //exploration gauche
} |
Problème: ce code ne donne pas la solution optimale :aie:
Question: comment corriger ou améliorer mon programme ??
toutes vos remarques sont les bienvenues ;)