visit.c

用贪心算法做的全国31个城市之间的旅行商问题源代码

#include<stdio.h>
#define Max 31
#define True 1
#define False 0
//保存最小路径
void path_copy(int *best_circle,int *cp)
{
	int i;
	for(i=0;i<Max;i++)
  *(best_circle+i)=*(cp+i);
}


void main()
{ 

int w[Max][Max];
int min_cost,cost;
int start,i,j,k,n,p,tmp;
int cp[Max];int best_circle[Max];
int arrived[Max];
char city[Max][4];
FILE *fp;
min_cost=1000000;
   //读入数据

	if((fp=fopen("data.txt","r"))==NULL)
	{printf("cannot open infile\n");
	return;}
	for(i=0;i<Max;i++)
         for(j=0;j<Max;j++)
		 { fscanf(fp,"%d ",&w[i][j]);
               if(w[i][j]==0)w[i][j]=10000;
		 }
  fclose(fp);

   //读入城市

	if((fp=fopen("city.txt","r"))==NULL)
	{printf("cannot open infile\n");
	return;}
	for(i=0;i<Max;i++)
      
		 { fscanf(fp,"%s ",&city[i]);
         printf("%s ",city[i]);
		 }
   
   fclose(fp);

		 //计算最小路径
		 n=Max;
		 for(i=0;i<n;i++)arrived[i]=False;
    for(start=0;start<n;start++){

		cost=0;arrived[start]=True;cp[0]=start;

	for(i=0;i<n;i++)if(i!=start)arrived[i]=False;
    p=start;
	for(i=1;i<n;i++){
		for(k=0;(arrived[k]);k++);
		tmp=w[p][k];
		for(j=k+1;j<n;j++)
			if(!(arrived[j])&&(tmp>w[p][j])){k=j;tmp=w[p][j];}
			cp[i]=k;arrived[k]=True;p=k;
			cost=cost+tmp;
			if(cost>min_cost)break;

	}
	cost=cost+w[p][start];
	if(min_cost>cost){
	min_cost=cost;
	path_copy(best_circle,cp);
	}
}
//打印结果
printf("\n最小路径长度为：");
printf("%ld\n",min_cost);
printf("途经城市如下：\n");
for(i=0;i<n;i++)
{
for(j=0;j<4;j++)
printf("%c",city[ best_circle[i]][j]);
printf(" ->");
}
for(j=0;j<4;j++)
printf("%c",city[ best_circle[0]][j]);
printf("\n\n很明显答案不唯一\n");
printf("\n");
getch();
}