旅行售货员问题.cpp

算法分析中

/*
旅行售货员问题
解空间树是一棵排列树。实现对排列树搜索的优先队列式分支限界法也可以有两种
不同的实现方式。其一是仅使用一个优先队列来存储活结点。优先队列中的每个活
结点都存储从根到该活结点的相应路径。另一种实现方式是用优先队列来存储活结点
，并同时存储当前已经构造出的部分排列树。在这种实现方式下，优先队列中的活
结点就不必再存储从根到该活结点的相应路径。这条路径可在必要时候从存储的部分
排列树中获得。在下面的讨论中我们采用第一种实现方式。
*/
/*
我们用邻接矩阵表示所给的图G。在类traveling中用一个二维数组a存储图G的邻接矩
阵。
*/
/*
找出路径出错在什么地方，赋值运算的地方要注意
*/
#include<iostream>
using namespace std;

const int NoEdge = -100;
template< class Type >
class Traveling
{
	friend int main();
	public:
		Type BBTSP(int v[]);
	private:
		int n;
		//number of vertex in the graph
		Type **a;
		//图的邻接矩阵
		Type NoEdge;
		//图G的无边标志
		Type cc;
		//当前费用
		Type bestc;
		//当前最小费用
};

/*
选用最小堆表示活结点优先队列。最小堆中元素的类型为MinHeapNode。该类型结点包含
域x，用于记录当前解;s表示结点在排列树中的层次，从排列树的根结点到该结点的路径为x[0:s]
需要进一步搜索的顶点是x[s+1:n-1]。cc表示当前费用，lcost是子树费用的下界
rcost是x[s:n-1]中顶点最小出边费用和。具体算法可描述如下：
*/

template<class Type>
class MinHeap
{
	public:
		Type *H;
		int Capacity;
		int Size;
	public:
		MinHeap(int n)
		{
			H = NULL;
			H = (Type*)malloc( sizeof( Type ) * ( n + 1 ) );
			Capacity = n;
			Size = 0;
		}
		MinHeap( MinHeap& a )
		{
			//要排除自赋值的情况
			if ( this.H != a.H )
			{
				this.H = a.H;
				this.Size = a.Size;
				this.Capacity = a.Capacity;
				for( int i = 0; i < Size; ++i )
				{
					this.H[i] = a.H[size];
				}
			}
		}

		/*
		基本的堆插入操作
		为了将node插入到堆中
		首先在下一个空闲位置++Size处，创建一个空穴，否则该堆将不是完全树
		如果x可以放在该穴中而不破坏堆的序，那么插入完成
		否则我们把空穴的父亲结点上的元素移动到该穴中，这样空穴就朝着根的方向上行一步
		继续该过程直到x能被放入空穴为止
		*/
		void Insert( Type& node )
		{
			int i;
			cout<<"Size = "<<Size<<endl;
			for( i = ++Size; H[i / 2] > node; i /= 2 )
			{
				H[i] = H[i / 2];
				if ( i / 2 == 0 )
				{
					break;
				}
				
			}
			H[i] = node;
			
		}

		/*
		当删除一个最小元时
		在根结点处产生一个空穴。
		由于现在堆少了一个元素，因此堆中最后一个元素必须移动到该堆的某个地方
		如果x可以放到空穴中，那么DeleteMin完成
		否则应该将两个儿子中较小者移入空穴
		这样空穴就向下推了一层。重复该步骤直到x可以被放入空穴中
		*/
		void DeleteMin( Type& node )
		{
			int i,Child;
			Type MinElement,LastElement;
			MinElement = H[ 1 ];
			LastElement = H[Size--];

			for( i = 1; i * 2 <= Size; i = Child )
			{
				Child = i * 2;
				if ( ( Child != Size && H[ Child + 1 ] < H[ Child ] ) )
				{
					Child++;
				}

				if ( LastElement > H[ Child ] )
				{
					H[ i ] = H[ Child ];      
				}
				else
				{
					break;
				}
			}
			H[i] = LastElement;
			node = MinElement;
			
		}
		
};

template< class Type >
class MinHeapNode
{
	friend Traveling< Type >;
	public:
		MinHeapNode()
		{
			lcost = 0;
			cc = 0;
			rcost = 0;
			s = 0;
			x = 0;
		}
		operator Type() const
		{
			return lcost;
		}
		MinHeapNode* operator=( const MinHeapNode& a )
		{
			if ( &(*this) != &a )
			{
				lcost = a.lcost;
				cc = a.cc;
				rcost = a.rcost;
				s = a.s;
				x = a.x;
			}
			return this;
			
		}

		bool operator>( const MinHeapNode& a)
		{
			return lcost < a.lcost;
		}

		bool operator<( const MinHeapNode& a )
		{
			return lcost < a.lcost;
		}

