回溯法解旅行售货员问题.cpp

算法分析中

/*
旅行售货员问题
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;
}