tour.cpp

旅行商问题的实现

/****************************************/
/*程序:		旅行商(回溯)*/
/*作者:		Eric Roy	*/
/*日期:		2007-4-17	*/
/*调试:		VC6			*/
/****************************************/

#include <iostream>
using namespace std;

template<class Type>
class Traveling
{
	friend Type TSP(int**, int[], int, Type);
	private:
		void Backtrack(int i);
		int n,			//图G的顶点数
			*x,			//当前解
			*bestx;		//当前最优解
		Type **a,		//图G的领接矩阵
			cc,			//当前费用
			bestc,		//当前最优值
			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++)		//是否可进入x[j]子树
			if( a[x[i-1]][x[j]] != NoEdge && ( cc + a[x[i-1]][x[i]] < bestc || bestc == NoEdge ) )	//搜索子树
			{
				int temp=x[i];
				x[i]=x[j];
				x[j]=temp;
				cc+=a[x[i-1]][x[i]];
				Backtrack(i+1);
				cc-=a[x[i-1]][x[i]];
				temp=x[i];
				x[i]=x[j];
				x[j]=temp;
			}
	}
}

template<class Type>
Type TSP(Type **a, int v[], int n, Type NoEdge)	//返回旅行商回路的最小费用
{
	Traveling<Type> Y;		//初始化Y
	Y.x=new int[n+1];		//置X为单位排列
	for(int i=1;i<=n;i++)
		Y.x[i]=i;
	Y.a=a;
	Y.n=n;
	Y.bestc=NoEdge;
	Y.bestx=v;
	Y.cc=0;
	Y.NoEdge=NoEdge;
	Y.Backtrack(2);		//搜索x[2:n]的全排列
	delete []Y.x;
	return Y.bestc;
}

void main(int)
{
	const int n=4;
	int i,j;
	int tour[n+1][n+1]={{0,0,0,0,0},
						{0,0,30,6,4},
						{0,30,0,5,10},
						{0,6,5,0,20},
						{0,4,10,20,0}};
	cout<<"代价矩阵为: "<<endl;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			cout<<"\t"<<tour[i][j];
		}
		cout<<endl;
	}

	int **a;
	a=new int*[n+1];
	for(i=1;i<=n;i++)
	{
		a[i]=new int[n+1];
		for(j=1;j<=n;j++)
		{
			a[i][j]=tour[i][j];
		}
	}


	int v[n+1];		//回路数组
	int NoEgde=0;	//无边标识
	int result=TSP(a,v,n,NoEgde);	//最小费用
	cout<<endl<<"旅行顺序为: "<<endl;
	for(i=1;i<=n;i++)
	{
		cout<<"  "<<v[i];
	}
	cout<<"  "<<v[1];	//回到起点
	cout<<endl<<"最小费用为: "<<result<<endl;

	delete []a;
	system("pause");
}