	private:
		Type lcost;
		//子树费用的下界
		Type cc;
		//当前费用
		Type rcost;
		//x[s:n-1]中顶点最小出边费用和
		int s;
		//根结点到当前结点的路径为x[0:s]
		int *x;
		//需要进一步搜索的结点是x[s+1:n-1]
};

/*
算法开始创建一个容量为1000的最小堆，用于表示活结点优先队列。堆中每个结点的
lcost值是优先队列的优先级。接着计算出图中每个顶点的最小费用出边，并用Minout
记录。如果所给的有向图中某个顶点没有出边，则该图不可能有回路，算法即告结束。
如果每个顶点都有出边，则根据计算出来的Minout做算法的初始化。算法的第1个扩展结点
是排列树中根结点的惟一儿子结点。在该结点处已经确定的回路中惟一顶点为顶点1。因此
，初始时有s = 0,x[0] = 1, x[1:n-1]=(2,3,...,n),cc=0且rcost = Minout[i]总和i属于
(r,n)。算法中用bestc记录当前最优值，初始时还没找到回路,故bestc = NoEdge.
*/
template< class Type >
Type Traveling< Type >::BBTSP( int v[] )
{
	//解旅行售货员问题的优先队列式分支限界法
	//定义最小堆的容量为1000
	MinHeap< MinHeapNode< Type > > H(1000);
	Type *MinOut = new Type[n+1];
	//计算MinOut[i] = 顶点i的最小出边费用
	Type MinSum = 0;
	//最小出边费用和
	for( int i = 1; i <= n; ++i )
	{
		Type Min = NoEdge;
		for( int j = 1; j <= n; ++j )
		{
			//cout<<"a[i][j]: "<<a[i][j]<<endl;
			//cout<<"Min: "<<Min<<endl;
			if ( a[i][j] != NoEdge
			&& ( a[i][j] < Min || Min == NoEdge ) )
			{
				Min = a[i][j];
			}
		}
		if ( Min == NoEdge )
		{
			return NoEdge;
			//无回路
		}
		MinOut[i] = Min;
		MinSum += Min;
		//计算每个结点的最小出边以及最小出边和
	}
	//cout<<"MinSum: "<<MinSum<<endl;
	//初始化
	MinHeapNode< Type > E;
	E.x = new int[n];
	for( i = 0; i < n; ++i )
	{
		E.x[i] = i + 1;
	}
	E.s = 0;
	E.cc = 0;
	E.rcost = MinSum;
	Type bestc = NoEdge;
	//搜索排列空间树
	
	while( E.s <= n - 1 )
	//非叶子结点
	{
		cout<<"E.s: "<<E.s<<endl;
		//cout<<"开始处理新的扩展接点"<<endl;
		if ( E.s == n - 2 )
		//当前扩展结点是叶子结点的父结点
		//再加2条边构成回路
		//所构成回路是否优于当前最优解
		{
			cout<<"进入E.s == n-2"<<endl;
			cout<<"a[E.x[n-2]][E.x[n-1]]: "<<a[E.x[n-2]][E.x[n-1]]<<endl;
			cout<<"a[E.x[n-1]][1]: "<<a[E.x[n-1]][1]<<endl;
			cout<<"E.cc + a[E.x[n-2]][E.x[n-1]] + a[E.x[n-1]][1]: "<<E.cc + a[E.x[n-2]][E.x[n-1]] + a[E.x[n-1]][1]<<endl;
			cout<<"bestc: "<<bestc<<endl;
			if ( a[E.x[n-2]][E.x[n-1]] != NoEdge
			&& a[E.x[n-1]][1] != NoEdge
			&& ( E.cc + a[E.x[n-2]][E.x[n-1]] + a[E.x[n-1]][1] < bestc
			|| bestc == NoEdge ) )
			//费用更小回路
			{
				bestc = E.cc + a[E.x[n-2]][E.x[n-1]] + a[E.x[n-1]][1];
				E.cc = bestc;
				E.lcost = bestc;
				E.s++;

				cout<<"插入E.s == n - 2新数据前:"<<endl;
				cout<<"E.s: "<<E.s<<endl;
				cout<<"E.cc: "<<E.cc<<endl;
				cout<<"E.lcost: "<<E.lcost<<endl;
				for( i = 0; i < n; ++i )
			{
				cout<<"E.x["<<i<<"]"<<E.x[i]<<endl;
			}
				//getchar();
				H.Insert(E);
			//	cout<<"插入新数据后:"<<endl;
			//	getchar();
			//	getchar();
			}
			else
			{
				//delete []E.x;
				//舍弃扩展结点
			}
		}
		else
		//产生当前扩展结点的儿子结点
		{
			//cout<<"开始儿子儿子接点处理"<<endl;
			//cout<<"E.s: "<<E.s<<endl;
			for( int i = E.s + 1; i < n; ++i )
			{
				cout<<"边("<<E.x[E.s]<<","<<E.x[i]<<"): "<<a[E.x[E.s]][E.x[i]]<<endl;
				if ( a[E.x[E.s]][E.x[i]] != NoEdge )
				{
					//cout<<"可行儿子接点"<<endl;
					//可行儿子结点
					Type cc = E.cc + a[E.x[E.s]][E.x[i]];
					//cout<<"cc = "<<cc<<endl;
					Type rcost = E.rcost - MinOut[E.x[E.s]];
					//cout<<"rcost = "<<rcost<<endl;
					Type b = cc + rcost;
					//下界
					if ( b < bestc || bestc == NoEdge )
					{
						//子树可能含最优解
						//结点插入最小堆
						MinHeapNode< Type > N;
						N.x = new int[n];
						for( int j = 0; j < n; ++j )
						{
							N.x[j] = E.x[j];
						}
						N.x[E.s+1] = E.x[i];
						N.x[i] = E.x[E.s + 1];
						N.cc = cc;
						N.s = E.s + 1;
						N.lcost = b;
						N.rcost = rcost;
						H.Insert(N);
					}
				}
			}
			//cout<<"开始删除"<<endl;
			//delete []E.x;
			//完成结点扩展
			//cout<<"删除完成"<<endl;
		}
		/*try
		{
			H.DeleteMin(E);
		}
		catch(OutOfBounds)
		{
			break;
			//堆已空
		}*/
		if ( H.Size == 0 )
		{
			break;
		}
		else
		{
			H.DeleteMin(E);
			cout<<"取出新的扩展接点: "<<endl;
			cout<<"E.s: "<<E.s<<endl;
				cout<<"E.cc: "<<E.cc<<endl;
				cout<<"E.lcost: "<<E.lcost<<endl;
			for( i = 0; i < n; ++i )
			{
				cout<<"E.x["<<i<<"]"<<E.x[i]<<endl;
			}

			cout<<"Size = "<<H.Size<<endl;
		}
	}
	if ( bestc == NoEdge )
	{
		return NoEdge;
		//无回路
	}
	//将最优解复制到v[1:n]中
	cout<<"E.s: "<<E.s<<endl;
	for( i = 0; i < n; ++i )
	{
		cout<<"E.x["<<i<<"]"<<E.x[i]<<endl;
		v[i+1] = E.x[i];
	}
	while(true)
	{
		//释放最小堆中所有结点
		delete []E.x;
		/*try
		{
			H.DeleteMin(E);
		}
		catch(OutOfBounds)
		{
			break;
		}*/
		if ( H.Size == 0 )
		{
			break;
		}
		else
		{
			H.DeleteMin(E);
		}
	}
	cout<<"路径是: "<<endl;
	for( i = 0; i <= n; ++i )
	{
		cout<<v[i]<<" ";
	}
	cout<<endl;

	cout<<"bestc: "<<bestc<<endl;
	return bestc;
}

