旅行推銷員問題之C語言算法[原創] 
旅行推銷員問題：一位旅行推銷員想要訪問n個城市中每個城市恰好一次，并且返回到出發點。應如何走才能使總距離最短？其實就是求帶權完全無向圖中訪問每個頂點恰好一次并且返回出發點的總權數最小的回路，即總權數最小的哈密頓回路。

思路：把n個城市做全排列，并求出每種排列對應的總距離，然后選擇最短的一個。

推論：把上面求出的最短哈密頓回路看作一個圓，求出最短哈密頓回路以后，從回路上任一點開始出發而訪問每個頂點一次，總距離是相等的。因為總距離與圓周相等。

代碼（效率有待于提高，因為多判斷了一半的回路，即一條路反方向和正方向各判斷了一次）：

/*
   程序功能：求解旅行推銷員問題
   作者：BugEyes
   主頁：http://bugeyes.blog.edu.cn
*/

int flag=0;/*用來標記回路是否檢查完畢*/

int search(int distance[5][5],int start,int result[5]);
void next(int array[],int n);
void sort(int array[],int start,int end);
int dis_compute(int distance[5][5],int result[5]);
void chuli(int t_result[],int result[],int start,int n);


void main()
{
   int i,j,start;/*start表示出發點城市編號*/
   int distance[5][5]={{0,50,30,7,60},/*模擬城市之間的距離*/
                                {50,0,40,76,89},
                                {30,40,0,10,70},
                                {70,76,100,0,80},
                                {90,89,70,80,0}};
   int result[5]={0};/*存放最短哈密頓回路*/
   int dis_result=0;/*存放最短總距離*/
   printf("\nThe distance of cities are as follows:\n");
   for(i=0;i<5;i++)
   {
      for(j=0;j<=i;j++)
             printf("%4d",distance[i][j]);
      printf("\n\n");
   }
   printf("Please input the city number to start.Input -1 to exit.\n");
   scanf("%d",&start);
   while(start<-1||start>4)
   {
      printf("Sorry,you are wrong.\nPlease input the city number to start.Input -1 to exit.\n");
      scanf("%d",&start);
   }
   if(start==-1)/*-1表示結束程序*/
   {
      printf("\nBye.Good luck!\n");
      return;
   }
   printf("\nOK.Let's go!!!\n");
   dis_result=search(distance,start,result);/*計算最短哈密頓回路，并求總距離*/
   printf("\nThe best route is:\n");
   for(i=0;i<5;i++)
      printf("%4d->",result[i]);
   printf("%4d\n",result[0]);
   printf("And the whole distance is:%d\n",dis_result);
}

int search(int distance[5][5],int start,int result[5])
{
   int i,j;
   int t_distance,r_distance;
   int t_result[5]={0,1,2,3,4};
   int r_result[5];
   printf("\nI am in search function...........");
   t_distance=r_distance=dis_compute(distance,t_result);
   while(flag==0)
   {
      next(t_result,5);
      chuli(t_result,r_result,start,5);
      if((t_distance=dis_compute(distance,r_result))<r_distance)
      {/*若當前回路總距離在檢查過的回路中最小*/
             r_distance=t_distance;
             chuli(t_result,result,start,5);
      }
   }
   printf("\nI am leaving search function...............");
   return r_distance;
}

void next(int array[],int n)
{ /*計算下一個可能的回路，其實就是求排列*/
   int i,j,temp;
   printf("\nI am in next function..........................");
   flag=0;
   for(i=n-2;i>=0;i--)
      if(array[i]<array[i+1])
          break;
   for(j=n-1;j>i;j--)
      if(array[j]>array[i])
           break;
   if(j==i)
   {/*已是最后一條回路*/
      flag=1;
      return;
   }
   temp=array[i];
   array[i]=array[j];
   array[j]=temp;
   sort(array,i+1,n);
   printf("\nI am leaving next function..........................");
}

void sort(int array[],int start,int end)
{
   int i,j;
   printf("\nI am in sort function...............................");
   for(i=start;i<end-start;i++)
      for(j=start;j<end-1;j++)
  if(array[j]>array[j+1])
  {
     int t=array[j];
     array[j]=array[j+1];
     array[j+1]=t;
  }
   printf("\nI am leaving sort function...........................");
}

int dis_compute(int distance[5][5],int result[5])
{/*計算當前回路對應的總距離*/
    int r_distance=0;
    int i;
    printf("\nI am in dis_compute function.........................");
    for(i=0;i<5;i++)
        r_distance+=distance[result[i]][result[(i+1)%5]];
    printf("\nI am leaving dis_compute function...................");
    return r_distance;
}

void chuli(int t_result[],int result[],int start,int n)
{/*對選擇的回路重新排列，按出發點---->路徑---->出發點的順序排列*/
   int i,pos;
   printf("\nI am in chuli function..............................");
   for(i=0;i<n;i++)
      if(t_result[i]==start)
             break;
   pos=i;
   for(i=0;i<n;i++)
      result[i]=t_result[(pos+i)%n];
   printf("\nI am leaving chuli function.......................");
}

 

時間倉促，可能有考慮不周之處，請大家不吝賜教！