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

1、算法分析与设计实验报告第 X 次实验姓名刘悦学号201308080112班级物联1301班时间12.26上午地点工训楼C栋309 实验名称分支限界法求装载问题实验目的通过上机实验，掌握分支限界算法的思想，利用分支限界算法求装载问题并实现。实验原理活结点x在最优队列中的优先级定义为从根结点到结点x的路径所相应的载重量再加上剩余集装箱的总量之和。优先队列中优先级最大的活结点成为下一个扩展结点。优先队列中活结点x的优先级为x.uweight。以结点x为根的子树中所有结点相应的路径的载重量不超过x.uweight。子集树中叶结点相应载重量与其优先级相同。因此，一旦一个叶结点成为当前扩展结点，则可以断言

2、该叶结点所相应的解为即为最优解，终止算法。这里选用在搜索进程中保存当前已构造出的部分解空间树，在算法确定课达到最优解的叶结点时，就可以在解空间树中从该叶结点开始向根结点回溯，构造出相应的最优解。实验步骤 算法开始创建一个最大堆，表示活结点优先队列。 算法第一个扩展结点是子集树中根结点。 开始子集树的根结点是扩展结点。循环产生当前扩展结点的左右儿子结点。 如果当前扩展结点的左儿子结点是可行结点，即它所相应的重量为超过轮船的载重量，则将它加入到子集树的第i+1层上，并插入最大堆。 扩展结点的右儿子结点总是可行的，故直接插入子集树的最大堆中。 接着从最大堆中取出最大元素作为下一个扩展结点。 如果此时

3、不存在下一个扩展结点，则问题无可行解。 如果下一个扩展结点是叶结点，即子集树中第n+1层结点，则它相对应的可行解为最优解，算法结束。关键代码/定义集装箱的个数 const int N = 4; /*= 定义HeapNode类来存储最大堆中顶点的信息。 =*/ template class HeapNode template friend void AddLiveNode(MaxHeapHeapNode & H,bbnode *E,T wt,bool ch,int lev); template friend Ty MaxLoading(Ty w,Ty c,int n,int bestx); pu

4、blic: operator Type() constreturn uweight; private: bbnode *ptr; /指向活节点在子集树中相应节点的指针 Type uweight; /活节点优先级(上界) int level; /活节点在子集树中所处的层序号 ; /*=定义bbnode类来定义子集空间树中的结点类型。=*/ class bbnode template friend void AddLiveNode(MaxHeapHeapNode & H,bbnode *E,Type wt,bool ch,int lev); template friend Type MaxLoad

5、ing(Type w,Type c,int n,int bestx); friend class AdjacencyGraph; private: bbnode *parent; /指向父节点的指针 bool LChild; /左儿子节点标识 ; /*= AddLiveNode函数将新产生的活节点加入到子集树中,并将这个新结点插入到表示活结点优先队列的最大堆中。=*/ template void AddLiveNode(MaxHeapHeapNode & H,bbnode *E,Type wt,bool ch,int lev) /子集树结点赋值 bbnode *b = new bbnode;

6、b-parent = E; b-LChild = ch; HeapNode N; /最大堆结点赋值 N.uweight = wt; N.level = lev; N.ptr = b;/将结点N插入到最大堆中 H.Insert(N); /*=MaxLoading函数为使用优先队列求装载问题,返回最优装载重量,bestx返回最优解。 活结点x在最优队列中的优先级定义为从根结点到结点x的路径所相应的载重量再加上剩余集装箱的总量之和。优先队列中优先级最大的活结点成为下一个扩展结点。优先队列中活结点x的优先级为x.uweight。以结点x为根的子树中所有结点相应的路径的载重量不超过x.uweight。子

7、集树中叶结点相应载重量与其优先级相同。因此，一旦一个叶结点成为当前扩展结点，则可以断言该叶结点所相应的解为即为最优解，终止算法。 =*/ template Type MaxLoading(Type w,Type c,int n,int bestx) /定义最大的容量为1000 MaxHeapHeapNode H(1000); /定义剩余容量数组 Type *r = new Typen+1; rn = 0; for(int j=n-1; j0; j-) rj = rj+1 + wj+1; /初始化 int i = 1;/当前扩展节点所处的层 bbnode *E = 0;/当前扩展节点 Type

