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

算法分析与设计实验报告第 X次实验姓名刘悦学号201308080112班级物联1301班时间12.26上午地点工训楼C栋309 实验名称分支限界法求装载问题实验目的通过上机实验，掌握分支限界算法的思想，利用分支限界算法求装载问题并实现。实验原理活结点x在最优队列中的优先级定义为从根结点到结点x的路径所相应的载重量再加上剩余集装箱的总量之和。优先队列中优先级最大的活结点成为下一个扩展结点。优先队列中活结点x的优先级为x.uweight。以结点x为根的子树中所有结点相应的路径的载重量不超过x.uweight。子集树中叶结点相应载重量与其优先级相同。因此，一旦一个叶结点成为当前扩展结点，则可以断言该叶结点所相应的解为即为最优解，终止算法。这里选用在有哪些信誉好的足球投注网站进程中保存当前已构造出的部分解空间树，在算法确定课达到最优解的叶结点时，就可以在解空间树中从该叶结点开始向根结点回溯，构造出相应的最优解。实验步骤算法开始创建一个最大堆，表示活结点优先队列。算法第一个扩展结点是子集树中根结点。开始子集树的根结点是扩展结点。循环产生当前扩展结点的左右儿子结点。如果当前扩展结点的左儿子结点是可行结点，即它所相应的重量为超过轮船的载重量，则将它加入到子集树的第i+1层上，并插入最大堆。扩展结点的右儿子结点总是可行的，故直接插入子集树的最大堆中。接着从最大堆中取出最大元素作为下一个扩展结点。如果此时不存在下一个扩展结点，则问题无可行解。如果下一个扩展结点是叶结点，即子集树中第n+1层结点，则它相对应的可行解为最优解，算法结束。关键代码//定义集装箱的个数 const int N = 4; /*================================================================= 定义HeapNode类来存储最大堆中顶点的信息。 =================================================================*/templateclass Type class HeapNode { templateclass T friend void AddLiveNode(MaxHeapHeapNodeT H,bbnode *E,T wt,bool ch,int lev); templateclass Ty friend Ty MaxLoading(Ty w[],Ty c,int n,int bestx[]); public: operator Type() const{return uweight;} private: bbnode *ptr; //指向活节点在子集树中相应节点的指针 Type uweight; //活节点优先级(上界) int level; //活节点在子集树中所处的层序号 }; /*=================================================================定义bbnode类来定义子集空间树中的结点类型。=================================================================*/class bbnode { templateclass Type friend void AddLiveNode(MaxHeapHeapNodeType H,bbnode *E,Type wt,bool ch,int lev); templateclass Type friend Type MaxLoading(Type w[],Type c,int n,int bestx[]); friend class AdjacencyGraph; private: bbnode *parent; //指向父节点的指针 bool LChild; //左儿子节点标识 }; /*================================================================= AddLiveNode函数将新产生的活节点加入到子集树中,并将这个新结点插入到表示活结点优先队列的最大堆中。=================================================================*/templateclass