旅行商问题 C语言解法

C语言解决旅行商问题（货郎担问题），包括程序文件、源代码、程序测试图。

//程序使用C语言编写，解决旅行商（货郎担）问题，使用穷举法实现。
//特点：1、程序具有通用性，程序开始可以输入地点个数。
//      2、可以显示输出所有的路径及距离。
//      3、若最短路径有多种，可以实现全部输出

#include
#include 
#include 
#define N 100
int a[N][N];
int b[N];
void sort （int d[]int lowint up）          //排序函数（使用快速排序）
{
	int ijt;
	if（low	{
		i=low;
		j=up;
		t=d[low];
		while（i!=j）
		{ 
			while（it） 
				j--;  
			if（i				d[i++]=d[j];
			while（i				i++;
			if（i				d[j--]=d[i];
		}
		d[i]=t;
		sort（d low i-1）;
		sort（d i+1 up）;
	}
}
void suanfa（int d[]int n）                   //算法实现函数
{
	int ijktcsc;
	c=0;
	sc=0;
	long sh;
	s=1;
	for（i=1;i<=n;i++）
		s=s*i;                                //计算所有走法的个数
	printf（“共有%d种走法如下:\n“s）;
	sort（d0n-1）;
	sc+=a[0][d[0]];
	for（i=0;i		sc+=a[d[i]][d[i+1]];
	sc+=a[d[i]][0];                         //按1、2、3、4……计算的路程
	for（i=0;i		b[i]=d[i];                          //记忆地点顺序
    {
		printf（“路径1为  %d-->“1）;
     	for（i=0;i			printf（“%d-->“d[i]+1）;   //输出按1、2、3、4……结果
	    printf（“%d\t“1）;
    	printf（“路径1的值为\t%d\n“sc）;
	}                     
	for（h=2;h<=s;h++）                        //循环求各种路线的路程
	{
		j=n-1;
		while（d[j-1]>d[j]） j--;
		k=j;
		d[k]=d[j];
		for（i=j+1;i			if（d[k]>d[i]&&d[i]>d[j-1]）
			{
				k=i;
				d[k]=d[i];
			}
			t=d[k];
			d[k]=d[j-1];                     //变换路线顺序
			d[j-1]=t;
			sort（djn-1）;
			c+=a[0][d[0]];
			for（i=0;i				c+=a[d[i]][d[i+1]];
			c+=a[d[i]][0];                   //求对应路线的路程
			{
	        	printf（“路径%d为  %d-->“h1）;
             	for（i=0;i					printf（“%d-->“d[i]+1）;   //输出按该路线结果
         	    printf（“%d\t“1）;
            	printf（“路径%d的值为\t%d\n“hc）;
			}
			if（c			{  
				sc=c;
				for（i=0;i					b[i]=d[i];
			}
			c=0;
	}
	printf（“\n“）;                             
    printf（“最短距离为\t  %d\n“sc）;          //输出最短距离
    printf（“所有最短路径为:\n“）;              //此行以下用于最短路径有多条时的输出
    sort（d0n-1）;
	c+=a[0][d[0]];
	for（i=0;i		c+=a[d[i]][d[i+1]];
	c+=a[d[i]][0];                         
	for（i=0;i		b[i]=d[i];                         
	if（sc-c==0）
    {
		printf（“路径 \t%d-->“1）;            //比较是否为最短距离，若是输出路径
     	for（i=0;i			printf（“%d-->“d[i]+1）;  
	    printf（“%d\t\n“1）;
	}
	c=0;
	for（h=2;h<=s;h++）                       
	{
		j=n-1;
		while（d[j-1]>d[j]） j--;
		k=j;
		d[k]=d[j];
		for（i=j+1;i			if（d[k]>d[i]&&d[i]>d[j-1]）
			{
				k=i;
				d[k]=d[i];
			}
			t=d[k];
			d[k]=d[j-1];                     
			d[j-1]=t;
			sort（djn-1）;
			c+=a[0][d[0]];
			for（i=0;i				c+=a[d[i]][d[i+1]];
			c+=a[d[i]][0]; 
			if（sc-c==0）                                 //比较是否为最短距离，若是输出路径
			{
	        	printf（“路径\t%d-->“1）;
             	for（i=0;i“d[i]+1）;   
         	    printf（“%d

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       4406  2011-05-23 20:31  旅行商.cpp

     文件     266282  2011-05-23 20:08  旅行商问题.exe

     文件      57809  2011-05-23 20:42  测试\1.jpg

     文件      56222  2011-05-23 20:42  测试\2.jpg

     文件      55538  2011-05-23 20:40  测试\3.jpg

     文件      69884  2011-05-23 20:40  测试\4.jpg

     文件         56  2011-05-23 20:45  测试\说明.txt

     文件       4406  2011-05-23 20:30  源代码.txt

     目录          0  2011-05-23 20:43  测试

----------- ---------  ---------- -----  ----

               514603                    9