[TSP] Résolution exacte

Version imprimable

Bonsoir a tous,

je suis actuellement sur le probleme du voyageur de commerce (en c++).
En resolution exacte, donc pas de colonie de fourmis, ni d'algo genetique....
Et mon prog ne depasse pas les 50 villes. J'aurais voulu savoir ce que je peut ameliorer :
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 Recurs (Solution Partial, int Minorant) // Calcul du minorant de la matrice de coup int Min = M.Normalize(); Min += Minorant; if (Min > this->_best.GetCost()) return ; // Si dernier couple de ville if (Partial.GetStep() == M.GetSize()) { Partial.SetCost(Min); if (this->_best.GetCost() > Partial.GetCost()) this->_best = Partial; } else { Matrix M1(M); unsigned int X; unsigned int Y; Solution_Base Bis = Partial; // On prend le zero maximisant le minorant afin d'elaguer le plus tot possible if (M.GetEdgeMZ(&X, &Y) == false) return; M1.Left(X, Y); Partial.AddListItem(X, Y, M(X, Y)); if (!Partial.IsCurrentGoodCycle(M.GetSize())) return ; this->Recurs(Partial, Min, M1); M.Right(X, Y); this->Recurs(Bis, Min, M); }
Avec ce code j'arrive a faire 50 villes en une seconde mais pas plus apres ca monte trop rapidement le temps...

Du coup quels ameliorations pourrais-je faire pour augmenter ce seuil ??

Merci d'avance.
Cordialement,
NeoKript

19/10/2010, 20h18
Aleph69

Bonsoir,

commence par déterminer la complexité de ton algorithme.
Ensuite, tu sauras si ce comportement est normal ou non.

Citation:

Envoyé par NeoKript

Bonsoir a tous,

je suis actuellement sur le probleme du voyageur de commerce (en c++).
En resolution exacte, donc pas de colonie de fourmis, ni d'algo genetique....
Et mon prog ne depasse pas les 50 villes. J'aurais voulu savoir ce que je peut ameliorer :

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
 
Recurs (Solution Partial, int Minorant)
// Calcul du minorant de la matrice de coup
int Min = M.Normalize();
  Min += Minorant;
  if (Min > this->_best.GetCost())
    return ;
// Si dernier couple de ville
  if (Partial.GetStep() == M.GetSize())
    {
      Partial.SetCost(Min);
      if (this->_best.GetCost() > Partial.GetCost())
              this->_best = Partial;
    }
  else
    {
      Matrix M1(M);
      unsigned int X;
      unsigned int Y;
      Solution_Base Bis = Partial;
    // On prend le zero maximisant le minorant afin d'elaguer le plus tot possible
      if (M.GetEdgeMZ(&X, &Y) == false)
        return;
      M1.Left(X, Y);
      Partial.AddListItem(X, Y, M(X, Y));
      if (!Partial.IsCurrentGoodCycle(M.GetSize()))
        return ;
      this->Recurs(Partial, Min, M1);
      M.Right(X, Y);
      this->Recurs(Bis, Min, M);
    }

Avec ce code j'arrive a faire 50 villes en une seconde mais pas plus apres ca monte trop rapidement le temps...

Du coup quels ameliorations pourrais-je faire pour augmenter ce seuil ??

Merci d'avance.
Cordialement,
NeoKript

Bonjour NeoKript,
je travaille sur le même problème (TSP) en java, j'ai implémenter le même algorithme (sans le fait de calculer le zero maximisant le minorant afin d'elaguer le plus tot possible), mais ça marche pas comme il faut, voici le programme si vous avez une remarque ou correction de mon programme:

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
59
60
61
 
public void solveTSP(Solution3 Sp, int Sm)
{
  Sp.minorant+=calculMinorant(Sp.M); 	
  if(Sp.minorant>Sm) 
	return; //sortir si solution partielle de cout superieur
                  // à une solution deja trouvée 	
 
  if(Sp.listArt.size()==Sp.M.length-1)
  {
     for(int i=0; i<Sp.listArt.size(); i++)
	{
	 System.out.print(Sp.listArt.get(i).l+" "+Sp.listArt.get(i).c+"\t");			
	}
	System.out.print("cout="+Sp.minorant+"   \t");
 
	if(Sp.minorant<Sm)
	   Sm=Sp.minorant;
	   System.out.print("Sm="+Sm+"\t"); 
           System.out.print(Sp.listArt.size());
	    System.out.println();
  }
  else
   {
       int MD[][]=new int[Sp.M.length][Sp.M.length];
       int MG[][]=new int[Sp.M.length][Sp.M.length];
 
       int Mr[][]=updateMat(Sp.M);	 //Mr=M réduite en enlevant
                                 //le min de chaque ligne puis de chaq colonne 
       Arete t=choixArete(Mr, Sp.listArt); // choisir une arete
 
       if(t!=null)
	 {
	    MG=updateMatLC(t.l, t.c, Mr);	 //m-a-j de la matrice
                                                    // reduite pour l'exploration droite
	    MD=updateMatCase(t.l, t.c, Mr);	  // m-a-j ... gauche 			
	 }
 
	Solution3 SpG=new Solution3(MG);
	Solution3 SpD=new Solution3(MD);		
 
	SpD.listArt.addAll(Sp.listArt);
	if(t!=null)
	    SpD.listArt.add(t);
	SpG.listArt.addAll(Sp.listArt);
	SpD.minorant=Sp.minorant;
	SpG.minorant=Sp.minorant;	
 
	solveTSP(SpD, Sm);
	solveTSP(SpG, Sm);		
     }	
}
 
