算法分支限界法教学教案.doc

第六章 分支限界法1 学习要点1.1 学习要点理解分支限界法的剪枝搜索策略。掌握分支限界法的算法框架（1）队列式(FIFO)分支限界法（2）优先队列式分支限界法 通过应用范例学习分支限界法的设计策略。（1）单源最短路径问题（2）装载问题；（4）0-1背包问题；（8）批处理作业调度问题2 分支限界法的基本思想2.1 分支限界法描述采用广度优先产生状态空间树的结点，并使用剪枝函数的方法称为分支限界法。所谓“分支”是采用广度优先的策略，依次生成扩展结点的所有分支（即：儿子结点）。所谓“限界”是在结点扩展过程中，计算结点的上界（或下界），边搜索边减掉搜索树的某些分支，从而提高搜索效率。原理按照广度优先的原则，一个活结点一旦成为扩展结点（E-结点）R后，算法将依次生成它的全部孩子结点，将那些导致不可行解或导致非最优解的儿子舍弃，其余儿子加入活结点表中。然后，从活结点表中取出一个结点作为当前扩展结点。重复上述结点扩展过程，直至找到问题的解或判定无解为止。2.2 分支限界法与回溯法求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先的方式搜索解空间树。分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。2.3 常见的两种分支限界法队列式(FIFO)分支限界法 按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。搜索策略：一开始，根结点是唯一的活结点，根结点入队。从活结点队中取出根结点后，作为当前扩展结点。对当前扩展结点，先从左到右地产生它的所有儿子，用约束条件检查，把所有满足约束函数的儿子加入活结点队列中。再从活结点表中取出队首结点（队中最先进来的结点）为当前扩展结点，直到找到一个解或活结点队列为空为止。队列式分支限界法搜索解空间树的方式与解空间树的广度优先遍历算法极为相似，唯一的不同之处是队列式分支限界法不搜索以不可行结点为根的子树。优先队列式分支限界法 基本思想：为了加速搜索的进程，应采用有效的方式选择活结点进行扩展。按照优先队列中规定的优先级选取优先级最高的结点成为当前扩展结点。 搜索策略：对每一活结点计算一个优先级（某些信息的函数值），并根据这些优先级；从当前活结点表中优先选择一个优先级最高（最有利）的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解。再从活结点表中下一个优先级别最高的结点为当前扩展结点，直到找到一个解或活结点队列为空为止。3 0 -1背包问题3.1 算法思想首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列。在优先队列分支限界法中，节点的优先级由已装袋的物品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值和。templateTypep Knap:Bound(int i) /计算节点所相应价值的上界 Typew cleft = c-cw; /剩余容量高 Typep b = cp; /价值上界 /以物品单位重量价值递减序装填剩余容量 while(i=n & wi=cleft) cleft -= wi; b += pi; i+; /装填剩余容量装满背包 if(iAB,C【C，D（舍去），E】E，C【C，J（舍去），K】K，CF，GG，L，M【G，M（L，M已是叶节点）】GN，OO3.2 队列式(FIFO)算法示例解空间树如下图所示，1代表选择，0代表不选。分支限界法如下处理：可扩展结点：A 活结点队列：B，C选择路径 ： AW：0P：0可扩展结点：B； 活结点队列：C，D，E选择路径： A-BW：16P：45可扩展结点：C 活结点队列：D，E，F，G选择路径： A-CW：0 P：0如果扩展D，那么当前w = 31 30越界，所以直接进行剪枝，解空间树变成如下： 可扩展结点：E 活结点队列：F，G，J，K选择路径： A-B-EW：16P：45可扩展结点：F 活结点队列：G，J，K，L，M选择路径： A-C-FW：15P：25可扩展结点：G 活结点队列：J，K，L，M，N，O选择路径： A-C-GW：0P：0如果扩展J，那么当前w = 16+15=3130，所以对J剪枝，解空间树变为：可扩展结点：K 活结点队列：L，M，N，O选择路径： A-B-E-K W：16 P：45可扩展结点：L 活结点队列：M，N，O选择路径： A-C-F-L W：30 P：50可扩展结点：M 活结点队列：N，O选择路径： A-C-F-MW：15P：25可扩展结点：N 活结点队列：O选择路径： A-C-G-N W：15 P：25可扩展结点：O 活结点队列：NULL选择路径： A-C-G-OW：0P：0活结点队列为空，算法终止，从可行解中筛选出最佳解为（0,1,1），maxP = 50；3.3 完整代码#include using namespace std;/-template inline void Swap(Type &a,Type &b) Type temp = a; a = b; b = temp;templatevoid BubbleSort(Type a,int n) /记录一次遍历中是否有元素的交换 bool exchange; for(int i=0; in-1;i+) exchange = false ; for(int j=i+1; j=n-1; j+) if(aj=aj-1) Swap(aj,aj-1); exchange = true; /如果这次遍历没有元素的交换,那么排序结束 if(false = exchange) break ; /-class Object template friend Typep Knapsack(Typep p,Typew w,Typew c,int n, int bestx);public: int operator =a.d; private: int ID; float d; /单位重量价值;/-template class Knap;/返回最大价值，bestx返回最优解templateTypep Knapsack(Typep p,Typew w,Typew c,int n, int bestx) /初始化 Typew W = 0; /装包物品重量 Typep P = 0; /装包物品价值 /定义依单位重量价值排序的物品数组 Object *Q = new Objectn; for(int i=1; i=n; i+) /单位重量价值数组 Qi-1.ID = i; Qi-1.d = 1.0*pi/wi; P += pi; W += wi; if(W=c) return P;/所有物品装包 /依单位价值重量排序 BubbleSort(Q,n); /创建类Knap的数据成员 Knap K; K.p = new Typepn+1; K.w = new Typewn+1; for(int i=1; i=n; i+) K.pi = pQi-1.ID; K.wi = wQi-1.ID; K.cp = 0; K.cw = 0; K.c = c; K.n = n; /调用MaxKnapsack求问题的最优解 Typep bestp = K.MaxKnapsack(); for(int j=1; j=n; j+) bestxQj-1.ID = K.bestxj; delete Q; delete K.w; delete K.p; delete K.bestx; return bestp;templateclass MaxHeap public: MaxHeap(int MaxHeapSize = 10); MaxHeap() delete heap; int Size() const return CurrentSize; T Max() if (CurrentSize = 0) return heap1; MaxHeap& Insert(const T& x); MaxHeap& DeleteMax(T& x); void Initialize(T a, int size, int ArraySize);private: int CurrentSize, MaxSize; T *heap; / element array;templateMaxHeap:MaxHeap(int MaxHeapSize) MaxSize = MaxHeapSize; heap = new TMaxSize+1; CurrentSize = 0;templateMaxHeap& MaxHeap:Insert(const T& x) if(CurrentSize = MaxSize) coutno space! heapi/2) / i不是根节点，且其值大于父节点的值，需要继续调整 heapi = heapi/2; / 父节点下降 i /= 2; / 继续向上，搜寻正确位置 heapi = x; return *this;templateMaxHeap& 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-; / 取最后一个节点，从根开始重整 / 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(ciCurrentSize & heapci = heapci) break; / 是，i就是y的正确位置，退出 / 否，需要继续向下，重整堆 heapi = heapci; / 大于父节点的孩子节点上升 i = ci; / 向下一层，继续搜索正确位置 ci *= 2; heapi = y; return *this;templatevoid MaxHeap:Initialize(T a, int size,int ArraySize) 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) break; / yes / no heapc/2 = heapc; / move child up c *= 2; / move down a level heapc/2 = y; /-class bbnode public: template friend Typep Knapsack(Typep p,Typew w,Typew c,int n, int bestx); bbnode * parent; /指向父节点的指针 bool LChild; /左儿子节点标识;templateclass HeapNode public: operator Typep() const return uprofit; Typep uprofit, /节点的价值上界 profit; /节点所相应的价值 Typew weight; /节点所相应的重量 int level; /活节点在子集树中所处的层序号 bbnode *ptr; /指向活节点在子集中相应节点的指针;/-templateclass Knap public: Typep MaxKnapsack(); MaxHeapHeapNode *H; Typep Bound(int i); void AddLiveNode(Typep up,Typep cp,Typew cw,bool ch,int lev); bbnode *E; /指向扩展节点的指针 Typew c; /背包容量 int n; /物品数 Typew *w; /物品重量数组 Typep *p; /物品价值数组 Typew cw; /当前重量 Typep cp; /当前价值 int *bestx; /最优解;templateTypep Knap:Bound(int i) /计算节点所相应价值的上界 Typew cleft = c-cw; /剩余容量高 Typep b = cp; /价值上界 /以物品单位重量价值递减序装填剩余容量 while(i=n & wi=cleft) cleft -= wi; b += pi; i+; /装填剩余容量装满背包 if(i=n) b += pi/wi*cleft; return b;/将一个活节点插入到子集树和优先队列中templatevoid Knap:AddLiveNode(Typep up,Typep cp,Typew cw,bool ch,int lev) bbnode *b = new bbnode; b-parent = E; b-LChild = ch; HeapNode N; N.uprofit = up; N.profit = cp; N.weight = cw; N.level = lev; N.ptr = b; H-Insert(N);/优先队列式分支限界法，返回最大价值，bestx返回最优解templateTypep Knap:MaxKnapsack() H = new MaxHeapHeapNode (1000); /为bestx分配存储空间 bestx = new intn+1; /初始化 int i = 1; E = 0; cw = cp = 0; Typep bestp = 0;/当前最优值 Typep up = Bound(1); /价值上界 /搜索子集空间树 while(i!=n+1) /检查当前扩展节点的左儿子节点 Typew wt = cw + wi; if(wt bestp) bestp = cp + pi; AddLiveNode(up,cp+pi,cw+wi,true,i+1); up = Bound(i+1); /检查当前扩展节点的右儿子节点 if