分支限界法求解旅行商问题.doc

先看下运行过程最后运算时间输出到外部文件，精确到毫秒/*此城市是分支限界法求解旅行商问题，*/#include#include#include#include #include #include #define MAXSIZE 99999/#define CITYNUM 5/*4个城市的话，其实全排列的只有3个，另外一个是起点 固定的*/#define TOTLE 15/*4个城市对应的道路一共有6条*/#define MAX 32int CITYNUM=0;int TOTLE=0;char cityMAXSIZE=0;/*和下面这个数组 组成 两个城市之间的道路*/char citytwoMAXSIZE=0;int distanceMAXSIZE=0;/*存放城市间距离*/int valueallMAXSIZE=0;/*最后放每次 运算 的 路径值*/int all=0;/*对应上面的*/char backarrayMAXSIZE=0;long int bbb=0;int ccc=0;const int INF=1000000000;int mapMAXMAX=0;int minMAX2;struct EDGEint costMAX2;/*距离*/int sta;int lb,len;char seqMAX;q1000000;/*求下界*/int calc(int costMAX2,int n)int sum=0,i;for(i=0;in;i+)if(costi1!=INF)sum+=costi0+costi1;else if(costi0!=INF)sum+=costi0;if(costi0=mini0)sum+=mini1;else sum+=mini0;elsesum+=mini0+mini1;/*最小里面的一个，那么就是最小两个相加*/if(sum&1)sum=sum/2+1;else sum/=2;return sum;/*挑选*/void BFS(int s,int n)int front=-1,rear=0;int i,step=0;q0.sta=1;q0.len=1;q0.seq0=a;q0.seq1=0;for(i=0;in;i+)q0.costi0=q0.costi1=INF;while(front!=rear)int size=rear-front;step+;int min=INF;for(i=front+1;i=rear;i+)if(qi.lbmin)min=qi.lb;while(size-)front+;int sta=qfront.sta;if(qfront.lb!=min)continue;for(i=0;in;i+)int tsta;char tseqMAX;/*存城市*/int tlen=qfront.len+1;strcpy(tseq,qfront.seq);tseqtlen-1=i+a;tseqtlen=0;if(i=2&(sta&2)=0)printf(%s,tseq);printf(: error,C cant before bn);continue;if(1i)&sta)continue;tsta=(1i)+sta;rear+;qrear.sta=tsta;strcpy(qrear.seq,tseq);qrear.len=tlen;memcpy(qrear.cost,qfront.cost,sizeof(qfront.cost);int from=qfront.seqqfront.len-1-a;if(qrear.costi0=INF)qrear.costi0=mapfromi;elseqrear.costi1=mapfromi;if(qrear.costfrom0=INF)qrear.costfrom0=mapfromi;elseqrear.costfrom1=mapfromi;qrear.lb=calc(qrear.cost,n);printf(%s,tseq);printf(: lb=%dn,qrear.lb);/printf(rear=%dn,rear);/*自动生成文件*/void become()int i,j;FILE *fp;fp = fopen(in.dat,w);/srand(unsigned(time(NULL);for(i=0;iCITYNUM;i+)for(j=i+1;jn)n=sa0+1;if(sb0+1n)n=sb0+1;mapsa0sb0=mapsb0sa0=d;cnt+;fclose(fpp);/*printf(cnt=%dn,cnt);printf(n=%dn,n);*/for(i=0;in;i+)mapii=mini0=mini1=INF;for(i=0;in;i+)/*把每个点最小的两个找出来*/for(j=0;jn;j+)if(mapij=mini0)mini1=mini0;mini0=mapij;else if(mapijmini1)mini1=mapij;/*分支限界*/for(i=0;i1000;i+)BFS(0,n);gettimeofday(&endb,NULL);time_useb=(endb.tv_sec-startb.tv_sec)*1000+(endb.tv_usec-startb.tv_usec)/1000;/毫秒printf(It took you %f 毫秒n,time_useb/1000);/printf(%d,n);/*最好数组读出*/FILE *fp = NULL;fp = fopen(OUT.DAT, a+);if(NULL = fp) printf(wrong);return 0; /fprintf(fp, 蛮力: %d %fn, n,time_usea);fprintf(fp, 分支: %d %fn, n,time_useb/1000);fclose(fp);del()