Discussion :

[saraHij]

Salut ,
Je travaille sur le fameux probleme du voyageur de commerce (TSP) qui consiste à minimiser le cout des tournés
J'utilise les instances de l'API TSPLIB , voila le site : https://www.iwr.uni-heidelberg.de/gr.../TSPLIB95/tsp/
Jutilise le fichier :ulysses22.tsp qui represente les coordonées de 22 villes
Donc mon programme :

• li les coordonées à partir du fichier
• Génere la matrice des distances
• Et calcule le cout de la tourné ,

Voila le code :

Code :

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
 
#include <stdio.h>
#include <math.h>
#define NbrCities 22
 
double city_x[NbrCities], city_y[NbrCities];
float citymap[NbrCities*NbrCities];
int ids[NbrCities];
 
 
 float L2distance(float x1, float y1, float x2, float y2) {
    float x_d = pow(x1 - x2, 2);
    float y_d = pow(y1 - y2, 2);
    return sqrt(x_d + y_d);
}
 
 
void costMatrix(float *citymap){
    for(int i=0; i<NbrCities; i++) {
        for(int j=0; j<NbrCities; j++) {
            if(i!=j) {
                citymap[i*NbrCities+j] = L2distance(city_x[i], city_y[i], city_x[j], city_y[j]);
            } else {
                citymap[i*NbrCities+j] = 0;
            }
        }
     }
}
 
 
float cost(int* population, float* citymap) {
 
   float distance = 0;
   float population_cost;
    for (int j = 0; j < NbrCities-1; j++) {
        distance += citymap[ NbrCities*population[j] + population[j+1] ];
    }
        distance += citymap[ NbrCities*population[0] + population[NbrCities-1] ];
 
     return distance;
}
 
 
int main()
{
 
    FILE *myFile,*out;
    myFile = fopen("test.txt", "r");           
    out = fopen("out.txt", "w");
 
    int tour[]={1,14,13,12,7,6,15,5,11,9,10,19,20,21,16,3,2,17,0,4,18,8};
 
   myFile = fopen("test.txt", "r");
        for (int i = 0; i < NbrCities; i++)
            {
               fscanf(myFile,"%d %lf %lf",&ids[i],&city_x[i],&city_y[i]); 
            }
 
        costMatrix(citymap);
 
 
 
printf("  %f ",cost(tour,citymap));
 
 
 return 0;
 
}

Mon problem est que normalement comme le site indique la solution optimale est : 7013
et moi en executant ce probleme j'ai retouver une valeur inférieur à la solution :153 ce qui n'est pas normale ,
Je sais pas ou est le probléme !! merci d'avance pour l'aide.

[Sve@r]

Bonjour

Déjà pour la forme de ton code, tu as une façon de coder merdique. Tu ouvres deux fois ton fichier, tu ne le fermes jamais. Tu utilises des globales que tu passes quand-même en paramètre aux fonctions. Tu définis des variables sans les utiliser (population_cost). Tu mets des espaces mis au hasard avant le nom de la fonction. Là ça va que le code est court, mais un code plus long je ne l'aurais même pas regardé.
D'autant plus que cela t'avait déjà été signalé.

Accessoirement, il est d'usage de définir les macros en majuscules et les valeurs entre parenthèses (#define NBRCITIES (22)). Les majuscules c'est pour éviter de les confondre avec des variables et les parenthèses c'est juste pour des raisons d'homogénéïté (quand on définit des macros paramétrées, les parenthèses sont obligatoires pour éviter les erreurs de priorités et par extension on met alors des parenthèses tout le temps même quand la valeur est en dur).
Tu pourrais aussi créer une structure pour gérer les x et y ce qui t'éviterait de dédoubler tes tableaux. Ce n'est pas que ce soit primordial mais ça donne de bons réflexes. Ok, c'est chiant de préparer ses outils quand on veut aller vite mais dans la plupart des cas, on y gagne ensuite en clarté et en modularité.

