Version brute-force de l'algo TSP.

tsp_bf.c

//
//  TSP - BRUTE-FORCE
//
// -> la structure "point" est définie dans tools.h

static double dist(point A, point B){
	return sqrt((B.x-A.x)*(B.x-A.x)+(B.y-A.y)*(B.y-A.y));
}

static double value(point *V, int n, int *P){
	double sum =0;
    for(int i=0;i<n-1;i++){
        sum+= dist(V[P[i]],V[P[i+1]]);
    }
    sum+=dist(V[P[n-1]],V[P[0]]);
	return sum;
}

static double tsp_brute_force(point *V, int n, int *Q){
	int* P=(int*)malloc(n*sizeof(int));
    for(int i=0;i<n;i++) P[i]=i;
    memcpy(Q,P,n*sizeof(int));
    double value_min=value(V,n,P);
    while(NextPermutation(P,n) && running){
        drawTour(V,n,P);
        double val = value(V,n,P);
        if(val< value_min){
            value_min=val;
            memcpy(Q,P,n*sizeof(int));

        }
    }
    free(P);
	return value_min;
}

static void MaxPermutation(int *P, int n, int k){
    for(int i =k+1;i<n-1;i++){
        int tampon =i;
        for(int j=i+1;j<n-1;j++){
            if(P[j]>=P[tampon]) tampon =j;
        }
        int tmp = P[i];
        P[i]=P[tampon];
        P[tampon] = tmp;
    }
	return ;
}

static double value_opt(point *V, int n, int *P,double w){
	double s =0;
    for(int i=0;i<n-1;i++){
        s+= dist(V[P[i]],V[P[i+1]]);
        if(s>w) return -(i+1);
    }
    s+=dist(V[P[n-1]],V[P[0]]);
    if(s>w)return -n;
	return s;
}

static double tsp_brute_force_opt(point *V, int n, int *Q){
    int* P=(int*)malloc(n*sizeof(int));
    for(int i=0;i<n;i++) P[i]=i;
    memcpy(Q,P,n*sizeof(int));
    double value_min=value(V,n,P);
    int k=0;
    while(NextPermutation(P,n) && running){
        drawTour(V,n,P);
        double val = value_opt(V,n,P,value_min);
        if(val <0){
            k= -val;
            MaxPermutation(P,n,k-1);

        }
        else if(val< value_min){
            value_min=val;
            memcpy(Q,P,n*sizeof(int));
        }
    }
    free(P);
	return value_min;
}