voici un résumé de l'algorithme de Little pour la résolution de TSP:
soit la matrice des couts entre villes suivante:
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).
Code : Sélectionner tout - Visualiser dans une fenêtre à part
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 ∞
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:
problème:
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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58 public void solveTSP(int M[][],Arete[] Sp, int CoutSp, int Sm, int Mcout[][]) { int M2[][]=new int[M.length][M.length]; M2=M.clone(); CoutSp=calculCout(Sp, Mcout); if(CoutSp>Sm) return; else { if(testFin(M)) //condition d'aret { { for(int i=0; i<Sp.length; i++) { if(Sp[i]!=null) System.out.print(Sp[i].l+" "+Sp[i].c+"\t"); } System.out.print("cout="+CoutSp+" \t"); if(CoutSp<=Sm) Sm=CoutSp; System.out.print("Sm="+Sm+"\t"); System.out.println(); } } else { Arete[] Spd=new Arete[M.length+1]; Arete[] Spg=new Arete[M.length+1]; int CoutSpd=CoutSp; int CoutSpg=CoutSp; Spd=Sp.clone(); Spg=Sp.clone(); int Mr[][]=new int[M.length][M.length]; int Mr1[][]=new int[M.length][M.length]; Mr=updateMat(M2); Mr1=Mr.clone(); Arete t=(Arete) choixArete2(Mr, Spd); //choisir une arete int MD[][]=new int[M.length][M.length]; //matrice d'exploration //Droite int MG[][]=new int[M.length][M.length]; //matrice d'exploration //Guauche if(t!=null) { MD=updateMatLC(t.l, t.c, Mr); //m-a-j de la matrice // reduite pour l'exploration droite MG=updateMatCase(t.l, t.c, Mr1); // m-a-j ... gauche Spd[t.l]=t; //ajout de l'arete choisie à la solution // partielle droite solveTSP2(MD, Spd, CoutSpd, Sm, Mcout); solveTSP2(MG, Spg, CoutSpg, Sm, Mcout); } } } }
ce programme n'explore qu'une seule solution complète, voici un extrait
des arêtes explorés :
//0 3 est l'arete de la ligne 0 et la colonne 3
Question:
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 0 3 1 2 2 0 3 1 cout=12 Sol_meilleur=12 1 2 2 0 3 1 cout=6 Sm=6 0 3 2 0 3 1 cout=11 Sm=11 2 0 3 1 cout=5 Sm=5 0 3 1 2 3 1 cout=10 Sm=10 1 2 3 1 cout=4 Sm=4 0 3 3 1 cout=9 Sm=9 3 1 cout=3 Sm=3 0 3 1 2 2 0 cout=9 Sm=9 1 2 2 0 cout=3 Sm=3 0 3 2 0 cout=8 Sm=8 2 0 cout=2 Sm=2 0 3 1 2 cout=7 Sm=7 1 2 cout=1 Sm=1 0 3 cout=6 Sm=6 cout=0 Sm=0
est ce que vous pouvez m'aider à corriger ce code ?
merci d'avance
Partager