Et surtout ben on n'utilise pas de globales dans le but de "se simplifier la programmation" car cela mêne souvent au crash après coup. Les globales sont faites quand on ne peut pas faire autrement.

Sinon pour le fond, ben effectivement le résultat donne 153. Sauf que tes données diffèrent de celles du site. Car dans le fichier "ulysses22.opt.tour", les 4 dernières valeurs sont "22, 4, 18, 8" (toi tu as écrit "0, 4, 18, 8"). Ceci dit, même si on met "22" dans ton code ça donne 146 et pas 7013. Mais bon, tu nous parles d'un algo sans le décrire comme si on était sensé le connaitre (enfin j'en connais un mais qui ne fait référence qu'aux distances entre les villes et qui ne mentionne absolument pas un quelconque "tour").
Or ici c'est un forum C, pas un forum algo (qui existe aussi mais ailleurs) donc on est bons en C mais on ne connait pas forcément tous les algos. Je te conseille donc d'aller leur poser la question en y décrivant ta façon de raisonner (pseudo-code). Question C, ton code compile et tourne malgré ses imperfections donc nous on n'y peut rien (sauf si quelqu'un connait cet algo et passe par ici). Toutefois tu peux quand-même faire le calcul à la main voir si ça donne bien 7013 (et peut-être alors qu'en faisant ça à la main tu trouveras ton erreur).
Il y a juste un petit truc ici qui me chiffonne

Code c :

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

1
2
3
4
   for (j = 0; j < NbrCities-1; j++) {
        distance += citymap[ NbrCities*population[j] + population[j+1] ];
    }
        distance += citymap[ NbrCities*population[0] + population[NbrCities-1] ];

A la dernière itération, "j" vaut "NbrCities-2". Donc quand tu additionnes population[j+1] tu additionnes population[NbrCities-1]. Or juste en dessous tu additionnes encore population[NbrCities-1]. Est-ce correct par rapport à l'algo ? Et en plus, qu'est-ce qui garantit que "NbrCities*population[j] + population[j+1]" sera inférieur à "NbrCities * NbrCities" (taille du tableau "citymap") ???

PS: Juste pour te montrer ton code correctement écrit

Code c :

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
#include <stdio.h>
#include <math.h>
#define NB_CITIES 22
 
typedef struct {
	double x;
	double y;
} t_coord;
 
float L2distance(const t_coord* const p1, const t_coord* const p2) {
	return sqrt(pow(p1->x - p2->x, 2) + pow(p1->y - p2->y, 2));
}
 
void costMatrix(float *citymap, t_coord *city) {
	int i, j;
	for(i=0; i < NB_CITIES; i++) {
		for(j=0; j < NB_CITIES; j++)
			citymap[i*NB_CITIES+j]=i!=j ?L2distance(&city[i], &city[j]) :0;
	}
}
 
float cost(int* population, float* citymap) {
	float distance=0;
	int i;
	for (i=0; i < NB_CITIES-1; i++)
		distance+=citymap[NB_CITIES*population[i] + population[i+1]];
	distance+=citymap[NB_CITIES*population[0] + population[NB_CITIES-1]];
 
	return distance;
}
 
int main() {
	FILE *myFile;
	int i;
	int ids;
 
	int tour[]={1, 14, 13, 12, 7, 6, 15, 5, 11, 9, 10, 19, 20, 21, 16, 3, 2, 17, 22, 4, 18, 8};
	float citymap[NB_CITIES*NB_CITIES];
	t_coord city[NB_CITIES];
 
	myFile=fopen("test.txt", "r");
	for (i=0; i < NB_CITIES; i++)
		fscanf(myFile, "%d %lf %lf", &ids, &city[i].x, &city[i].y); 
	fclose(myFile);
 
	costMatrix(citymap, city);
	printf("%f\n", cost(tour, citymap));
	return 0;
}

Il reste le même (donc donne le même résultat) mais au-moins on y voit plus clair...

[saraHij]

Bounjour ,
Tout d'abord merci pour vos remarques et corrections .
Donc en ce qui concerne l'algo voila un exemple :
ciyimap est la matrice des distances (symétrique) pour 4 villes ça doit être par exemple comme ça :

	0	1	2	3
0	0	122	40	50
1	122	0	30	210
2	40	30	0	99
3	50	219	99	0

Pour calculer le coût d'une tournée : 2-0-1-3 il faut calculer la distance entre 2 et 0 , 0 et 1 , 1 et 3 et puis le coût de retour : 3 et 2
Ici par exemple on a 4 villes , la matrice des coûts (citymap) est un tableau de 1 dimension
donc les données sont stockés : 0 122 40 50 122 0 30 210 40 30 0 99 50 219 99 0
Pour calculer alors les coût j'ai utilisé la fonction :

Code :

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

1
2
3
4
5
6
7
8
9
float cost(int* individu, float* citymap) {
	float distance=0;
	int i;
	for (i=0; i < NB_CITIES-1; i++)
		distance+=citymap[NB_CITIES*individu[i] + individu[i+1]];
	distance+=citymap[NB_CITIES*individu[0] + individu[NB_CITIES-1]];
 
	return distance;
}

elle prend en paramètre la tournée qui est : 2-0-1-3
donc
La première itération : coût entre 2 et 0 , la matrice des coûts (citymap) est 40 : puisque la matrice est symétrique c'est soit : citymap[8] ou citymap[2].
La formule est : citymap[ 4 * tournee[0] + tournee[1 ]] ==> citymap[ 4 * 2 + 0 ] ==> citymap[ 8 ] = 40
ou : citymap[ tournee[0] +4 * tournee[1] ] ==> citymap[ 2 + 4* 0 ] ==> citymap[ 2 ] =40

donc on a besoin de NB_CITIES-1 itérations
en plus de la distance de retour entre 3 et 2.

Pour le résultat normalement le site montre les solutions optimal calculé exacte .

[Sve@r]

Effectivement, ton algorithme est correct.
J'ai appliqué ton exemple sur ton algo codé en Python (plus rapide pour tester) et le résultat donne 471

Code python :

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
#!/usr/bin/env python3
# coding: utf-8
dist=(
	(0, 122, 40, 50),
	(122, 0, 30, 210),
	(40, 30, 0, 99),
	(50, 210, 99, 0)
)
tournee=(2, 0, 1, 3)
 
def cost(dist, tournee, l=0):
	dist=tuple(x for d in dist for x in d)
	d=0
	for i in range(l-1):
		pos=l * tournee[i] + tournee[i+1]
		print(i, pos, dist[pos])
		d+=dist[pos]
	# for
	pos=l * tournee[0] + tournee[l-1]
	print(pos, dist[pos])
	d+=dist[pos]
	return d
# cost()
 
print(cost(dist, tournee, 4))

Et effectivement le déplacement de 2 à 0 (40) puis de 0 à 1 (122) puis de 1 à 3 (210) puis de 3 à 2 (99) fait bien 471.

Maintenant parlons un peu de ta façon de calculer les distances. Tu appliques la formule de la norme d'un vecteur (qui est issue de celle de Pythagore). mais cette formule ne vaut que pour des coordonnées placées dans un plan. Or les coordonnées des villes du fichier "ulysse22" sont des coordonnées géographiques (positionnées sur une sphère de rayon approximatif égal à 6400km).

Si par exemple j'utillise ta méthode pour calculer la distance entre Marseille (43.3 ; 5.4) et Lyon (45.75 ; 4.85), le calcul donne racine((45.75 - 43.3)^2 + (4.85 - 5.4)^2) = racine(6.0025 + 0.3025)=racine(6.305)=2.51. Or Lyon et Marseille sont situées à environ 300km l'une de l'autre.

Donc voilà. Il te faut prendre en compte la rotondité de la Terre pour calculer les vraies distances...

[saraHij]

Oui vous avez raison , merci beaucoup pour l'aide !!!