分支限界法求解装载问题实验报告

分支限界法求解装载问题一、方法一般原理分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。两种分支限界法（1）队列式(FIFO)分支限界法按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。（2）优先队列式分支限界法按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。二、描述问题有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i的重量为wi，且211ccwnii，要求确定是否有一个合理的装载方案可将这n个集装箱装上这2艘轮船。如果有，请给出该方案。三、由原理得到的算法、算法的复杂度、改进1、可得算法算法enquence将活结点加入队列。若i=n，则表示当前为叶节点，此时只要检查对应的可行解是否为最优解。in时,当期结点为内部节点，加入队列中。在算法的while循环中，首先检测当前扩展结点的左儿子结点是否为可行结点。如果是则将其加入到活结点队列中。然后将其右儿子结点加入到活结点队列中(右儿子结点一定是可行结点)。2个儿子结点都产生后，当前扩展结点被舍弃。活结点队列中的队首元素被取出作为当前扩展结点，由于队列中每一层结点之后都有一个尾部标记-1，故在取队首元素时，活结点队列一定不空。当取出的元素是-1时，再判断当前队列是否为空。如果队列非空，则将尾部标记-1加入活结点队列，算法开始处理下一层的活结点。2、时间复杂度Maxloading算法计算时间和空间复杂性均为O(2n)。3、可能的改进节点的左子树表示将此集装箱装上船，右子树表示不将此集装箱装上船。设bestw是当前最优解；wt是当前扩展结点所相应的重量；r是剩余集装箱的重量。则当wt+rbestw时，可将其右子树剪去，因为此时若要船装最多集装箱，就应该把此箱装上船。另外，为了确保右子树成功剪枝，应该在算法每一次进入左子树的时候更新bestw的值。while(true){//检查左儿子结点Typewt=Ew+w[i];//左儿子结点的重量if(wt=c){//可行结点if(wtbestw)bestw=wt;//加入活结点队列if(in)Q.push(wt);}//检查右儿子结点if(Ew+rbestw&&in)Q.push(Ew);//可能含最优解Ew=Q.front();Q.pop();//取下一扩展结点if(Ew==-1){//同层结点尾部if(Q.empty())returnbestw;Q.push(-1);//同层结点尾部标志Ew=Q.front();Q.pop();//取下一扩展结点i++;//进入下一层r-=w[i];}}构造最优解:为了在算法结束后能方便地构造出与最优值相应的最优解，算法必须存储相应子集树中从活结点到根结点的路径。为此目的，可在每个结点处设置指向其父结点的指针，并设置左儿子标志。templateclassTypeclassQNode{friendvoidEnQueue(queueQNodeType*&,Type,int,int,Type,QNodeType*,QNodeType*&,int*,bool);friendTypeMaxLoading_three(Type*,Type,int,int*);private:QNode*parent;//指向父结点的指针boolLChild;//左儿子标志Typeweight;//结点所相应的载重量};四、算法实现voidEnQueue(intwt,int&bestw,inti,intn,Queue*E,Queue*&bestE,boolch)//该函数负责加入活结点{//如果不是叶结点，则将结点权值wt加入队列Qif(i==n){if(wt==bestw){//当前最优载重量bestE=E;bestx[n]=ch;}return;}Add(wt,E,ch);//不是叶子}intMaxLoading(intw[],intc,intn){//返回最优装载值//为层次1初始化interr;//返回值inti=1;//当前扩展结点的层intEw=0;//当前扩展结点的权值intr=0;//剩余集装箱重量Queue*E=0;//当前扩展结点//*bestE当前最优扩展结点for(intj=2;j=n;j++)r+=w[j];bestw=0;//目前的最优值Q=newQueue;Q-next=NULL;Q-weight=-1;err=Add(-1,NULL,0);//标记本层的尾部if(err){return0;}while(true){intwt=Ew+w[i];//检查左孩子结点if(wt=c){if(wtbestw)bestw=wt;EnQueue(Ew+w[i],bestw,i,n,E,bestE,1);}//右孩子总是可行的EnQueue(Ew,bestw,i,n,E,bestE,0);Delete(E);//取下一个扩展结点if(E!=NULL&&E-weight==-1){//到达层的尾部if(IsEmpty())break;if(in)Add(-1,NULL,0);//同层结点的尾部Delete(E);//取下一扩展结点i++;//进入下一层r-=w[i];}Ew=E-weight;}//构造当前最优解for(j=n-1;j0;j--){bestx[j]=bestE-LChild;bestE=bestE-parent;}return0;}五、总结由此，我们可以总结出分支限界法的设计思路：设求解最大化问题，解向量为X=(x1,…,xn)，xi的取值范围为Si，|Si|=ri。在使用分支限界搜索问题的解空间树时，先根据限界函数估算目标函数的界[down,up]，然后从根结点出发，扩展根结点的r1个孩子结点，从而构成分量x1的r1种可能的取值方式。对这r1个孩子结点分别估算可能的目标函数bound(x1)，其含义：以该结点为根的子树所有可能的取值不大于bound(x1)，即：bound(x1)≥bound(x1,x2)≥…≥bound(x1,…,xn)若某孩子结点的目标函数值超出目标函数的下界，则将该孩子结点丢弃；否则，将该孩子结点保存在待处理结点表PT中。再取PT表中目标函数极大值结点作为扩展的根结点，重复上述。直到一个叶子结点时的可行解X=(x1,…,xn)，及目标函数值bound(x1,…,xn)。分支限界法与回溯法的不同：（1）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。（2）搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。六、附录（源码）#includeiostreamusingnamespacestd;classQueue{public:Queue*parent;//指向父结点的指针boolLChild;//左儿子标志intweight;//结点所相应的载重量Queue*next;};int*bestx;intbestw=0;//目前的最优值Queue*Q;//活结点队列Queue*bestE;//当前最优扩展结点Queue*lq=NULL;Queue*fq=NULL;intAdd(intw,Queue*E,booll){Queue*q;q=newQueue;q-next=NULL;q-weight=w;q-parent=E;q-LChild=l;if(Q-next==NULL){Q-next=q;fq=lq=Q-next;//一定要使元素放到链中}else{lq-next=q;lq=q;}return0;}intIsEmpty(){if(Q-next==NULL)return1;return0;}intDelete(Queue*&E){Queue*tmp=NULL;tmp=fq;E=fq;Q-next=fq-next;/*一定不能丢了链表头*/fq=fq-next;return0;}voidEnQueue(intwt,int&bestw,inti,intn,Queue*E,Queue*&bestE,boolch)//该函数负责加入活结点{//如果不是叶结点，则将结点权值wt加入队列Qif(i==n){if(wt==bestw){//当前最优载重量bestE=E;bestx[n]=ch;}return;}Add(wt,E,ch);//不是叶子}intMaxLoading(intw[],intc,intn){//返回最优装载值//为层次1初始化interr;//返回值inti=1;//当前扩展结点的层intEw=0;//当前扩展结点的权值intr=0;//剩余集装箱重量Queue*E=0;//当前扩展结点//*bestE当前最优扩展结点for(intj=2;j=n;j++)r+=w[j];bestw=0;//目前的最优值Q=newQueue;Q-next=NULL;Q-weight=-1;err=Add(-1,NULL,0);//标记本层的尾部if(err){return0;}while(true){intwt=Ew+w[i];//检查左孩子结点if(wt=c){if(wtbestw)bestw=wt;EnQueue(Ew+w[i],bestw,i,n,E,bestE,1);}//右孩子总是可行的EnQueue(Ew,bestw,i,n,E,bestE,0);Delete(E);//取下一个扩展结点if(E!=NULL&&E-weight==-1){//到达层的尾部if(IsEmpty())break;if(in)Add(-1,NULL,0);//同层结点的尾部Delete(E);//取下一扩展结点i++;//进入下一层r-=w[i];}Ew=E-weight;}//构造当前最优解for(j=n-1;j0;j--){bestx[j]=bestE-LChild;bestE=bestE-parent;}return0;}voidmain(){intn=0;intc=0;inti=0;int*w;cout请输入集装箱树数量:;cinn;cout请输入轮船的载重量:;cinc;w=newint[n+1];bestx=newint[n+1];cout请输入集装箱的重量:;for(i=1;i=n;i++)cinw[i];MaxLoading(w,c,n);cout最优载重量为:bestwendl;cout最优装载方案为(1表示装入,0表示不装入):;for(i=1;i=n;i++)coutbestx[i];}