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.