队列分支限界法解最优装载问题.cpp

算法分析中

#include<iostream>
#include "tree.h"
#include "binheap.h"
#include <algorithm>
#include <deque>
using namespace std;

/*
while循环检测中，首先检测当前扩展结点的左儿子结点是否为可行结点
如果是则调用EnQueue将其加入到活结点队列中，然后将其右儿子结点加入到活结点
队列中（右儿子结点总是可行的）。
两个儿子结点都产生后，当前扩展结点被舍弃。活结点队列中的队首元素被取出作为当前扩展结点
由于队列中每一层结点之后都有一个尾部标记-1
故在取队首元素时，活结点队列一定不空。当取出的元素是-1时再判断当前队列是否为空。
如果队列非空。则将尾部标记-1假
入到队列中，必须这样，不然会出现反复取到-1的死循环。
*/
/*template<class Type>
class Graph
{
	friend int main();
	public:
		void ShortestPaths(int);
	private:
		int n;
		//图G的顶点数
		int *prev;
		//前趋顶点数组
		Type **c;
		//图G的邻接矩阵
		Type *dist;
		//最短距离数组
};*/

template<class Type>
class MinHeapNode
{
	public:
		MinHeapNode()
		{
		};

		MinHeapNode( MinHeapNode& a )
		{
			i = a.i;
			length = a.length;
		};

		operator int() const
		{
			return length;
		};

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

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

	private:
		int i;
		//顶点编号
		Type length;
		//当前路长
};

/*
堆结构：
堆就是一棵完全二叉树
数组来存储各个结点
数组中任一位置i上的元素，其左儿子在位置2i上，右儿子在2*i+1上，当然了存储下标从1开始

堆序性质
在一个堆中，对于每一个结点x，x的父亲中的关键字小于x中的关键字，根结点除外
*/

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

		void Add( Type& node )
		{
			if ( Size == Capacity )
			{
				cout<<"capacity"<<endl;
				return;
			}
			else
			{
				//cout<<"Add type:"<<endl;
				
				if ( Rear + 1 == Capacity )
				{
					H[Rear] = node;
					Rear = 0;
					++Size;
				}
				else
				{
					H[Rear] = node;
					++Size;
					++Rear;
				}
				//cout<<"Size = "<<Size<<endl;
				//cout<<"Rear = "<<Rear<<endl;

			}
			
		};

		void Delete( Type& node )
		{
			if ( Size == 0 )
			{
				return;
			}
			else
			{
				//cout<<"Delete:"<<endl;
				
				if ( Front == Capacity )
				{
					Front = 0;
				}
				node = H[Front];
				//cout<<"node:"<<endl;
				++Front;
				--Size;
			}
			//cout<<"Size = "<<Size<<endl;
			//cout<<"Front = "<<Front<<endl;

		};

		bool IsEmpty()
		{
			return ( 0 == Size );
		};
};

template< class Type >
class QNode
{
	friend void EnQueue( Queue< QNode< Type > * > &Q,
						 Type wt,
						 int i,
						 int n,
						 Type bestw,
						 QNode< Type > *E,
						 QNode< Type > *&bestE,
						 int *bestx,
						 bool ch);
	friend Type MaxLoading( Type* w,
							Type c,
							int n,
							int* bestx );

	QNode()
	{
		parent = 0;
		LChild = 0;
		weight = 0;
	};

	bool operator=( QNode& a )
	{
		parent = a.parent;
		LChild = a.LChild;
		weight = a.weight;
		return true;
	};

	void print()
	{
		cout<<"parent = "<<parent<<endl;
		cout<<"LChild = "<<LChild<<endl;
		cout<<"weight = "<<weight<<endl;
	};

	private:
		QNode *parent;
		//指向父结点的指针
		bool LChild;
		//左儿子标志
		Type weight;
		//结点所相应的载重量
};

template< class Type >
void EnQueue( Queue< QNode< Type > * > &Q,
			  Type wt,
			  int i,
			  int n,
			  Type bestw,
			  QNode< Type > *E,
			  QNode< Type > *&bestE,
			  int *bestx,
			  bool ch )
{
	//将活结点加入到活结点队列中
	//使用指针的引用，是可以对bestE进行修改
	if ( i == n )
	{
		//可行叶结点
		if ( wt == bestw )
		{
			//当前最优载重量
			bestE = E;
			bestx[n] = ch;
		}
		return;
	}
	QNode< Type > *b;
	b = new QNode< Type >;
	b->weight = wt;
	b->parent = E;
	b->LChild = ch;
	Q.Add(b);

}

template< class Type >
Type MaxLoading( Type *w,Type c,int n,int *bestx )
{
	//队列式分支限界法，返回最优载重量，bestx返回最优解
	//初始化
	Queue< QNode< Type > * > Q(20);
	//活结点队列
	QNode<Type> *O;
	O = new QNode<Type>;
	O->weight = -1;
	O->LChild = -1;
	O->parent = 0;
	Q.Add(O);
	//同层结点尾部标志
	int i = 1;
	//当前扩展结点所处的层
	Type Ew = 0;
	//扩展结点所相应的载重量
	Type bestw = 0;
	//当前最优载重量
	Type r = 0;
	//剩余集装箱重量
	for( int j = 2; j <= n; ++j )
	{
		r += w[j];
	}
	QNode< Type > *E = 0;
	//当前扩展结点
	QNode< Type > *bestE;
	//当前最优结点
	//搜索子集空间树
	while( true )
	{
		//检查左儿子结点
		Type wt = Ew + w[i];
		if ( wt <= c )
		{
			// 可行结点
			if ( wt > bestw )
			{
				bestw = wt;
			}
			EnQueue( Q,wt,i,n,bestw,E,bestE,bestx,true );
		}
		
		// 检查右儿子结点
		if ( Ew + r > bestw )
		{
			EnQueue( Q,Ew,i,n,bestw,E,bestE,bestx,false );
		}
		
		Q.Delete( E );
		// 取下一扩展结点
		
		if ( E->weight == -1  )
		{
			//同层结点尾部
			if ( Q.IsEmpty() )
			{
				break;
			}
			Q.Add( O );
			//同层结点尾部标志
			
			Q.Delete( E );
			//取下一个扩展结点
			i++;
			//进入下一层
			r -= w[i];
			//剩余的集装箱数量
		}
		Ew = E->weight;
		//新扩展结点所相应的载重量
	}
	//构造当前最优解

	for( j = n - 1; j > 0; --j )
	{
		bestx[j] = bestE->LChild;
		bestE = bestE->parent;
	}
	cout<<bestw<<endl;
	return bestw;
}

int main()
{
	int a[4] = 
	{
		0,10,30,33
	};
	int c = 50;
	int b[4] = {0,0,0,0};
	MaxLoading<int>(a,50,3,b);
	return 0;
}