计算机算法设计与分析：分支限界法
|
180
|
头歌,算法

1668 字
|
21 分钟

第1关：装载问题 (FIFO 优先队列法)

题目

问题描述

有一批共个集装箱要装上 2 艘载重量分别为 C1 和 C2 的轮船，其中集
装箱 i 的重量为 Wi ，且\(\sum_{i=1}^nw_i\leq c_1+c_2\)

装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。如果有，找出一种装载方案。

容易证明：如果一个给定装载问题有解，则采用下面的策略可得到最优装载方案。

(1)首先将第一艘轮船尽可能装满；

(2)将剩余的集装箱装上第二艘轮船。

任务描述

本关任务：采用队列式分支限界法来完成装载问题

相关知识

在算法的 while 循环中，首先检测当前扩展结点的左儿子结点是否为可行结点。如果是则将其加入到活结点队列中。然后将其右儿子结点加入到活结点队列中(右儿子结点一定是可行结点)。 2 个儿子结点都产生后，当前扩展结点被舍弃。
活结点队列中的队首元素被取出作为当前扩展结点，由于队列中每一层结点之后都有一个尾部标记 -1 ，故在取队首元素时，活结点队列一定不空。当取出的元素是 -1 时，再判断当前队列是否为空。如果队列非空，则将尾部标记 -1 加入活结点队列，算法开始处理下一层的活结点。

while (true) {
    // 检查左儿子结点
    if (Ew + w[i] <= c) // x[i] = 1
        EnQueue(Q, Ew + w[i], bestw, i, n);
    // 右儿子结点总是可行的
    EnQueue(Q, Ew, bestw, i, n); // x[i] = 0
    Q.Delete(Ew);     // 取下一扩展结点
    if (Ew == -1) {      // 同层结点尾部
        if (Q.IsEmpty()) return bestw;
        Q.Add(-1);        // 同层结点尾部标志
        Q.Delete(Ew);  // 取下一扩展结点
        i++;
    }                 // 进入下一层      
}

算法改进
节点的左子树表示将此集装箱装上船，右子树表示不将此集装箱装上船。设 bestw 是当前最优解； ew 是当前扩展结点所相应的重量； r 是剩余集装箱的重量。则当 ew+rbestw 时，可将其右子树剪去，因为此时若要船装最多集装箱，就应该把此箱装上船。

另外，为了确保右子树成功剪枝，应该在算法每一次进入左子树的时候更新 bestw 的值。

// 检查左儿子结点
  Type wt = Ew + w[i];   // 左儿子结点的重量
      if (wt <= c) {     // 可行结点
         if (wt > bestw) bestw = wt;
         // 加入活结点队列
         if (i < n) Q.Add(wt);

    //检查右儿子结点
      if (Ew + r > bestw && i < n)
          Q.Add(Ew);     // 可能含最优解
      Q.Delete(Ew);     // 取下一扩展结点

构造最优解
为了在算法结束后能方便地构造出与最优值相应的最优解，算法必须存储相应子集树中从活结点到根结点的路径。为此目的，可在每个结点处设置指向其父结点的指针，并设置左、右儿子标志。

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

编程要求

请仔细阅读右侧代码，结合相关知识，在 Begin - End 区域内进行代码补充，完成使用队列式分支限界法来完成装载问题的任务。

测试说明

平台会对你编写的代码进行测试：

测试输入：
4
70
20 10 26 15

预期输出：
Ship load:70
The weight of the goods to be loaded is:
20 10 26 15
Result:
1 0 1 1
The optimal loading weight is:61

开始你的任务吧，祝你成功！

参考答案

studentFIFO.cpp

//装载问题 队列式分支限界法求解 

#include "Queue.h"
#include <iostream>
using namespace std;
 
int N = 0;
 
template<class Type>
class QNode
{
	public:
		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);
 
template<class Type>
Type MaxLoading(Type w[],Type c,int n,int bestx[]);
 
int main()
{
	float c = 0;  
    float w[100] = {0};//下标从1开始  
    int x[100];  
	float bestw;
	
	cin>>N;
	cin >>c;
	for(int i=1; i<=N; i++)  
    {  
        cin>>w[i];  
    }  
    cout<<"Ship load:"<<c<<endl;  
    cout<<"The weight of the goods to be loaded is:"<<endl;  
    for(int i=1; i<=N; i++)  
    {
        cout<<w[i]<<" ";  
    }  
    cout<<endl;  
   
    bestw = MaxLoading(w,c,N,x);  
  
    cout<<"Result:"<<endl;  
    for(int i=1; i<=N; i++)  
    {  
        cout<<x[i]<<" ";  
    }  
    cout<<endl;  
	cout<<"The optimal loading weight is:"<<bestw<<endl;
  
    return 0;  
}
 
//将活节点加入到活节点队列Q中
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)
{
	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;		//活节点队列
	Q.Add(0);					//同层节点尾部标识
	int i = 1;					//当前扩展节点所处的层
	Type Ew = 0,				//扩展节点所相应的载重量
		 bestw = 0,				//当前最优装载重量
		 r = 0;					//剩余集装箱重量
 
	for(int j=2; j<=n; j++)
	{
		r += w[j];
	}
	
	QNode<Type> *E = 0,			//当前扩展节点
				*bestE;			//当前最优扩展节点
 
	//搜索子集空间树
	//**************begin************/
	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) {//同层节点尾部
            if(Q.IsEmpty()) {
                break;
            }
            Q.Add(0);       //同层节点尾部标识
            Q.Delete(E);    //取下一扩展节点
            i++;            //进入下一层
            r-=w[i];        //剩余集装箱重量
        }
        Ew  =E->weight;        //新扩展节点所对应的载重量
    }
	//**************end**************/
 
	//构造当前最优解
	//**************begin************/
    for(int j = n - 1; j > 0; --j) {
        bestx[j] = bestE->LChild;
        bestE = bestE->parent;
    }
	//**************end**************/
	return bestw;
}

