Bonjour,
je viens d'appliquer un algorithme récursif pour la résolution du TSP (ou voyageur de commerce), mais le problème c'est que mon programme n'explore pas toutes les branches possibles lors de la recherche récursive.
voici le code si vous pouvez m'aidez :

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
 
// M: est la matrice des couts entre villes
//Sp: tableau d'arêtes de la solution partielle
//Sm: meilleur cout deja trouvé
//minorant: somme des mins des lignes et colonnes
public void solveTSP(int M[][], Arete[] Sp, int minorant, int Sm)
{
  int M2[][]=new int[M.length][M.length];
  M2=M.clone();
  int minorant1=minorant;
  minorant1+=calculMinorant(M2);
 
  if(minorant1>Sm) return;
 
  else
   {					
	if(testFin(M2)&&(testTabRemplie(Sp)))	//condition d'aret
	{
 
             for(int i=0; i<Sp.length; i++)
	         {
	           f(Sp[i]!=null)
			System.out.print(Sp[i].l+" "+Sp[i].c+"\t");			
		  }					
	      System.out.print("cout="+minorant1+"   \t");
 
	      if(minorant1<=Sm)
		  Sm=minorant;
	      System.out.print("Sm="+Sm+"\t"); 	
	      System.out.println();
 
	 }			
     else
      {
	Arete[] Spd=new Arete[M.length+1];
        Arete[] Spg=new Arete[M.length+1];
	Spd=Sp.clone();
	Spg=Sp.clone();
	int Mr[][]=new int[M.length][M.length];
	Mr=updateMat(M2);
	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]; //... Gauche   
       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, Mr);	 // m-a-j ... gauche 
      Spd[t.l]=t;   //ajout de l'arete choisie à la solution partielle droite
 
      solveTSP(MD, Spd, minorant1, Sm);
      solveTSP(MG, Spg, minorant1, Sm);			
	     }			
         }	
    }	
}
Merci d'avance pour toutes remarques ou corrections