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

《分支限界法求解旅行商问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、先看下运行过程最后运算时间输出到外部文件，精确到毫秒/*此城市是分支限界法求解旅行商问题，*/#include#include#include#include#include#include#defineMAXSIZE99999//#defineCITYNUM5/*4个城市的话，其实全排列的只有3个，另外一个是起点固定的*///#defineTOTLE15/*4个城市对应的道路一共有6条*/#defineMAX32intCITYNUM=0;int

2、TOTLE=0;charcity[MAXSIZE]={0};/*和下面这个数组组成两个城市之间的道路*/charcitytwo[MAXSIZE]={0};intdistance[MAXSIZE]={0};/*存放城市间距离*/intvalueall[MAXSIZE]={0};/*最后放每次运算的路径值*/intall=0;/*对应上面的*/charbackarray[MAXSIZE]={0};longintbbb=0;intccc=0;constintINF=1000000000;intmap[MAX][MAX]={0};intmin[MAX][2];struc

3、tEDGE{intcost[MAX][2];/*距离*/intsta;intlb,len;charseq[MAX];}q[1000000];/*求下界*/intcalc(intcost[MAX][2],intn){intsum=0,i;for(i=0;i

4、lse{sum+=min[i][0]+min[i][1];/*最小里面的一个，那么就是最小两个相加*/}}if(sum&1)sum=sum/2+1;elsesum/=2;returnsum;}/*挑选*/voidBFS(ints,intn){intfront=-1,rear=0;inti,step=0;q[0].sta=1;q[0].len=1;q[0].seq[0]='a';q[0].seq[1]=0;for(i=0;i

5、ear-front;step++;intmin=INF;for(i=front+1;i<=rear;i++){if(q[i].lb

6、i==2&&(sta&2)==0){printf("%s",tseq);printf(":error,Ccan'tbeforeb");continue;}if((1<

7、(q[rear].cost[i][0]==INF){q[rear].cost[i][0]=map[from][i];}else{q[rear].cost[i][1]=map[from][i];}if(q[rear].cost[from][0]==INF){q[rear].cost[from][0]=map[from][i];}else{q[rear].cost[from][1]=map[from][i];}q[rear].lb=calc(q[rear].cost,n);printf("%s",tseq);printf(":lb=%d",q[rear].lb)

8、;}}}//printf