//程序使用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