分支限界法求装载问题_物联1301班_刘悦_08080112.doc

算法分析与设计实验报告第 X 次实验姓名学号班级时间地点 实验名称分支限界法求装载问题实验目的通过上机实验，掌握分支限界算法的思想，利用分支限界算法求装载问题并实现。实验原理活结点x在最优队列中的优先级定义为从根结点到结点x的路径所相应的载重量再加上剩余集装箱的总量之和。优先队列中优先级最大的活结点成为下一个扩展结点。优先队列中活结点x的优先级为x.uweight。以结点x为根的子树中所有结点相应的路径的载重量不超过x.uweight。子集树中叶结点相应载重量与其优先级一样。因此，一旦一个叶结点成为当前扩展结点，如此可以断言该叶结点所相应的解为即为最优解，终止算法。这里选用在搜索进程中保存当前已构造出的局部解空间树，在算法确定课达到最优解的叶结点时，就可以在解空间树中从该叶结点开始向根结点回溯，构造出相应的最优解。实验步骤 算法开始创建一个最大堆，表示活结点优先队列。 算法第一个扩展结点是子集树中根结点。 开始子集树的根结点是扩展结点。循环产生当前扩展结点的左右儿子结点。 如果当前扩展结点的左儿子结点是可行结点，即它所相应的重量为超过轮船的载重量，如此将它参加到子集树的第i+1层上，并插入最大堆。 扩展结点的右儿子结点总是可行的，故直接插入子集树的最大堆中。 接着从最大堆中取出最大元素作为下一个扩展结点。 如果此时不存在下一个扩展结点，如此问题无可行解。 如果下一个扩展结点是叶结点，即子集树中第n+1层结点，如此它相对应的可行解为最优解，算法完毕。关键代码/定义集装箱的个数 const int N = 4; /*= 定义HeapNode类来存储最大堆中顶点的信息。 =*/template<class Type> class HeapNode template<class T> friend void AddLiveNode(MaxHeap<HeapNode<T> >& H,bbnode *E,T wt,bool ch,int lev); template<class Ty> friend Ty MaxLoading(Ty w,Ty c,int n,int bestx); public: operator Type() constreturn uweight; private: bbnode *ptr; /指向活节点在子集树中相应节点的指针 Type uweight; /活节点优先级(上界) int level; /活节点在子集树中所处的层序号 ; /*=定义bbnode类来定义子集空间树中的结点类型。=*/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; /左儿子节点标识 ; /*= AddLiveNode函数将新产生的活节点参加到子集树中,并将这个新结点插入到表示活结点优先队列的最大堆中。=*/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;/将结点N插入到最大堆中 H.Insert(N); /*=MaxLoading函数为使用优先队列求装载问题,返回最优装载重量,bestx返回最优解。 活结点x在最优队列中的优先级定义为从根结点到结点x的路径所相应的载重量再加上剩余集装箱的总量之和。优先队列中优先级最大的活结点成为下一个扩展结点。优先队列中活结点x的优先级为x.uweight。以结点x为根的子树中所有结点相应的路径的载重量不超过x.uweight。子集树中叶结点相应载重量与其优先级一样。因此，一旦一个叶结点成为当前扩展结点，如此可以断言该叶结点所相应的解为即为最优解，终止算法。 =*/template<class Type> Type MaxLoading(Type w,Type c,int n,int bestx) /定义最大的容量为1000 MaxHeap<HeapNode<Type> > H(1000); /定义剩余容量数组 Type *r = new Typen+1; rn = 0; for(int j=n-1; j>0; j-) rj = rj+1 + wj+1; /初始化 int i = 1;/当前扩展节点所处的层 bbnode *E = 0;/当前扩展节点 Type Ew = 0; /扩展节点所相应的载重量 /搜索子集空间树 while(i!=n+1)/非叶子节点 /检查当前扩展节点的儿子节点 if(Ew+wi<=c) /将结点参加最大堆中 AddLiveNode(H,E,Ew+wi+ri,true,i+1); /右儿子节点 AddLiveNode(H,E,Ew+ri,false,i+1); /取下一扩展节点 HeapNode<Type> N; /从最大堆中取出最大值 H.DeleteMax(N); /赋值 i = N.level; E = N.ptr; Ew = N.uweight - ri-1; /构造当前最优解 for(int j=n; j>0; j-) bestxj = E->LChild; E = E->parent; return Ew; 测试结果1. 当所有物品无法装入两艘轮船时结果如下所示：输出时间。输出是否可以将集装箱全部装上两艘轮船。输出所有装上第1艘轮船的集装箱的重量。1代表对应集装箱装上轮船，0代表对应集装箱不装上轮船输出待装上轮船的集装箱的重量。输出第2艘船的载重量输出第1艘船的载重量没有装入第1艘轮船的集装箱的重量为10，这里第2艘轮船的载重量为8，小于10，所以无法将剩余集装箱装上第2艘轮船，所以不可以将集装箱全部装入两艘轮船。2. 当所有物品可以装入两艘轮船时结果如下所示：没有装入第1艘轮船的集装箱的重量为10，这里第2艘轮船的载重量为80，大于10，所以可以将剩余集装箱装上第2艘轮船，所以可以将集装箱全部装入两艘轮船。使用分支限界法求装在问题时间很短，可以看到算法的性质很好。实验心得 与旅行售货员问题比拟起来，这个装载问题要好理解很多，因为这个算法的解空间是子集树，而不是排列树，与0-1背包问题非常类似，所以很多问题的求解都是相似的，弄懂一个问题，会编写其中一个问题的代码，其他问题也就迎刃而解了。分支限界法的算法思想也不算非常难。但是我认为分支限界法有一个不好的地方，就是需要另外编写代码来实现最大最小堆，这个代码的编写我感觉是非常繁琐的，稍不小心马虎了，堆得实现就会出现问题。不过还好，编写了这么多的分支界限法的代码，可以通用堆的实现，只要将其定义为.h头文件格式就可以了。 到这里其实就做完了所有的算法设计与分析课程的实验。刚开始分治法的实验的时候还感觉蛮轻松的。但是越到后面感觉越难。要想当年，我们数据结构课程，写Dijkstra算法，与最大最小堆有关的算法的时候，三个人一组都是勉勉强强才能搞定。到了现在，一个代码，自己也可以敲出来，虽然中间还是会遇到很多的问题，但是还好坚持一下就都能解决了。果然一个算法还是要反复学习的，每次学习都会有不同的感受，每多学习一次，就能理解得更加透彻。这也说明，算法分析与设计这门的学习还是很有用处的，使我对算法的掌握更进一步。但是这算法分析与设计课程学习的算法比数据结构课程学习的算法要深入很多，要对一些算法完全掌握，还需要我平时多下功夫。 编写这个代码，主要是为了熟悉最优装载算法的不同实现，就我自己来说，我还是更加偏爱贪心算法，可是贪心算法，因为贪心算法的实现真的是非常非常的简单。回溯法和分支限界法比贪心算法要难理解一点，但是好好研究一下，也是可以看懂的。我觉得算法课程的一大难点就是，算法思想都懂，但是不会实现具体问题。这也告诫我，在平时的学习中，需要多进展实践，在实践中掌握知识。 通过这次实验，编写了分支限界法求解装载问题的代码，使我对分支限界法的思想更加熟悉，对装载问题的问题描述与解题思路更加熟悉。相信在以后的学习工作中一定可以熟练使用分支限界法，可以使用多种方法求解装载问题。实验得分助教签名附录：完整代码#include "MaxHeap.h" #include <iostream>#include<cstdlib>#include<time.h>#include<iomanip>#include<stdlib.h> using namespace std; /定义集装箱的个数 const int N = 4; class bbnode; /*= 定义HeapNode类来存储最大堆中顶点的信息。 =*/ template<class Type> class HeapNode template<class T> friend void AddLiveNode(MaxHeap<HeapNode<T> >& H,bbnode *E,T wt,bool ch,int lev); template<class Ty> friend Ty MaxLoading(Ty w,Ty c,int n,int bestx); public: operator Type() constreturn uweight; private: bbnode *ptr; /指向活节点在子集树中相应节点的指针 Type uweight; /活节点优先级(上界) int level; /活节点在子集树中所处的层序号 ; /*= 定义bbnode类来定义子集空间树中的结点类型。=*/ 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; /左儿子节点标识 ; /*= AddLiveNode函数将新产生的活节点参加到子集树中,并将这个新结点插入到表示活结点优先队列的最大堆中。=*/ 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;/将结点N插入到最大堆中 H.Insert(N); /*=MaxLoading函数为使用优先队列求装载问题,返回最优装载重量,bestx返回最优解。 活结点x在最优队列中的优先级定义为从根结点到结点x的路径所相应的载重量再加上剩余集装箱的总量之和。优先队列中优先级最大的活结点成为下一个扩展结点。优先队列中活结点x的优先级为x.uweight。以结点x为根的子树中所有结点相应的路径的载重量不超过x.uweight。子集树中叶结点相应载重量与其优先级一样。因此，一旦一个叶结点成为当前扩展结点，如此可以断言该叶结点所相应的解为即为最优解，终止算法。 =*/ template<class Type> Type MaxLoading(Type w,Type c,int n,int bestx) /定义最大的容量为1000 MaxHeap<HeapNode<Type> > H(1000); /定义剩余容量数组 Type *r = new Typen+1; rn = 0; for(int j=n-1; j>0; j-) rj = rj+1 + wj+1; /初始化 int i = 1;/当前扩展节点所处的层 bbnode *E = 0;/当前扩展节点 Type Ew = 0; /扩展节点所相应的载重量 /搜索子集空间树 while(i!=n+1)/非叶子节点 /检查当前扩展节点的儿子节点 if(Ew+wi<=c) /将结点参加最大堆中 AddLiveNode(H,E,Ew+wi+ri,true,i+1); /右儿子节点 AddLiveNode(H,E,Ew+ri,false,i+1); /取下一扩展节点 HeapNode<Type> N; /从最大堆中取出最大值 H.DeleteMax(N); /赋值 i = N.level; E = N.ptr; Ew = N.uweight - ri-1; /构造当前最优解 for(int j=n; j>0; j-) bestxj = E->LChild; E = E->parent; return Ew; /*= main函数是主函数。 实现输入输出，分别输出两艘轮船的载重量，输出各个集装箱的重量。输出集装箱是否装上第一艘轮船，输出是否可以将集装箱全部装入两艘轮船。 这里的各个集装箱的重量和两艘轮船的载重量是在主函数中给的。 =*/ int main() float c1 = 70; float c2 = 80; float w = 0,20,10,26,15;/下标从1开始 float sum_weight=0; int xN+1; float bestw; /输出第1艘轮船的重量 cout<<"第1艘轮船载重为："<<c1<<endl<<endl; /输出第2艘轮船的重量 cout<<"第2艘轮船载重为："<<c2<<endl<<endl; /输出待装上轮船的物品的重量 cout<<"待装集装箱的重量分别为："<<endl; for(int i=1; i<=N; i+) cout<<wi<<" " cout<<endl;cout<<endl; /开始计时 clock_t start,end,over;start=clock();end=clock();over=end-start;start=clock();/调用函数 bestw = MaxLoading(w,c1,N,x); /完毕计时 end=clock();/输出是否选择装上第一艘船的集装箱 cout<<"分支限界选择结果为:"<<endl; for(int i=1; i<=4; i+) cout<<xi<<" " sum_weight+=wi; cout<<endl;cout<<endl; /输出第一艘轮船的最优装载重量 cout<<"第一艘最优装载重量为："<<bestw<<endl<<endl; /输出是否可以将所有的集装箱装上两艘轮船 if(sum_weight-bestw<=c2)cout<<"可以将集装箱全部装入两艘轮船。"<<endl;elsecout<<"不可以将集装箱全部装入两艘轮船。"<<endl; /输出时间 printf("nThe time is %6.3fn",(double)(end-start-over)/CLK_TCK); return 0; 最大堆的实现如下所示：#include<iostream>using namespace std;template<class T> class MaxHeap public: MaxHeap(int MaxHeapSize = 10); MaxHeap() delete heap; int Size() const return CurrentSize; T Max() /查 if (CurrentSize) return heap1; MaxHeap<T>& Insert(const T& x); /增 MaxHeap<T>& DeleteMax(T& x); /删 void Initialize(T a, int size, int ArraySize); private: int CurrentSize, MaxSize; T *heap; / element array ; template<class T> MaxHeap<T>:MaxHeap(int MaxHeapSize) / Max heap constructor. MaxSize = MaxHeapSize; heap = new TMaxSize+1; CurrentSize = 0; template<class T> MaxHeap<T>& MaxHeap<T>:Insert(const T& x) / Insert x into the max heap. if (CurrentSize = MaxSize) cout<<"no space!"<<endl; return *this; / 寻找新元素x的位置 / i初始为新叶节点的位置，逐层向上，寻找最终位置 int i = +CurrentSize; while (i != 1 && x > heapi/2) / i不是根节点，且其值大于父节点的值，需要继续调整 heapi = heapi/2; / 父节点下降 i /= 2; / 继续向上，搜寻正确位置 heapi = x; return *this; template<class T> MaxHeap<T>& MaxHeap<T>:DeleteMax(T& x) / Set x to max element and delete max element from heap. / check if heap is empty if (CurrentSize = 0) cout<<"Empty heap!"<<endl; return *this; x = heap1; / 删除最大元素 / 重整堆 T y = heapCurrentSize-; / 取最后一个节点，从根开始重整 / find place for y starting at root int i = 1, / current node of heap ci = 2; / child of i while (ci <= CurrentSize) / 使ci指向i的两个孩子中较大者 if (ci < CurrentSize && heapci < heapci+1) ci+; / y的值大于等于孩子节点吗？ if (y >= heapci) break; / 是，i就是y的正确位置，退出 / 否，需要继续向下，重整堆 heapi = heapci; / 大于父节点的孩子节点上升 i = ci; / 向下一层，继续搜索正确位置 ci *= 2; heapi = y; return *this; template<class T> void MaxHeap<T>:Initialize(T a, int size,int ArraySize) / Initialize max heap to array a. delete heap; heap = a; CurrentSize = size; MaxSize = ArraySize; / 从最后一个内部节点开始，一直到根，对每个子树进展堆重整 for (int i = CurrentSize/2; i >= 1; i-) T y = heapi; / 子树根节点元素 / find place to put y int c = 2*i; / parent of c is target / location for y while (c <= CurrentSize) / heapc should be larger sibling if (c < CurrentSize && heapc < heapc+1) c+; / can we put y in heapc/2? if (y >= heapc) break; / yes / no heapc/2 = heapc; / move child up c *= 2; / move down a level heapc/2 = y;