int main()
{
	int **a = 0;
	a = new int*[5];
	if ( a == 0 )
	{
		return 0;
	}

	for( int i = 0; i < 5; ++i )
	{	
		a[i] = 0;
		a[i] = new int[5];
		if ( a[i] == 0 )
		{
			return 0;
		}
	}

	a[0][0] = -100;
	a[0][1] = -100;
	a[0][2] = -100;
	a[0][3] = -100;
	a[0][4] = -100;

	a[1][0] = -100;
	a[1][1] = 0;
	a[1][2] = 1;
	a[1][3] = 1;
	a[1][4] = 40;

	a[2][0] = -100;
	a[2][1] = 1;
	a[2][2] = 0;
	a[2][3] = 30;
	a[2][4] = 1;

	a[3][0] = -100;
	a[3][1] = 1;
	a[3][2] = 30;
	a[3][3] = 0;
	a[3][4] = 1;

	a[4][0] = -100;
	a[4][1] = 4;
	a[4][2] = 1;
	a[4][3] = 1;
	a[4][4] = 40;
	
	Traveling<int> obj;
	obj.a = a;
	obj.bestc = 0;
	obj.cc = 0;
	obj.n = 4;
	obj.NoEdge = NoEdge;
	int *v = new int[5];
	for( int j = 0; j < 5; ++j )
	{
		v[j] = 0;
	}
	obj.BBTSP( v );

/*{
	friend int main();
	public:
		Type BBTSP(int v[]);
	private:
		int n;
		//number of vertex in the graph
		Type **a;
		//图的邻接矩阵
		Type NoEdge;
		//图G的无边标志
		Type cc;
		//当前费用
		Type bestc;
		//当前最小费用
};*/
	 
	return 0;
}