矿大算法第6章 分支限界法.ppt

if (! E) { // 同层结点的尾部 if (Q.IsEmpty()) break; Q.Add(0); // 添加层结点尾部标志 Q.Delete(E) ; // 从队列Q中取下一个E结点 i++ ; // E-结点的层次 r -= w[i];} // E结点中余下的重量Ew=E- weight ; // 新的E结点的重量}//end of while// 沿着从bestE到根的路径构造x[n-1],…,x[1], 而x[n]已经在函数EnQueue中赋值。for (j = n - 1; j 0; j--) { bestx[j] = bestE-LChild; // bool型?int型 bestE = bestE-parent;}return bestw; } 4）优先队列式分支限界法 在对子集树进行最大收益分支限界有哪些信誉好的足球投注网站时，活结点列表是一个最大优先级队列，其中每个活结点x都有一个相应的重量上限（最大收益）。这个重量上限是结点x 相应的重量加上剩余货箱的总重量，所有的活结点按其重量上限的递减顺序变为E结点。 注意：如果结点x的重量上限是x.uweight，则在子树中不可能存在重量超过x.uweight 的结点。另外，当叶结点对应的重量等于它的重量上限时，可以得出结论：该叶结点所对应的解就是最优解，其他任何活结点都不会有更优的解，有哪些信誉好的足球投注网站终止。 上述策略可以用两种方法来实现： 最大优先级队列中的活结点都是互相独立的，因此每个活结点内部必须记录从子集树的根到此结点的路径。一旦找到了最优装载所对应的叶结点，就利用这些路径信息来计算x 值。 除了把结点加入最大优先队列之外，结点还必须放在另一个独立的树结构中，这个树结构用来表示所生成的子集树的一部分。当找到最大装载之后，就可以沿着路径从叶结点逐步返回到根，从而计算出x 值。 采用第二种方案：优先队列用HeapNode 类型的最大堆来表示。 templateclass Tclass HeapNode {public: operator T () const {return uweight;}private: bbnode *ptr; //指向活结点在子集树中位置 T uweight; // 活结点的重量上限 int level; //活结点所在子集树的层} ; 子集树中结点的类型是bbnode。结点按uweight值从最大堆中取出。 class bbnode {private: bbnode *parent; // 父结点指针 bool LChild; // 当是父结点的左孩子时取true} ; 函数AddLiveNode用于把bbnode类型的活结点加到子树中，并把HeapNode类型的活结点插入最大堆。AddLiveNode必须被定义为bbnode和HeapNode的友元。 templateclass T void AddLiveNode(MaxHeapHeapNodeT H, bbnode *E, T wt, bool ch, int lev) { // 向最大堆H中增添一个层为lev，上限重量为wt的活结点，新结点是E的儿子(左孩子：ch=true) bbnode *b = new bbnode; //新结点加入子集树 b-parent = E; b-LChild = ch; HeapNodeT N; //新结点插入队列中 N.uweight = wt; N.level = lev; N.ptr = b; H.Insert(N);} 函数MaxLoading的思路 定义一个容量为1000的最大堆。可以用它来解决优先队列中活结点数在任何时候都不超过1000的装箱问题。对于更大型的问题，需要一个容量更大的最大堆。如果改用基于指针的优先队列，则不必预置队列容量。 初始化剩余重量数组r。第i+1层的结点（即x[1~ i]的值都已确定）对应的剩余总重量为r[i]=Σw[j]，j从i+1到n。 变量E指向子集树中的当前E结点，Ew 是该结点对应的重量， i是它所在的层。 起初，根结点是E结点，因此取i=1, Ew=0。由于没有明确地存储根结点，因此E的初始值取为0。while 循环用于产生当前E结点的左、右孩子。如果左孩子是可行的（即没有超出容量），则将它加入到子集树中并作为一个第i+1层结点加入最大堆中。可行结点的右孩子总是可行的，它总被加入子树及最大堆中。在完成添加操作后，接着从最大堆中取出下一个E结点。如果没有下一个E结点，则不存在可行的解。如果下