#include?“stdio.h“
#include?“math.h“
#include?“stdlib.h“


#define?N?10
//#define?M?1*2*3*4
#define?num?100
int?noEdge=-1;??????//無邊標記

struct?object
{
	int?n;???//城市編號
	int?x;???//x坐標
	int?y;???//y坐標
}wup;

struct?object?wp[N+1];??//共N個城市
??
double?A[num][num];//存放各個城市之間的代價
int?count;//記錄走過的節點數
int?bestA[num];//當前最優解
int?x[num];//當前解

double?currentP;//當前路徑值
double?bestPath;//當前最短路徑值

int?distant（int?x1int?y1int?x2int?y2）
{
	double?x=0;
	x=sqrt（pow（abs（x1-x2）2）+pow（abs（y1-y2）2））;

?return?（int）x;

}

void?Backtrack（int?i）
{
	count++;
	if（i==N）
	{
		if（A[x[N-1]][x[N]]!=noEdge?&&?A[x[N]][x[1]]!=noEdge）
		{
			if（?bestPath?==?noEdge?||bestPath?>?currentP+A[x[N-1]][x[N]]+A[x[N]][x[1]]）
			{
			
				for（int?j=1;j<=N;j++）
				{
					bestA[j]=x[j];
				}
				bestPath=currentP+A[x[N-1]][x[N]]+A[x[N]][x[1]];
			}

		}
	}
	else
	{
		int?j;
		for（j=i;j<=N;j++）
		{
			if（A[x[i-1]][x[j]]?!=noEdge）
			{
				if（bestPath?==noEdge?||?bestPath?>?currentP+A[x[i-1]][x[j]]+A[x[j]][x[1]]?）
				{
					int?temp;
					currentP?+=A[x[i-1]][x[j]];
					temp=x[i];
					x[i]=x[j];
					x[j]=temp;
					Backtrack（i+1）;
					temp=x[i];
					x[i]=x[j];
					x[j]=temp;
					currentP?-=A[x[i-1]][x[j]];
				}
			}
		}
????}	
}

double?tsp（）
{
	//初始化
	bestPath=noEdge;
	currentP=0.0;
	int?i;
	for（i=1;i<=N;i++）
	{
		x[i]=i;
	}
	Backtrack（2）;
	return?bestPath;
}

void?output（）
{
	int?i;
	for（i=1;i<=N;i++）
	{
		printf（“%4d“bestA[i]）;
	}
	printf（“??1“）;
	printf（“\n“）;
}

int?main（）?
{????
	int?ij;
	//獲取數據
????FILE?*fp;????????/*文件指針*/

	if（（fp=fopen（“data.txt““r+“））==NULL）?
	{
		printf（“cannot?open?the?file!“）;?
		exit（0）;?
	}?
	//讀取文件
	
	for（i=1;i<=N;i++）
	{
		fscanf（fp“%d%d%d“&wp[i].n&wp[i].x&wp[i].y）;
	}

	printf（“??城市編號??x坐標??y坐標\n“）;
	for（i=1;i<=N;i++）
	{	
		printf（“?????%d??????%d???%d\n“wp[i].nwp[i].xwp[i].y）;
	}
	printf（“--------------------------------------\n\n“）;

	for（?i=1;i<=N;i++）
	{?
	??for（j=1;j<=N;j++）
	??{?
		??if（i==j）
		??{
			A[i][j]=-1;
		??}
		??else
		??{
			??A[i][j]=distant（wp[i].xwp[i].ywp[j].xwp[j].y）;
		??}
	??}
	}
	for（i=1;i<=N;i++）
	{
		printf（“第%d行:??“i）;
		for（j=1;j<=N;j++）
		{?
			printf（“%2.0f??“A[i][j]）;
		}
		printf（“\n“）;
	}

	printf（“\n“）;
	printf（“--------------------------------------\n“）;
?????printf（“走%d個城市最短路徑為：%lf\n“Ntsp（））;
?????printf（“走法為:“）;??
	?output（）;
	?printf（“循環次數：%d\n“count）;
}??

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

?????文件?????221877??2018-07-01?18:59??15計2-2015551239-王維-用回溯法解TSP問題\15計2-2015551239-王維-用回溯法解TSP問題.docx

?????文件???????2136??2015-05-07?14:17??15計2-2015551239-王維-用回溯法解TSP問題\data.txt

?????文件???????2620??2018-07-01?15:47??15計2-2015551239-王維-用回溯法解TSP問題\tsp.cpp

?????文件?????163437??2018-07-01?15:37??15計2-2015551239-王維-用回溯法解TSP問題\tsp.exe

?????目錄??????????0??2018-07-01?18:59??15計2-2015551239-王維-用回溯法解TSP問題

-----------?---------??----------?-----??----

???????????????390070????????????????????5