tsp.cpp

计算机算法设计与分析(王晓东)教材上相关源程序代码。 包括分治法(4)

#include "iostream.h"

void Swap(int *a,int* b);

class Traveling{
	friend int TSP(int **, int [],int,int);
	private:
		void Backtrack(int i);
		int init();
		int n,//图G的顶点数
			*x,//当前解
			*bestx;//当前最优解
		int ** a,//图G的临界矩阵
			cc,//当前费用
			bestc,//当前最优值
			NoEdge;//无边标记
		int * MinOut;//顶点i的最小出边费用
		int rcost;//最小出边费用和
};

int Traveling::init()
{
	MinOut = new int[n+1];
	rcost = 0;
	//计算MinOut[i]=顶点i的最小出边费用
	for(int i=1;i<=n;i++)
	{
		int Min=NoEdge;
		for(int j=1;j<=n;j++)
		{
			if(a[i][j]!=NoEdge && (a[i][j]<Min||Min==NoEdge))
			{
				Min= a[i][j];
			}
		}
		if(Min==NoEdge) return NoEdge;//无回路
		MinOut[i]=Min;
		rcost+=Min;
	
	}
	for(int j=1;j<=n;j++)
	{
		cout<<MinOut[j]<<"  ";
	}
	cout<<endl;
	cout<<rcost<<endl;
	return 1;
}

void Traveling::Backtrack(int i)
{
	if(i==n)
	{
		if(a[x[n-1]][x[n]]!=NoEdge && a[x[n]][x[1]]!=NoEdge &&
			(cc+a[x[n-1]][x[n]]+a[x[n]][x[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]][x[1]];
		}
	}
	else{
		for(int j=i;j<=n;j++)//是否可以进入x[j]子树？
		{
			if(a[x[i-1]][x[j]]!=NoEdge){
				//可行儿子结点
				int tcc = cc+a[x[i-1]][x[j]];
				int trcost = rcost - MinOut[x[i-1]];
				int b = tcc+trcost;

				if(b<bestc || bestc == NoEdge){
					//搜索子树
					//子树可能含最优解
					Swap(&x[i],&x[j]);
					cc+=a[x[i-1]][x[i]];
					rcost = rcost - MinOut[x[i-1]];
					Backtrack(i+1);
					cc-=a[x[i-1]][x[i]];
					rcost = rcost + MinOut[x[i-1]];
					Swap(&x[i],&x[j]);
				}
			}
		}
	}
}

int TSP(int ** a,int v[],int n, int NoEdge)
{
	Traveling 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;
	//搜所x[2:n]的全排列
	int f= Y.init();
	if(f==Y.NoEdge) 
	{	
		cout<<"无回路"<<endl;
		return Y.NoEdge;
	}
	Y.Backtrack(2);
	delete[] Y.x;
	return Y.bestc;
}

void Swap(int *a, int *b)
{
	int i =1;
	int *p = &i;
	*p = *a;
	*a = *b;
	*b = *p;
}

void main(void)
{	
	int n=4;
	
	int a[5]={0,0,0,0,0};
	int b[5]={0,0,30,6,4};
	int c[5]={0,30,0,5,10};
	int d[5]={0,6,5,0,20};
	int e[5]={0,4,10,20,0};
	int *p[5] ={a,b,c,d,e};

	int NoEdge=0;
	int v[5];
	int bestc = TSP(p,v,n,NoEdge);
	
	cout<<"最优路径为：";
	for(int k=1;k<=n;k++)
		cout<<v[k]<<" ";
	cout<<endl;
	cout<<"最优路径的耗费为：";
	cout<<bestc<<endl;
}