第2关：装载问题 (最优队列法)

题目

问题描述

有一批共个集装箱要装上 2 艘载重量分别为 C1 和 C2 的轮船，其中集
装箱i的重量为 Wi ，且\(\sum_{i=1}^nw_i\leq c_1+c_2\)

装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这 2 艘轮船。如果有，找出一种装载方案。

容易证明：如果一个给定装载问题有解，则采用下面的策略可得到最优装载方案。

(1)首先将第一艘轮船尽可能装满；

(2)将剩余的集装箱装上第二艘轮船。

任务描述

本关任务：采用优先队列式分支限界法来完成装载问题

相关知识

  1. 解装载问题的优先队列式分支限界法用最大优先队列存储活结点表。活结点 x 在优先队列中的优先级定义为从根结点到结点x的路径所相应的载重量再加上剩余集装箱的重量之和。

  2. 优先队列中优先级最大的活结点成为下一个扩展结点。以结点 x 为根的子树中所有结点相应的路径的载重量不超过它的优先级。子集树中叶结点所相应的载重量与其优先级相同。

  3. 在优先队列式分支限界法中，一旦有一个叶结点成为当前扩展结点，则可以断言该叶结点所相应的解即为最优解。此时可终止算法。

编程要求

请仔细阅读右侧代码，结合相关知识，在Begin - End区域内进行代码补充，完成采用优先队列式分支限界法来完成装载问题的任务。

测试说明

平台会对你编写的代码进行测试：

测试输入：
4
70
20 10 26 15

预期输出：
Ship load:70
The weight of the goods to be loaded is:
20 10 26 15
Result:
1 0 1 1
The optimal loading weight is:61

开始你的任务吧，祝你成功！

参考答案

studentOPT.cpp

//装载问题 优先队列式分支限界法求解 
#include "MaxHeap.h"

 
int N;
 
class bbnode;
 
template<class Type>
class HeapNode
{

	public:
		operator Type() const{return uweight;}
		bbnode *ptr;		//指向活节点在子集树中相应节点的指针
		Type uweight;		//活节点优先级(上界)
		int level;			//活节点在子集树中所处的层序号
};
 
class bbnode
{
	template<class Type>
	friend void AddLiveNode(MaxHeap<HeapNode<Type>>& H,bbnode *E,Type wt,bool ch,int lev);
	template<class Type>
	friend Type MaxLoading(Type w[],Type c,int n,int bestx[]);
	friend class AdjacencyGraph;
 
	private:
		bbnode *parent;		//指向父节点的指针
		bool LChild;		//左儿子节点标识
};
 
template<class Type>
void AddLiveNode(MaxHeap<HeapNode<Type>>& H,bbnode *E,Type wt,bool ch,int lev);
 
template<class Type>
Type MaxLoading(Type w[],Type c,int n,int bestx[]);
 
 
int main()
{
	float c = 0;  
    float w[100] = {0};//下标从1开始  
    int x[100];  
	float bestw;
	
	cin>>N;
	cin >>c;
	for(int i=1; i<=N; i++)  
    {  
        cin>>w[i];  
    }  
    cout<<"Ship load:"<<c<<endl;  
    cout<<"The weight of the goods to be loaded is:"<<endl;  
    for(int i=1; i<=N; i++)  
    {  
        cout<<w[i]<<" ";  
    }  
    cout<<endl;  
	
    bestw = MaxLoading(w,c,N,x);  
  
    cout<<"Result:"<<endl; 
    for(int i=1; i<=N; i++)  
    {  
        cout<<x[i]<<" ";  
    }  
    cout<<endl;  
	cout<<"The optimal loading weight is:"<<bestw<<endl;
  
    return 0; 
}
 
//将活节点加入到表示活节点优先队列的最大堆H中
template<class Type>
void AddLiveNode(MaxHeap<HeapNode<Type>>& H,bbnode *E,Type wt,bool ch,int lev)
{
	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);
}
 
//优先队列式分支限界法，返回最优载重量，bestx返回最优解
template<class Type>
Type MaxLoading(Type w[],Type c,int n,int bestx[])
{
	//定义最大的容量为1000
	MaxHeap<HeapNode<Type>> H(1000);
 
	//定义剩余容量数组
	Type *r = new Type[n+1];
	r[n] = 0;
 
	//**************begin************/
    for(int j=n-1; j>0; j--) {
        r[j] = r[j+1] + w[j+1];
    }
	//**************end**************/
	
 
	//初始化
	int i = 1;//当前扩展节点所处的层
	bbnode *E = 0;//当前扩展节点
	Type Ew = 0; //扩展节点所相应的载重量
 
	//搜索子集空间树
	//**************begin************/
    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];
    }
	//**************end**************/
 
	//构造当前最优解
	//**************begin************/
    	for(int j=n; j>0; j--) {
        bestx[j] = E->LChild;
        E = E->parent;
    }
	//**************end**************/
 
	return Ew;
}
上一篇
下一篇