/*
旅行售貨員問題
解空間樹是一棵排列樹。實現對排列樹搜索的優先隊列式分支限界法也可以有兩種
不同的實現方式。其一是僅使用一個優先隊列來存儲活結點。優先隊列中的每個活
結點都存儲從根到該活結點的相應路徑。另一種實現方式是用優先隊列來存儲活結點
，并同時存儲當前已經構造出的部分排列樹。在這種實現方式下，優先隊列中的活
結點就不必再存儲從根到該活結點的相應路徑。這條路徑可在必要時候從存儲的部分
排列樹中獲得。在下面的討論中我們采用第一種實現方式。
*/
/*
我們用鄰接矩陣表示所給的圖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;
}