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);
}
}
}
} |
Partager