#include "stdio.h"
#define n 10
typedef int DataType;
DataType	bestc;
DataType	*bestx,a[n][n],x[n];
DataType	cc;
void Swap(DataType *a,DataType *b)
{
		DataType *t=a;
		*a=*b;
		*b=*t;
}
void tSP(int i)
{// 旅行商問題的回溯算法
	int j;
	if (i == n) {// 位于一個葉子的父節點
		// 通過增加兩條邊來完成旅行
		if (a[x[n-1]][x[n]]!=0&&a[x[n]][1]!=0&&
			(cc+a[x[n-1]][x[n]]+a[x[n]][1]<bestc||bestc ==0)) 
		{// 找到更優的旅行路徑
			for(j = 1; j <= n; j++)
				bestx[j] = x[j];
			bestc=cc+a[x[n-1]][x[n]] + a[x[n]][1];}
		}
		else {// 嘗試子樹
			for (j = i; j <= n; j++)
				//能移動到子樹x [ j ]嗎?
				if (a[x[i-1]][x[j]] !=0&&
					(cc+a[x[i-1]][x[i]]<bestc||bestc == 0)) 
				{//能搜索該子樹
					Swap(&x[i], &x[j]);
					cc += a[x[i-1]][x[i]];
					tSP(i+1);
					cc -= a[x[i-1]][x[i]];
					Swap(&x[i], &x[j]);
				}
		}
}
DataType TSP(int v[])
{// 用回溯算法解決旅行商問題
	// 返回最優旅游路徑的耗費，最優路徑存入v [ 1 : n ]
	//初始化
	int x[n+1],i;
	// x 是排列
	for (i = 1; i <= n; i++)
		x[i] = i;
	bestc=0;
	bestx=v; // 使用數組v來存儲最優路徑
	cc = 0;
	// 搜索x [ 2 : n ]的各種排列
	tSP(2);
	return bestc;
}
void main()
{
	int v[n];
	//初始化v[n],*bestx,a[n][n],x[n]
	TSP(v);
}