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

《分支限界法求解装载问题实验报告.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、分支限界法求解装载问题一、方法一般原理分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。两种分支限界法（1）队列式(FIFO)分支限界法按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。（2）优先队列式分支限界法按照优先队列中规定

2、的优先级选取优先级最高的节点成为当前扩展节点。二、描述问题有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i的重量为nwi，且wic1c2，要求确定是否有一个合理的装载方案可将这n个集装箱装上这2i1艘轮船。如果有，请给出该方案。三、由原理得到的算法、算法的复杂度、改进1、可得算法算法enquence将活结点加入队列。若i=n，则表示当前为叶节点，此时只要检查对应的可行解是否为最优解。i

3、入到活结点队列中(右儿子结点一定是可行结点)。2个儿子结点都产生后，当前扩展结点被舍弃。活结点队列中的队首元素被取出作为当前扩展结点，由于队列中每一层结点之后都有一个尾部标记-1，故在取队首元素时，活结点队列一定不空。当取出的元素是-1时，再判断当前队列是否为空。如果队列非空，则将尾部标记-1加入活结点队列，算法开始处理下一层的活结点。2、时间复杂度nMaxloading算法计算时间和空间复杂性均为O(2)。3、可能的改进节点的左子树表示将此集装箱装上船，右子树表示不将此集装箱装上船。设bestw是当前最优解；wt是当前扩展结点所相应的重量；r是剩余集装箱的重量。则当wt+r

4、bestw时，可将其右子树剪去，因为此时若要船装最多集装箱，就应该把此箱装上船。另外，为了确保右子树成功剪枝，应该在算法每一次进入左子树的时候更新bestw的值。while(true){//检查左儿子结点Typewt=Ew+w[i];//左儿子结点的重量if(wt<=c){//可行结点if(wt>bestw)bestw=wt;//加入活结点队列if(ibestw&&i

5、.empty())returnbestw;Q.push(-1);//同层结点尾部标志Ew=Q.front();Q.pop();//取下一扩展结点i++;//进入下一层r-=w[i];}}构造最优解:为了在算法结束后能方便地构造出与最优值相应的最优解，算法必须存储相应子集树中从活结点到根结点的路径。为此目的，可在每个结点处设置指向其父结点的指针，并设置左儿子标志。templateclassQNode{friendvoidEnQueue(queue*>&,Type,int,int,Type,QNode*,QNode

6、>*&,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]

7、=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