蛮力法求解旅行商问题

先看下运行过程：/*此程序用蛮力法求解旅行商问题，输入城市数目得出最优解，将运算时间存储到外部文件，精确到毫秒*/#includestdio.h#includestdlib.h#includestring.h#includetime.h#includesys/time.h#includeassert.h#defineMAXSIZE99999//#defineCITYNUM5/*4个城市的话，其实全排列的只有3个，另外一个是起点固定的*///#defineTOTLE15/*4个城市对应的道路一共有6条*/#defineMAX32intCITYNUM=0;intTOTLE=0;charcity[MAXSIZE]={0};/*和下面这个数组组成两个城市之间的道路*/charcitytwo[MAXSIZE]={0};intdistance[MAXSIZE]={0};/*存放城市间距离*/intvalueall[MAXSIZE]={0};/*最后放每次运算的路径值*/intall=0;/*对应上面的*/charbackarray[MAXSIZE]={0};longintbbb=0;intccc=0;/*文件里存了全部的道路和距离比如：ab7，读取数据到三个数组*/voidread(){intnn=1,ii=1;inti=1;intp;FILE*fp;fp=fopen(in.dat,rb);while(!feof(fp)){p=fscanf(fp,%c%c%d\n,&city[nn],&citytwo[nn],&distance[nn]);/*读取的时候遇到回车所以fscanf时候加\n*/if((p!=EOF)){nn++;i++;TOTLE++;}else{break;}}fclose(fp);printf(city);printf(distance\n);for(ii=1;iinn;ii++){printf(%c%c%d\n,city[ii],citytwo[ii],distance[ii]);}}/*两两互换*/voidswap(int*l,int*r){inttemp;temp=*l;*l=*r;*r=temp;}/*打印各种东西...*/voidprint(intncount,int*val){intn=0;inti;intii=0;intnnn=0;intsum=0;/*每次运算加起来的最后路程*/intvalue[MAXSIZE]={0};/*存放每次运算上面那个结果*/printf(a-);for(;nncount;n++){printf(%c-,val[n]);backarray[bbb]=val[n];bbb++;}printf(a);printf(=);/*起点城市*/for(i=0;iTOTLE;i++){if(val[0]==citytwo[i+1]&&city[i+1]=='a'){printf(%d+,distance[i+1]);value[nnn]=distance[i+1];nnn++;}}/*中间的全排列城市*/for(i=0;incount;i++){for(ii=1;ii=TOTLE;ii++){if(val[i]==city[ii]&&val[i+1]==citytwo[ii]){printf(%d+,distance[ii]);value[nnn]=distance[ii];nnn++;continue;}elseif(val[i]==citytwo[ii]&&val[i+1]==city[ii]){printf(%d+,distance[ii]);value[nnn]=distance[ii];nnn++;continue;}}}/*最后返回起点*/for(i=0;iTOTLE;i++){if(val[ncount-1]==citytwo[i+1]&&city[i+1]=='a'){printf(%d=,distance[i+1]);value[nnn]=distance[i+1];nnn++;}}/*存放走一次的路径*/for(i=0;innn;i++){sum=sum+value[i];}printf(%d,sum);/*存入数组*/valueall[all]=sum;all++;printf(\n);}/*蛮力法穷举*/voidfunc(intncount,intn,int*val){if(1==n){print(ncount,val);}else{inti=0;int*pnew=(int*)malloc(sizeof(int)*ncount);for(;in;i++){memcpy(pnew,val,sizeof(int)*ncount);swap(pnew+ncount-n,pnew+ncount-1-i);func(ncount,n-1,pnew);}free(pnew);}}/*自动生成文件*/voidbecome(){inti,j;FILE*fp;fp=fopen(in.dat,w);//srand(unsigned(time(NULL)));for(i=0;iCITYNUM;i++){for(j=i+1;j=CITYNUM;j++){fprintf(fp,%c%c%d\n,i+'a',j+'a',rand()%10+1);}}fclose(fp);}voiddel(){remove(in.dat);}intmain(){printf(请输入城市的数目（大于1的整数）：);scanf(%d,&CITYNUM);CITYNUM=CITYNUM-1;become();floattime_usea=0;floattime_useb=0;structtimevalstarta;structtimevalenda;structtimevalstartb;structtimevalendb;inti=0,ncount=CITYNUM,*val=0;inttemp;intloop;intn=0,d,cnt=0;charsa[10],sb[10];intj;gettimeofday(&starta,NULL);read();val=(int*)malloc(sizeof(int)*ncount);/*a城市是起点，从b城市开始全排列，把所有城市存在val中*/for(i=0;incount;i++){val[i]='b'+i;}func(ncount,ncount,val);/*for(i=0;iall;i++){if(i%10==0){printf(%d,valueall[i]);printf(\n);}else{printf(%d,valueall[i]);}}*//*找到最短路程*/temp=valueall[0];for(i=1;iall;i++){if(tempvalueall[i]){temp=valueall[i];ccc=i;}}printf(Theshorttestwayis:%d\n,temp);printf(a-);for(i=ccc*(CITYNUM-1);iccc*(CITYNUM-1)+(CITYNUM-1);i++){printf(%c-,backarray[i]);}printf(a);printf(\n);gettimeofday(&enda,NULL);time_usea=(enda.tv_sec-starta.tv_sec)*1000+(enda.tv_usec-starta.tv_usec)/1000;//毫秒printf(Ittookyou%f毫秒\n,time_usea);//printf(b=%ld,all=%d,ccc=%d\n,bbb,all,ccc);free(val);FILE*fp=NULL;fp=fopen(OUT.DAT,a+);if(NULL==fp){printf(wrong);return0;}fprintf(fp,蛮力:%d%f\n,n,time_usea);//fprintf(fp,分支:%d%f\n,n,time_useb/1000);fclose(fp);del();printf(如果需要再算一次，请按1\n);printf(如果需要退出，请按2\n);scanf(%d,&loop);switch(loop){case1:returnmain();case2:return;default:return;}return0;}