Résolution du 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
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);			
	     }			
	}	
     }	
}

problème:
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

Code:

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

Question:
est ce que vous pouvez m'aider à corriger ce code ?
merci d'avance