装载问题（分支限界法）

装载问题（分支限界法）

问题定义：

• 有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i的重量为w，且Ew≤c1+c2
• 装载问题要求确定是否有一个合理的装载方案，可将这n个集装箱装E这2艘轮船。
• 如果有，找出一种装载方案。

方案

• 将第一艘船尽可能装满
• 剩余物体装上第二艘轮船

1.队列式分支限界法如何知道当前处理的结点属于解空间树中的哪一层？

1. 队列Q初始化为-1，t记录层数，初始化为1
2. 添加A结点的子结点，B,C都满足约束条件，Q：-1，B，C
3. 弹出队首元素：-1，啊，看到了-1~那第t层一定全部变成了死结点! t++=2, push -1 ,Q: B，C，-1
4. 弹出队首元素，B，嗯不是-1，添加B的所有的子结点，D不满足约束条件，Q：C，-1，E
5. 弹出队首元素，C，不是-1，添加C的子结点，F，G都满足约束，Q：-1，E，F，G
6. 弹出队首元素，-1！ t++=3, push -1，Q：E，F，G，-1 弹出队首元素，E，添加E的子结点，因为t=3，所以J，K均是叶子节点，不再添加
7. 同理，F，G都是叶子节点，直接判断是不是可行解和最佳解，最后弹出-1表示解空间树遍历结束

2.代码实现
①队列

#include <Queue.h>
int fun(int w,int *v, int n){
	if(n==0) return 0;
	int currw=v[0]<=w?v[0]:0,t=1,bestw=0;//当前结点的权值，第t层,最佳解，当前部分解
	Queue <int> Q;
	Q.add(-1);//根节点不必加入
	while(true){		
		//到达叶子节点，判断是不是当前最优解
		if(t==n){
			if(currw>bestw) bestw=currw;
		}
		//否则剪左右枝
	    else{
		    //处于第t+1层的左子节点，剪枝
			if(currw+v[t]<=w){
				Q.add(currw+v[t]);
			}
			//第t+1层右子结点,剪枝
			if(currw+accum(t+2)>bestw)
				Q.add(currw);
		}
		//下一个待处理的结点到根节点路径权值
		currw=Q.front();
		
		if(currw==-1){//一层结束
			if(Q.empty()) return bestw;//全部访问完
			Q.add(-1);
			t++;
			currw=Q.front();
		}
	}
}

如何得到解向量？
将每个点用一个类表示，Qnode:

class Qnode{
public:
	Qnode(int par,bool Lch,int wt){
		parent=par;
		Lchild=Lch;
		w=wt;
	}
	friend int fun(int w,int *v, int n);
	friend void bestx(int n,int *x);
private:	
	Qnode* parent,*bestq;//父结点、最优解的最后一个结点
	bool Lchild;//是不是父结点的左子节点
	int w;//第一艘船的载重量
};

int fun(int w,int *v, int n){
	if(n==0) return 0;
	int currw=v[0]<=w?v[0]:0,t=1,bestw=0;//当前结点的权值，第t层,最佳解，当前部分解
	Queue <Qnode* > Q;
	Qnode *currq;
	Q.add(0);//同层结点尾部标志
	while(true){		
		//到达叶子节点，判断是不是当前最优解
		if(t==n){
			if(currw>bestw){
		   		 bestw=currw;
		   		 bestq=currq;
		   	}
		}
		//否则剪左右枝
	    else{
		    //处于第t+1层的左子节点，剪枝
			if(currw+v[t]<=w){
				Qnode q=Qnode(currq,1,currw+v[t]);
				Q.add(&q);
			}
			//第t+1层右子结点,剪枝
			if(currw+accum(t+2)>bestw){
				Qnode q=Qnode(currq,0,currw);
				Q.add(&q);
			}
		}
		//下一个待处理的结点到根节点路径权值
		currq=Q.front();
		Q.pop();
		currw=currq->wt;
		if(currq==0){//一层结束
			if(Q.empty()) return bestw;//全部访问完
			Q.add(0);
			t++;
			currq=Q.front();
			currw=currq->wt;
		}
	}
}

void bestx(int n,int *x){
	Qnode *par=bestq;
	for(int i=n-1;i>0;i--){
		x[i]=par->Lchild?1:0;
		par=par->parent;
	}
}

②优先队列

a.优先级是什么？
从根节点到该结点路径上的载重量+剩余的集装箱重量之和

• 优先队列中优先级最大的活结点成为下一个扩展结点。以结点x为根的子树中所有结点相应的路径的载重量不超过它的优先级。
• 子集树中叶结点所相应的载重量与其优先级相同。
• 在优先队列式分支限界法中，一旦有一个叶结点成为当前扩展结点，则可以断言该叶结点所相应的解即为最优解。此时可终止算法。

b.实现方法:

• 最大优先级队列中的活节点都是互相独立的，因此每个活节点内部必须记录从子集树的根到此节点的路径。
• 一旦找到了最优装载所对应的叶节点,就利用这些路径信息来计算x值。

template <class Type>class HeapNode;
class bbnode {
	friend void AddLiveNode (MaxHeap<HeapNode<int>> &，bbnode *，int, bool, int);
	friend int MaxLoading(int*, int, int, int*);
	friend class AdjacencyGraph;
private:
	bbnode *parent;//指向父结点的指针
	bool LChild;//左儿子结点标志
};

template<class Type>
class HeapNode {
	friend void AddLiveNode(MaxHeap<HeapNode<Type> >&, bbnode*, Type, bool, int);
	friend Type MaxLoading(Type*, Type, int, int*);
public:
	operator Type () const { return uweight; }
private:
	bbnode *ptr;//指向活结点在子集树中相应结点的指针
	Type uweight;//活结点优先级(上界)
	int level;//活结点在子集树中所处的层序号
};

template <class Type>
//将活结点加入到表示活结点优先队列的最大堆H中
void AddLiveNode (MaxHeap<HeapNode<Type> >&H，bbnode *E, Type wt, bool ch, int 1ev) {
	bbnode *b = new bbnode;
	b->parent = E;
	b->LChild = ch;
	HeapNode<Type> N;
	N.uweight = wt;
	N.level = lev;
	N.ptr = b;
	H.Insert(N);
}
template <class Type>
//优先队列式分支限界法，返回最优载重量，bestx 返回最优解
Type MaxLoading(Type w[], Type C, int n, int bestx[]) {
	MaxHeap <HeapNode<Type>> H(1000);//定义最大堆的容量为1000
	Type *r = new Type [n+1];//定义剩余重量数组r
	r[n] = 0;
	for (int j=n-1; 1 > 0; j--)
		r[j] = r[j+1]+w[j+1];//初始化
	int i=1;//当前扩展结点所处的层
	bbnode *E = 0;//当前扩展结点
	Type EW = e;//扩展站点所相应的载重量
	//搜索子集空间树
	while (i != n+1) {
		//非叶结点
		//检查当前扩展结点的儿子结点
		if (Ew+W[i] <= c)//左儿子结点为可行结点
			AddLiveNode(H，E, Ew+w[i]+r[i], true, i+1);
		AddLiveNode(H, E, Ew+r[i], false, i+1);//右儿子结点
		HeapNode<Type> N;
		//取下一扩展结点
		H.DeleteMax(N);
		//非空
		i = N.level; 
		E = N.ptr;
		Ew = N.uweight-r[i-1];
		//构造当前最优解
		for(int j=n;j>e;j--){
			bestx[j] = E->LChild;
			E = E->parent;
		}
		return EW;
}