TSP.zip_tsp_tsp回溯法_回溯法_回路长度最短_最短长度回路

#include<stdio.h> #include<stdlib.h> #include<time.h> #include<string.h> #include<math.h> int n; //the number of the vertex int m; //the number of the color int sum = 0; int t1 ,t2; int site = 0; double cc ; typedef struct BASE{ //the struct of the site char id[30]; int num; float jing; float wei; } BASE; int x[50]; int bestx[50]; BASE base[50]; double c[100][100]; double bestc ; void swap(int &a,int &b){ int temp; temp = a; a = b; b = temp; } void Trackback(int i,int n,float cc){ site++; //printf("the first %f\n",cc); if(i == n){ //printf("fuck %f !",cc); //printf("the site %f %f\n",c[x[n-1]][x[n]],c[x[n]][1]); int temp; if(n == 20) temp = 18; else temp = 13; if(fabs(c[x[n-1]][x[n]]-99999)>0.1 && fabs(c[x[n]][temp]-99999)>0.1&&(cc+c[x[n-1]][x[n]]+c[x[n]][temp] < bestc || fabs(bestc-99999)<0.1)){ for(int j = 1; j <= n; j++){ bestx[j] = x[j]; // printf("%f\n",bestc); } if(n == 20) bestc = cc+c[x[n-1]][x[n]] + c[x[n]][18]; if(n == 15) bestc = cc+c[x[n-1]][x[n]] + c[x[n]][13]; } } else{ for(int j = i; j <= n; j++) if(fabs(c[x[i-1]][x[j]]-99999)>0.1 && (cc+c[x[i-1]][x[j]] < bestc || fabs(bestc - 99999)<0.1)){ int temp; temp = x[i]; x[i] = x[j]; x[j] = temp; cc += c[x[i-1]][x[i]]; Trackback(i+1,n,cc); cc -= c[x[i-1]][x[i]]; temp = x[i]; x[i] = x[j]; x[j] = temp; } } } int main(){ int num; printf("please input the number of the sites:15 or 20\n"); scanf("%d",&num); FILE *fp; float temp; memset(x, 0, sizeof(x)); memset(bestx, 0, sizeof(x)); for(int i = 1;i<=num;i++) x[i] = i; if(num == 20){ x[1] = 18; x[18] = 1; } else{ x[1] = 13; x[13] = 1; } if(num == 15){ if((fp = fopen("site.txt","r"))!=NULL){ for(int i = 1;i<=15;i++){ fscanf(fp,"%s",&base[i].id); } for(int i = 1;i<=15;i++){ for(int j = 1; j<=15;j++){ fscanf(fp,"%lf",&c[i][j]); } } } } else{ if((fp = fopen("site2.txt","r"))!=NULL){ for(int i = 1;i<=20;i++){ fscanf(fp,"%s",&base[i].id); } for(int i = 1;i<=20;i++){ for(int j = 1; j<=20;j++){ fscanf(fp,"%lf",&c[i][j]); } } } } cc = 0; bestc = 99999; clock_t t1 = clock(); Trackback(2,num,cc); clock_t t2 = clock(); double t3 = double (t2-t1)/CLOCKS_PER_SEC; printf("the program costs %lf s\n",t3); for(int i= 1;i <=num;i++) printf("%s -> ",base[bestx[i]].id); printf("%s\n",base[bestx[1]].id); printf("the distance of the is %lf",bestc); }