Discussion :

[The Grey]

voici un résumé de l'algorithme de Little pour la résolution de TSP:

soit la matrice des couts entre villes suivante:

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      ∞

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 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
 
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
Question: comment corriger ou améliorer mon programme ??
toutes vos remarques sont les bienvenues