8、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 N; /从最大堆中取出最大值 H.DeleteMax(N); /赋值 i = N.level; E = N.ptr; Ew = N.uweight - ri-1; /构造当前最优解 for(int j=n; j0; j-) bestx

9、j = E-LChild; E = E-parent; return Ew; 测试结果1. 当所有物品无法装入两艘轮船时结果如下所示：输出时间。输出是否可以将集装箱全部装上两艘轮船。输出所有装上第1艘轮船的集装箱的重量。1代表对应集装箱装上轮船，0代表对应集装箱不装上轮船输出待装上轮船的集装箱的重量。输出第2艘船的载重量输出第1艘船的载重量没有装入第1艘轮船的集装箱的重量为10，这里第2艘轮船的载重量为8，小于10，所以无法将剩余集装箱装上第2艘轮船，所以不可以将集装箱全部装入两艘轮船。2. 当所有物品可以装入两艘轮船时结果如下所示：没有装入第1艘轮船的集装箱的重量为10，这里第2艘轮船的载重

10、量为80，大于10，所以可以将剩余集装箱装上第2艘轮船，所以可以将集装箱全部装入两艘轮船。使用分支限界法求装在问题时间很短，可以看到算法的性质很好。实验心得 与旅行售货员问题比较起来，这个装载问题要好理解很多，因为这个算法的解空间是子集树，而不是排列树，与0-1背包问题非常类似，所以很多问题的求解都是相似的，弄懂一个问题，会编写其中一个问题的代码，其他问题也就迎刃而解了。分支限界法的算法思想也不算非常难。但是我认为分支限界法有一个不好的地方，就是需要另外编写代码来实现最大最小堆，这个代码的编写我感觉是非常繁琐的，稍不小心马虎了，堆得实现就会出现问题。不过还好，编写了这么多的分支界限法的代码，可

11、以通用堆的实现，只要将其定义为.h头文件格式就可以了。 到这里其实就做完了所有的算法设计与分析课程的实验。刚开始分治法的实验的时候还感觉蛮轻松的。但是越到后面感觉越难。要想当年，我们数据结构课程，写Dijkstra算法，与最大最小堆有关的算法的时候，三个人一组都是勉勉强强才能搞定。到了现在，一个代码，自己也可以敲出来，虽然中间还是会遇到很多的问题，但是还好坚持一下就都能解决了。果然一个算法还是要反复学习的，每次学习都会有不同的感受，每多学习一次，就能理解得更加透彻。这也说明，算法分析与设计这门的学习还是很有用处的，使我对算法的掌握更进一步。但是这算法分析与设计课程学习的算法比数据结构课程学习的

12、算法要深入很多，要对一些算法完全掌握，还需要我平时多下功夫。 编写这个代码，主要是为了熟悉最优装载算法的不同实现，就我自己来说，我还是更加偏爱贪心算法，可是贪心算法，因为贪心算法的实现真的是非常非常的简单。回溯法和分支限界法比贪心算法要难理解一点，但是好好研究一下，也是可以看懂的。我觉得算法课程的一大难点就是，算法思想都懂，但是不会实现具体问题。这也告诫我，在平时的学习中，需要多进行实践，在实践中掌握知识。 通过这次实验，编写了分支限界法求解装载问题的代码，使我对分支限界法的思想更加熟悉，对装载问题的问题描述与解题思路更加熟悉。相信在以后的学习工作中一定可以熟练使用分支限界法，可以使用多种方法

13、求解装载问题。实验得分助教签名附录：完整代码#include MaxHeap.h #include #include#include#include#include using namespace std; /定义集装箱的个数 const int N = 4; class bbnode; /*= 定义HeapNode类来存储最大堆中顶点的信息。 =*/ template class HeapNode template friend void AddLiveNode(MaxHeapHeapNode & H,bbnode *E,T wt,bool ch,int lev); template fri

