/*
旅行售貨員問題
1.算法描述
旅行售貨員問題的解空間是一棵排列樹。對于排列樹的回溯搜索與生成1，2，。。。，n
的所有排列的遞歸算法Perm類似。設開始時x=[1,2,...n]，則相應的排列樹由x[1:n]的所有
排列構成
如果每個活動接點有m種選擇的一個排列就叫作完全m叉樹
如果是一個全排列，就叫做排列樹
在遞歸函數Backtrack中，當i==n，當前擴展結點是排列樹的葉結點的父結點。此時
算法檢測圖G是否存在一條從頂點x[n-1]到頂點x[n]的邊和一條從頂點x[n]到頂點1的
邊。如果這兩條邊都存在，則找到一條旅行售貨員回路。此時算法還需要判斷這條回路
的費用是否優于已經找到的當前最優回路的費用bestc。如果是，則必須更新當前最優值bestc
和當前最優解bestx。
當i<n時，當前擴展結點位于排列樹的第i-1層。圖G中存在從頂點x[i-1]到頂點x[i]的邊時，
x[1:i]構成圖G的一條路徑，且當x[1:i]的費用小于當前最優值時算法進入排列樹的第i層
，否則將剪去相應的子樹。算法中用變量cc記錄當前路徑x[1:i]的費用。
*/
template<class Type>
class Traveling
{
	friend Type TSP(int **,int [],int,Type);
	private:
		void Backtrack(int i);
		int n;
		//圖G的頂點數
		int *x;
		//當前解
		int *bestx;
		//當前最優解
		Type **a;
		//圖G的鄰接矩陣
		int cc;
		//當前費用
		int bestc;
		//當前最優值
		int NoEdge;
		//無邊標記
};

template<class Type>
void Traveling<Type>::Backtrack(int i)
{
	if ( i == n )
	{
		if ( a[x[n-1]][x[n]] != NoEdge
			&& a[x[n]][1] != NoEdge
			&& ( cc + a[x[n-1]][x[n]] + a[x[n]][1] < bestc
			|| bestc == NoEdge ) )
		{
			for( int j = 1; j <= n; ++j )
			{
				bestx[j] = x[j];
			}
			bestc = cc + a[x[n-1]][x[n]] + a[x[n]][1];
		}
	}
	else
	{
		for( int j = i; j <= n; ++j )
		{
			if ( a[x[i-1]][x[j]] != NoEdge
				&& (cc + a[x[i-1]][x[i]] < bestc 
				|| bestc == NoEdge ) )
			{
				//搜索子樹
				int t;
				t = x[i];
				x[i] = x[j];
				x[j] = t;
				cc += a[x[i-1]][x[i]];
				Backtrack(i+1);
				cc -= a[x[i-1]][x[i]];
				t = x[i];
				x[i] = x[j];
				x[j] = t;
				//回到上層的時候恢復原來的值

			}
		}
	}
}

template<class Type>
Type TSP(Type **a,int v[],int n,Type NoEdge)
{
	Traveling<Type> Y;
	//初始化Y
	Y.x = new int[n+1];
	for( int i = 1; i <= n; ++i )
	{
		Y.x[i] = i;
	}
	Y.a = a;
	Y.n = n;
	Y.bestc = NoEdge;
	Y.bestx = v;
	Y.NoEdge = NoEdge;
	//
	Y.Backtrack(2);
	//搜索從2開始的全排列
	delete[] Y.x;
	return Y.bestc;
}
/*
不考慮bestx所需要的計算時間，則Backtrack需要O((n-1)!)計算時間。由于
算法Backtrack在最壞情況下可能需要更新O((n-1)!)次當前最優解bestx,每次更新
bestx需O(n)計算時間，從而整個算法的計算時間復雜性為O(n!)
*/
int main()
{
	return 0;
}