lab_2(vc).c

某售货员要到若干城市去推销商品

#include<stdio.h>
#include<math.h>
#include<time.h>
//#include<graphics.h>

int d[20][524288];/* 保存最短距离 */
int path[20][524288];/* 保存路径 */
int c[20];  /*保存最优路线每边的距离，用于输出界面*/
int num=0;    //输出界面点计数


int Juge(int j,int i)
{/* 判断二进制表示的子集是否含i结点，有返回1，否则返回0 */
/*   printf("___%d___%d__%d__%d\n",j,i,(j>>(i-1)),(j>>(i-1))&1); */
    if(j&(1<<(i-1)))return 1;
    else return 0;
}



long int Out_k(long int j,int k)
{/* 计算V[i]集合中除了k结点后 */
    return j&(~(1<<(k-1)));
}


void TSP(long int n,int way[][20])
{/* TSP动态规划主算法 */
    long int i,j,k,flag=1,temp;
    temp=(long int)(pow(2,(double)(n-1))-1);//求点集最大值2^(n-1)-1
    /* printf("--%ld",t); */

    for(i=1;i<n;i++)/* 初始化第0列 */
        d[i][0]=way[i][0];
    for(j=1;j<temp;j++)
        for(i=1;i<n;i++)
            if(!Juge(j,i))
            {//判断点集V[j]是否包含i结点，若无则求d[i][j]   
                for(k=1;k<n;k++)
                    if(Juge(j,k))
                    {//求出V[j]点集包含的每个顶点
                        if(flag==1)
                        {//flag为1，则d[i][j]第一次算，直接保存
                            d[i][j]=way[i][k]+d[k][Out_k(j,k)];
                            flag=0;
                            path[i][j]=k;/* 保存最短路线点 */
                        }
                        else if(d[i][j]>way[i][k]+d[k][Out_k(j,k)])
                        {    //否则判断新的路线为更小时，换值
                            d[i][j]=way[i][k]+d[k][Out_k(j,k)];
                            path[i][j]=k;/* 保存最短路线点 */
                        }
                
                    }   
                    flag=1; 
            }
    
    flag=1;
    for(k=1;k<n;k++)
        if(Juge(temp,k))    
            if((flag==0)&&(d[0][temp]>way[0][k]+d[k][Out_k(temp,k)]))
            {
                d[0][temp]=way[0][k]+d[k][Out_k(temp,k)];
                path[0][temp]=k;/* 保存最短路线点 */
            }
             else if (flag==1)
            {
                d[0][temp]=way[0][k]+d[k][Out_k(temp,k)];
                flag=0;
                path[0][temp]=k;/* 保存最短路线点 */
            /*  printf("-------%d--%d---%d---%d\n",i,mm,j,d[0][temp]); */
            }
}


void print(int n,int way[][20])
{/* 输出每结点距离 */
    int i,j=0;
    printf("%d\n",n);
    for(i=0;i<n;i++)
        {
            for(j=0;j<n;j++)
                printf("%3d ",way[i][j]);
            printf("\n");
         }
}



void print_path(int j,int n,int way[][20])
{/* 输出最短路线 */
    int i,k,l;
    i=l=0;
    printf("\nThe shortest path of TSP%d.txt is:\n",n);
    printf("1->");

    for(k=1;k<n;k++)
    {//从后开始寻找结点经过的顺序 
        printf("%d->",path[i][j]+1);
        i=path[i][j];
        c[num]=way[l][i];//保存走过的距离
        j=Out_k(j,i);//除去结点i后的点集，为寻找下个结点
        num++;
        l=i;

    }
    c[num]=way[i][0];
    printf("1\n");
}

/*
void show(int nn)
{//输出图形界面，采用随机函数输出结点圆心坐标位置

   int i=1,m,n,m0,n0,t0,t1;
   char s[30]; //输出结点号
   char ss[30];//输出结点间的距离
   int gdriver, gmode;
   num=0;
   detectgraph(&gdriver,&gmode);
   initgraph(&gdriver, &gmode, "");
   setbkcolor(WHITE);
   cleardevice();
   setfillstyle(1,i);
   setcolor(i);
   
   t0=m0=rand()%20*20;//随机产生圆心坐标.
   t1=n0=rand()%20*20;//t0,t1保存第一个结点位置，用于最后返回
   
   sprintf(s,"%d",i);//把数字转为字符串
   outtextxy(m0,n0,s) ;//在坐标(m0,n0)输出 字符串 s
   circle(m0,n0,15);//圆心(m0,n0)半径15
   getch();
   for(i=2;i<=nn;i++)
   {
       setfillstyle(1,i);
       setcolor(i);
       m=rand()%20*20+i*10;n=rand()%20*20+i*10;
       circle(m,n,15);

       settextstyle(4,0,1);
       sprintf(s,"%d",i);
       sprintf(ss,"%d",c[num]);
       
       outtextxy(m,n,s) ;
       outtextxy((m0+m)/2,(n0+n)/2,ss);
       line(m0,n0,m,n);//在(m0,n0)和(m,n)间划条直线
       num++;
       m0=m;n0=n;
       getch();
   }
    sprintf(ss,"%d",c[num]);
    outtextxy((m0+t0)/2,(n0+t1)/2,ss);
    line(m0,n0,t0,t1);
    getch();
    closegraph();
}

*/
void main()
{/* 主函数 */
    FILE *fp;
    char filename[10];
    long int i,j,n;
    int way[20][20];/* 保存每结点间距离 */
    
    clock_t start,end;
    start = clock();/*开始时时间点*/
    printf("Please input the filename for test : ");
    scanf("%s",filename);/* read the file */
    if((fp = fopen(filename,"rw"))==NULL)
    {
        printf("cannot open file\n");
        return;
    }   
    fscanf(fp,"%d",&n);
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            fscanf(fp,"%d",&way[i][j]);

    print(n,way);
    TSP(n,way);
    
    i=(int)(pow(2,(double)(n-1))-1);
    print_path(i,n,way);
    end = clock();//结束时间点
    printf("The shortest distance of TSP%d.txt is:",n);
    printf("%d\n",d[0][i]);
    printf("The running time is %lfs\n",(double)(end - start)/CLK_TCK);
    getch();
  //  show(n);
    fclose(fp);
}