tsp2l.c

旅行商问题

#include <stdio.h>

int cd[30][30];  /*存储两地之间的代价*/
int tmin=32767; /*存储最小代价*/
int path[30];   /*存储最小代价的路径*/
int cn,sc;      /*cn为城市结点的个数，sc为起点*/

struct city{
  int ec;
  int tv;
};
 /*ec表示城市结点编号，tv到此地的代价*/
struct city city[30]; /*栈，存储走过的结点*/
 /*由文件城市结点的信息*/
void cinf()
{
  int i,j;
  FILE *fp;

  if((fp=fopen("ct.txt","rb"))==NULL)
    exit();
  for(i=0;i<cn-1;i++)
    for(j=i+1;j<=cn-1;j++)
     {
       fscanf(fp,"%d",&cd[i][j]);
       cd[j][i]=cd[i][j];
     }
  fclose(fp);
  printf("The cities'information:\n");
  for(i=0;i<cn;i++)
   {
    for(j=0;j<cn;j++)
       printf("%4d",cd[i][j]);
       printf("\n");
    }
}
 /*搜索最小代价的路径*/
void travel()
{

  int ctv=0;
  int top=-1;
  int s=0,i,c[30];

  printf("Input the number of cities:");
  scanf("%d",&cn);
  printf("Input the beginning city:");

  while(1)
   {
    scanf("%d",&sc);
    if(sc>=0&&sc<cn) break;
    else printf("Input wrong!Please re-enter:");
   }
  cinf();
  c[sc]=1;
  top++;
  city[top].ec=sc;
  city[top].tv=0;
  while(1)
  {
   for(i=s;i<cn;i++)
    if(c[i]==0&&(city[top].tv+cd[city[top].ec][i])<tmin) /*搜索未访问过且当前代价小于已知的最小代价的城市结点，若成功则将此城市结点进栈*/
      {
       top++;
       city[top].ec=i;
       city[top].tv=city[top-1].tv+cd[city[top-1].ec][city[top].ec];
       c[i]=1;
       s=0;
       break;
      }
    if(i==cn)/*若未进栈且搜索未完毕，则出栈*/
      {
       if(top==0)break;
       s=city[top].ec+1;
       c[city[top].ec]=0;
       top--;
      }
    else if(top==cn-1)  /*找到一条路径*/
      {
       ctv=city[top].tv+cd[city[top].ec][sc];
       if(ctv<tmin) /*找到的路径代价更小，则存储最小代价值和路径*/
       {
        tmin=ctv;
        for(i=0;i<cn;i++)
         path[i]=city[i].ec;
       }
     }
  }
}

main()
{ int i;
  travel();
  printf("The best path:");
  for(i=0;i<cn;i++)
   printf("%d-->",path[i]);
  printf("%d",sc);
  printf("\nMinimum value=%d",tmin);
  getch();
}