Algorithme de little pour la résolution de TSP (voyageur de commerce)

**The Grey** · 28/11/2010, 13h05

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

**chaplin** · 01/12/2010, 19h29

Comment corriger ou améliorer mon programme ??
Il faut consulter un expert en optimisation, seulement c'est payant

si on veut avoir la meilleure solution du marché.

**The Grey** · 01/12/2010, 23h23

Envoyé par chaplin

Comment corriger ou améliorer mon programme ??
Il faut consulter un expert en optimisation, seulement c'est payant

si on veut avoir la meilleure solution du marché.

le savoir n'est bon que s'il est partagé

**Branch** · 03/12/2010, 19h27

Envoyé par Faissall

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	
}

Salut,

je vois déjà quelques petit problèmes dans ton code...

1/

Tu pars du principe que si tu passe Sm à solveTSP et qu'il est modifié au cours de l'appel à solveTSP alors il sera modifié dans la méthode ayant appelé solveTSP. Hors ce n'est pas le cas... Pour t'en convaincre tu peux exécuter le code suivant :

Code java :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
 
public static void main(String[] args)
{
   int a = 2;
   System.out.println(a); // 2
   modify(a);
   System.out.println(a); // 2
}
 
public static void modify(int a)
{
     a = 3;
}

2/

Lorsque tu fais

Code java :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
ArrayList<Arete> SpD=Sp;
ArrayList<Arete>SpG=Sp;

tu fait une copie des référence pas des objets :s

Du coup lorsque tu fait

Code java :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
SpD.add(t);

tu ajoute aussi t à SpG se qui veut dire qu'au lieu d'avoir SpG.size() = SpD.size() - 1 tu as SpG.size() = SpD.size(). Du coup tu peux penser avoir sélectionné suffisament d'arcs pour que ton algorithme ait trouvé une solution réalisable alors que ce n'est pas le cas

Pour contourner ce problème je te propose :

Code java :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
ArrayList<Arete> SpD= (ArrayList<Arete>)(Sp.clone());
ArrayList<Arete>SpG= (ArrayList<Arete>)(Sp.clone());

Je devine également d'autres problèmes au niveau de la modification de ta matrice de distance

Si les modifications que je t'ai suggéré ne suffisent pas, n'hésite pas à poster tes autres méthodes, je pourrais peut-être t'aider

Bon courage

**The Grey** · 03/12/2010, 21h36

Envoyé par Branch

Salut,

je vois déjà quelques petit problèmes dans ton code...

1/

Tu pars du principe que si tu passe Sm à solveTSP et qu'il est modifié au cours de l'appel à solveTSP alors il sera modifié dans la méthode ayant appelé solveTSP. Hors ce n'est pas le cas... Pour t'en convaincre tu peux exécuter le code suivant :

Code java :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
 
public static void main(String[] args)
{
   int a = 2;
   System.out.println(a); // 2
   modify(a);
   System.out.println(a); // 2
}
 
public static void modify(int a)
{
     a = 3;
}

2/

Lorsque tu fais

Code java :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
ArrayList<Arete> SpD=Sp;
ArrayList<Arete>SpG=Sp;

tu fait une copie des référence pas des objets :s

Du coup lorsque tu fait

Code java :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
SpD.add(t);

tu ajoute aussi t à SpG se qui veut dire qu'au lieu d'avoir SpG.size() = SpD.size() - 1 tu as SpG.size() = SpD.size(). Du coup tu peux penser avoir sélectionné suffisament d'arcs pour que ton algorithme ait trouvé une solution réalisable alors que ce n'est pas le cas

Pour contourner ce problème je te propose :

Code java :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
ArrayList<Arete> SpD= (ArrayList<Arete>)(Sp.clone());
ArrayList<Arete>SpG= (ArrayList<Arete>)(Sp.clone());

Je devine également d'autres problèmes au niveau de la modification de ta matrice de distance

Si les modifications que je t'ai suggéré ne suffisent pas, n'hésite pas à poster tes autres méthodes, je pourrais peut-être t'aider

Bon courage

Je vous remercie pour votre réponse,
j'ai modifié ce que vous m'avez demandé, mais comme vous dites, je crois que c'est pas le seul beug

, je sais bien que je ne suis pas expert en Java, j'essaye de programmer et apprendre des gens comme vous...
pour les autres méthodes je les ai testé une par une avant, mais pour s'assurer les voilà, je vous demande des remarques ou corrections:

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
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

**The Grey** · 08/12/2010, 23h04

Envoyé par Faissall

Je vous remercie pour votre réponse,
j'ai modifié ce que vous m'avez demandé, mais comme vous dites, je crois que c'est pas le seul beug

, je sais bien que je ne suis pas expert en Java, j'essaye de programmer et apprendre des gens comme vous...
pour les autres méthodes je les ai testé une par une avant, mais pour s'assurer les voilà, je vous demande des remarques ou corrections:

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
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

Aucune idée ??!!

**The Grey** · 10/12/2010, 11h04

Presque résolu, reste à détecter les cycles,
proposez si vous avez des idées svp

Algorithme de little pour la résolution de TSP (voyageur de commerce)

Algorithmes et structures de données

Discussions similaires

Partager

Partager