tsp.h

用回溯法实现最大团问题

template<class T> class Traveling
{
	public:
		Traveling(int,T**,T,T);
		~Traveling();
		void Backtrack(int i);
		void print();
	private:
		void swap(T&a,T&b);
		int N,
			*X,
			*BestX;
		T**A,
			CC,
			BestC,
			NoEdge;
};
template<class T>
Traveling<T>::Traveling(int n,T**a,T c,T e)
{
	N=n;
	A=a;
	NoEdge=e;
	X=new int[N+1];
	BestX=new int[N+1];
	CC=c;
	BestC=e;
	for(int i=0;i<=N;i++)
		X[i]=i;
}
template<class T>
Traveling<T>::~Traveling()
{
	delete[]X;
	delete[]BestX;
}
template<class T>
void Traveling<T>::swap(T&a,T&b)
{
	T temp=a;
	a=b;
	b=temp;
}
template<class T>
void Traveling<T>::print()
{
	if(BestC!=NoEdge)
	{
		cout<<"最优巡回路线是："<<endl;
		cout<<BestX[1]<<endl;
		for(int i=2;i<=N;i++)
		{
			cout<<"->"<<BestX[i]<<endl;
		}
		cout<<endl;
		cout<<"所需费用为："<<BestC<<endl;
	}
	else
		cout<<"问题无解!"<<endl;
}
template<class T>
void Traveling<T>::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))
	   {
         //搜索子树
         swap(X[i],X[j]);
         CC+=A[X[i-1]][X[i]];
         Backtrack(i+1);
         CC-=A[X[i-1]][X[i]];
         swap(X[i],X[j]);
	   }
	 }
 }
}