Algorithme de little pour la résolution de TSP (voyageur de commerce)
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) //condition d'arret
{
for(int i=0; i<Sp.size()-1; 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 ;)