14、end 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 friend void AddLiveNode(MaxHeapHeapNode & H,bbnode *E,Type

15、wt,bool ch,int lev); template friend Type MaxLoading(Type w,Type c,int n,int bestx); friend class AdjacencyGraph; private: bbnode *parent; /指向父节点的指针 bool LChild; /左儿子节点标识 ; /*= AddLiveNode函数将新产生的活节点加入到子集树中,并将这个新结点插入到表示活结点优先队列的最大堆中。=*/ template void AddLiveNode(MaxHeapHeapNode & H,bbnode *E,Type wt,b

16、ool ch,int lev) /子集树结点赋值 bbnode *b = new bbnode; b-parent = E; b-LChild = ch; HeapNode N; /最大堆结点赋值 N.uweight = wt; N.level = lev; N.ptr = b;/将结点N插入到最大堆中 H.Insert(N); /*=MaxLoading函数为使用优先队列求装载问题,返回最优装载重量,bestx返回最优解。 活结点x在最优队列中的优先级定义为从根结点到结点x的路径所相应的载重量再加上剩余集装箱的总量之和。优先队列中优先级最大的活结点成为下一个扩展结点。优先队列中活结点x的优先

17、级为x.uweight。以结点x为根的子树中所有结点相应的路径的载重量不超过x.uweight。子集树中叶结点相应载重量与其优先级相同。因此，一旦一个叶结点成为当前扩展结点，则可以断言该叶结点所相应的解为即为最优解，终止算法。 =*/ template Type MaxLoading(Type w,Type c,int n,int bestx) /定义最大的容量为1000 MaxHeapHeapNode H(1000); /定义剩余容量数组 Type *r = new Typen+1; rn = 0; for(int j=n-1; j0; j-) rj = rj+1 + wj+1; /初始化

18、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 N; /从最大堆中取出最大值 H.DeleteMax(N); /赋值 i = N.level; E = N.ptr; Ew = N.uw

19、eight - ri-1; /构造当前最优解 for(int j=n; j0; 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

20、 xN+1; float bestw; /输出第1艘轮船的重量 cout第1艘轮船载重为：c1endlendl; /输出第2艘轮船的重量 cout第2艘轮船载重为：c2endlendl; /输出待装上轮船的物品的重量 cout待装集装箱的重量分别为：endl; for(int i=1; i=N; i+) coutwi ; coutendl;coutendl; /开始计时 clock_t start,end,over;start=clock();end=clock();over=end-start;start=clock();/调用函数 bestw = MaxLoading(w,c1,N,x);

21、 /结束计时 end=clock();/输出是否选择装上第一艘船的集装箱 cout分支限界选择结果为:endl; for(int i=1; i=4; i+) coutxi ; sum_weight+=wi; coutendl;coutendl; /输出第一艘轮船的最优装载重量 cout第一艘最优装载重量为：bestwendlendl; /输出是否可以将所有的集装箱装上两艘轮船 if(sum_weight-bestw=c2)cout可以将集装箱全部装入两艘轮船。endl;elsecout不可以将集装箱全部装入两艘轮船。endl; /输出时间 printf(nThe time is %6.3fn,

22、(double)(end-start-over)/CLK_TCK); return 0; 最大堆的实现如下所示：#includeusing namespace std;template class MaxHeap public: MaxHeap(int MaxHeapSize = 10); MaxHeap() delete heap; int Size() const return CurrentSize; T Max() /查 if (CurrentSize) return heap1; MaxHeap& Insert(const T& x); /增 MaxHeap& DeleteMax(T

23、& x); /删 void Initialize(T a, int size, int ArraySize); private: int CurrentSize, MaxSize; T *heap; / element array ; template MaxHeap:MaxHeap(int MaxHeapSize) / Max heap constructor. MaxSize = MaxHeapSize; heap = new TMaxSize+1; CurrentSize = 0; template MaxHeap& MaxHeap:Insert(const T& x) / Insert

24、 x into the max heap. if (CurrentSize = MaxSize) coutno space! heapi/2) / i不是根节点，且其值大于父节点的值，需要继续调整 heapi = heapi/2; / 父节点下降 i /= 2; / 继续向上，搜寻正确位置 heapi = x; return *this; template MaxHeap& MaxHeap:DeleteMax(T& x) / Set x to max element and delete max element from heap. / check if heap is empty if (CurrentSize = 0) coutEmpty heap!endl; return *this; x = heap1; / 删除最大元素 / 重整堆 T y = heapCurrentSize-; / 取最后一个节点，从根开始重整