ert.c

对于组合数学中旅行商问题

#include "stdio.h"
#define   maxn   14  
#define    INF    9999
int   Distance[maxn][maxn]={
	{0,	    27,	 44,	 17,	   11,  27,	    42,	   INF,	    INF,	INF,	20,	 25,	21,	21},
	{27,	0,	 31,     27,	   49,	 INF,	INF,	INF,	INF,	INF,	INF,	INF,	52,	21},
	{44,	31,  0,	     19,	   INF,  27,	32,	    INF,	INF,	INF,	47,	 INF,	INF,	INF},
	{17,	27,  19,     0,	       14,	 INF,	INF,	INF,	INF,	INF,	30,	INF,	INF,	INF},
	{11,	49,	 INF,   14,	       0,	 13,	20,	    INF,	INF,	28,	    15,	 INF,	INF,	INF},
	{27	,   INF, 27,    INF,	   13,	 0,	     9,	    21,  	INF,	26,	    26,	 INF,	INF,	INF},
	{42	,   INF, 32,    INF,    	20,	 9,	    0,	    13,	    INF,	32, 	INF,	INF,	INF,	INF},
	{INF,	INF, INF,	INF,	    INF, 21,	13,	    0,	    19,	    INF,	INF,	INF,	INF,	INF},
	{INF,	INF ,INF,	INF,	    INF, INF,	INF,	19,	    0,	    11, 	20,	INF,	INF,	INF},
	{INF,	INF	,INF,	INF,	    28,	 26,	32,	    INF,	11,  	0,  	10,	20,	INF,	INF},
	{20	,   INF	, 47,	30,	        15,	 26,	INF,	INF,	20,  	10,	    0,	18,	INF,	INF},
	{25	,   INF	,INF,	INF,	    INF, INF,	INF,	INF,	INF,	20,	   18,	0,	23,	INF},
	{21,	52	,INF,	INF,	    INF, INF,	INF,	INF,	INF,	INF,	INF,	23,	0,	27},
	{21	,   21	,INF,	INF,	    INF, INF,    INF,	INF,	INF,	INF,	INF,	INF,	27,	0}
	};


  int   Path[maxn];   
    
  void   quick_sort(int   a[],int   low,int   up)   
  {int   i,j,t;   
    if(low<up)   
  {i=low;   
            j=up;   
    t=a[low];   
    while(i!=j)   
    {while(i<j&&a[j]>t)   j--;   
      if(i<j)   a[i++]=a[j];   
      while(i<j&&a[i]<=t)   i++;   
      if(i<j)   a[j--]=a[i];   
    }   
  a[i]=t;   
  quick_sort(a,   low,   i-1);   
  quick_sort(a,   i+1,   up);   
  }   
  }   

  int   tsp(int   a[],int   n,int   start)   
  { int i,j,k,t,cost,mincost,s,count;   
    cost=0;
	mincost=0; 
    s=1;
    count;
    quick_sort(a,0,n-1);   
    mincost+=Distance[start][a[0]];   
    for(i=0;i<n-1;i++)    { mincost+=Distance[a[i]][a[i+1]];   
    mincost+=Distance[a[i]][start];  }
	
    for(i=0;i<n;i++)   Path[i]=a[i];   
      
    for(i=1;i<=n;i++)   s=s*i;   
    for(count=2;count<=s;count++)   
  {   
    j=n-1;   
    while(a[j-1]>a[j])   j--;   
    k=j;   a[k]=a[j];   
    for(i=j+1;i<n;i++)   
    if(a[k]>a[i]&&a[i]>a[j-1])   
    {k=i;a[k]=a[i];}   
    t=a[k];a[k]=a[j-1];a[j-1]=t;   
    quick_sort(a,j,n-1);   
    cost+=Distance[start][a[0]];   
            for(i=0;i<n-1;i++)     cost+=Distance[a[i]][a[i+1]];   
            cost+=Distance[a[i]][start];   
    if(cost<mincost)   
    {       mincost=cost;   
    for(i=0;i<n;i++)   Path[i]=a[i];   
    }   
  cost=0;   
          }   
    
    return   mincost;   
  }   
    
    
  void   main(void)   
  { 
	int   start,value,i,j,vertex[maxn];  
	int n;
    //printf("\n输入节点个数（小于十个）");   
    //scanf("%d",&n);   
	n=maxn;
    //getchar();   
    for(i=0;i<n;i++)   vertex[i]=i;   
    printf("输入出发节点编号（0～～%d）",n-1);   
    scanf("%d",&start);   
    getchar();   
    for(i=start;i<n-1;i++)   
		vertex[i]=vertex[i+1];  
    
	//printf("输入邻接矩阵\n");   
    //for(i=0;i<n;i++)   
   // for(j=0;j<n;j++)   
//	{
	//	printf("输入第%d个节点到第%d个节点间距离",i,j);   
      //  scanf("%d",&Distance[i][j]);   
      //     }   
    
    value=tsp(vertex,n-1,start);   
    printf("输入的邻接矩阵为:\n");   
    for(i=0;i<n;i++)   
            {for(j=0;j<n;j++)   
          printf("   %d   ",Distance[i][j]);   
      printf("\n");     
            }   
    printf("最短路径为\n%d-->",start);   
    for(i=0;i<n-1;i++)   printf("%d-->",Path[i]);   
    printf("%d\n",start);   
    printf("最短路径值为     %d",value);  
	printf("\n");
  }