//avec le constructeur de Solution3:
public Solution3(int M[][])
{
	this.listArt=new ArrayList<Arete>();
	this.M=M;
	this.minorant=0;
	this.cout=0;
}

Merci d'avance,
Cordialement

05/12/2010, 15h59
NeoKript

Salut,

ton code semble à priori correcte,
c'est quoi le soucis exactement ?

Montre moi le détail de tes fonctions updateMat.. et choixArrete, le problème vient peut-être de là.

Citation:

Envoyé par NeoKript

Salut,

ton code semble à priori correcte,
c'est quoi le soucis exactement ?

Montre moi le détail de tes fonctions updateMat.. et choixArrete, le problème vient peut-être de là.

Bonjour NeoKript,
je vous remercie pour votre réponse,
je crois que le problème vient de l'appel récursif sous java, puisque j'ai déjà tester les fonctions ci dessous une par une:

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
 
//calcul du minorant de M
public int calculMinorant(int M[][])
{
        int M2[][]=M;
	int Min=0;
	for(int i=0; i<M.length; i++)
	{
		Min+=minRow(i, M);	
		updateRow(minRow(i, M), i, M2);
	}		
	for(int j=0; j<M.length; j++)
	{
		Min+=minCol(j, M2);
	}
	return Min;
}
//le min de la ligne:
 
public int minRow(int l, int M[][])
{
	int n=M.length;	
	int mr=1000000;
	for(int j=0; j<n; j++)
		{
			if((M[l][j]<mr)&&(M[l][j]!=-1))
				mr=M[l][j];
		}
	if(mr==1000000)
	mr=0;
	return mr;
}
//m-a-j de la ligne:
public void updateRow(int r, int l, int M[][])
{
	int n=M.length;
	for(int i=0; i<n; i++)
		for(int j=0; j<n; j++)
	{
			if(i==l)
				if(M[i][j]!=-1)
					M[i][j]=M[i][j]-r;			
	}
}
 
//min de la colonne:
public int minCol(int c, int M[][])
{
	int n=M.length;
	int mc=1000000;
	for(int i=0; i<n; i++)
	{
		if((M[i][c]<mc)&&(M[i][c]!=-1))
				mc=M[i][c];
	}	
	if(mc==1000000)
		mc=0;	
	return mc;
}
 
//réduire M en enlevant les mins des lignes puis des cols 
//pour avoir des 0 ds chaque ligne et chaque colonne:
public int[][] updateMat(int M[][])
{
   int M2[][]=new int[M.length][M.length];
 
   for(int i=0; i<M.length; i++)
	for(int j=0; j<M.length; j++)
	{
	   if(M[i][j]==-1) 
		M2[i][j]=M[i][j];
           if(M[i][j]!=-1)
	        M2[i][j]=M[i][j]-minRow(i, M);	
	}
 
    int M3[][]=new int[M.length][M.length];
    for(int k=0; k<M.length; k++)
	for(int l=0; l<M.length; l++)
	    {
		if(M2[l][k]==-1)
		    M3[l][k]=M2[l][k];
		if(M2[l][k]!=-1)
		    M3[l][k]=M2[l][k]-minCol(k, M2);
	     }
	return M3;
}
//
public int minRow(int l, int M[][])
{
	int n=M.length;	
	int mr=1000000;
	for(int j=0; j<n; j++)
		{
			if((M[l][j]<mr)&&(M[l][j]!=-1))
				mr=M[l][j];
		}
	if(mr==1000000)
	mr=0;
	return mr;
}
//**
public int minCol(int c, int M[][])
{
	int n=M.length;
	int mc=1000000;
	for(int i=0; i<n; i++)
	{
		if((M[i][c]<mc)&&(M[i][c]!=-1))
				mc=M[i][c];
	}	
	if(mc==1000000)
		mc=0;	
	return mc;
}
 
 
//choix de l'arête:
public Arete choixArete(int M[][], ArrayList<Arete>Sp)
{
   Arete art=new Arete();
   Arete art2=new Arete();
   Arete artf=new Arete();
   int n=M.length;
   artf.l=-1; artf.c=-1;
   for(int i=0; i<n; i++)
 	for(int j=0; j<n; j++)
		if(M[i][j]!=-1)
		{				
		art.l=i; art.c=j; 
		art2.c=i; art2.l=j; 			
		if(!Sp.contains(art))
			if((!Sp.contains(art2))&&(art.l!=art.c))
			{
			artf.l=i;	artf.c=j;
			}									
		}
    if((artf.l==-1)||(artf.c==-1))
	return null;
     return artf;
}
// avec Arete est l'element choisit de M
public Arete()
{
	this.l=-1;
	this.c=-1;
}
 
//m-a-j de la ligne et la colonne de l'élément choisi pour la sol droite
public int[][] updateMatLC(int l, int c, int M[][])
{
	int n=M.length;
	int M2[][]=M;
	if((l!=-1)||(c!=-1))
	{
		for(int i=0; i<n; i++)
			M2[l][i]=-1;
		for(int j=0; j<n; j++)
			M2[j][c]=-1;
	}	
	M2[c][l]=-1; //
	return M2; 
}
 
//m-a-j de l'élément choisi pour l'exploration gauche:
public int[][] updateMatCase(int l, int c, int M[][])
{
	int M2[][]=M;		
	M2=M;
	if((l!=-1)||(c!=-1))
		M2[l][c]=-1;
	M2[c][l]=-1;
	return M2;
}

toutes vos remarques et corrections sont les bienvenues :zoubi: