《算法分支限界法教学教案》由会员分享，可在线阅读，更多相关《算法分支限界法教学教案（20页珍藏版）》请在金锄头文库上搜索。
1、第六章第六章 分支限界法分支限界法1学习要点1.1学习要点学习要点理解分支限界法的剪枝搜索策略。掌握分支限界法的算法框架（1）队列式(FIFO)分支限界法（2）优先队列式分支限界法 通过应用范例学习分支限界法的设计策略。（1）单源最短路径问题（2）装载问题；（4）0-1 背包问题；（8）批处理作业调度问题2分支限界法的基本思想2.1分支限界法分支限界法描述采用广度优先产生状态空间树的结点，并使用剪枝函数的方法称为分支限界法。所谓“分支”是采用广度优先的策略，依次生成扩展结点的所有分支（即：儿子结点） 。所谓“限界”是在结点扩展过程中，计算结点的上界（或下界） ，边搜索边减掉搜索树的某些分支，从
2、而提高搜索效率。原理按照广度优先的原则，一个活结点一旦成为扩展结点（E-结点）R 后，算法将依次生成它的全部孩子结点，将那些导致不可行解或导致非最优解的儿子舍弃，其余儿子加入活结点表中。然后，从活结点表中取出一个结点作为当前扩展结点。重复上述结点扩展过程，直至找到问题的解或判定无解为止。2.2分支限界法与回溯法分支限界法与回溯法求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先的方式搜索解空间树。分支限界
3、法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。2.3常见的两种分支限界法常见的两种分支限界法队列式(FIFO)分支限界法按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。搜索策略：一开始，根结点是唯一的活结点，根结点入队。从活结点队中取出根结点后，作
4、为当前扩展结点。对当前扩展结点，先从左到右地产生它的所有儿子，用约束条件检查，把所有满足约束函数的儿子加入活结点队列中。再从活结点表中取出队首结点（队中最先进来的结点）为当前扩展结点，直到找到一个解或活结点队列为空为止。队列式分支限界法搜索解空间树的方式与解空间树的广度优先遍历算法极为相似，唯一的不同之处是队列式分支限界法不搜索以不可行结点为根的子树。优先队列式分支限界法基本思想：为了加速搜索的进程，应采用有效的方式选择活结点进行扩展。按照优先队列中规定的优先级选取优先级最高的结点成为当前扩展结点。搜索策略：对每一活结点计算一个优先级（某些信息的函数值） ，并根据这些优先级；从当前活结点表中优
5、先选择一个优先级最高（最有利）的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解。再从活结点表中下一个优先级别最高的结点为当前扩展结点，直到找到一个解或活结点队列为空为止。30 -1 背包问题3.1算法思想算法思想首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列。在优先队列分支限界法中，节点的优先级由已装袋的物品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值和。templateTypep Knap:Bound(int i) /计算节点所相应价值的上界Typew cleft = c-cw; /剩余容量高Typep b = cp; /
6、价值上界/以物品单位重量价值递减序装填剩余容量while(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 越界，所以直接进行剪枝，解空间树变成如下：可
7、扩展结点：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 活结
8、点队列：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 = b; b = temp;templatevoid BubbleSort(Type a,int n) /记录一次遍历中是否有元素的交换bool exchange;for(int i=0; ifriend Typep Knapsac
9、k(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
10、 i=1; i K;K.p = new Typepn+1;K.w = new Typewn+1;for(int i=1; iclass MaxHeap public:MaxHeap(int MaxHeapSize = 10);MaxHeap() delete heap; int Size() const return CurrentSize; T Max() if (CurrentSize = 0) return heap1;MaxHeapMaxHeapvoid Initialize(T a, int size, int ArraySize);private:int CurrentSize,
11、MaxSize;T *heap; / element array;templateMaxHeap:MaxHeap(int MaxHeapSize) MaxSize = MaxHeapSize;heap = new TMaxSize+1;CurrentSize = 0;templateMaxHeap / 父节点下降i /= 2; / 继续向上，搜寻正确位置heapi = x;return *this;templateMaxHeap / 是，i 就是 y 的正确位置，退出/ 否，需要继续向下，重整堆heapi = heapci; / 大于父节点的孩子节点上升i = ci; / 向下一层，继续搜索正
12、确位置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 yint c = 2*i; / parent of c is targe
13、t location for ywhile (c = heapc) break; / yes/ noheapc/2 = heapc; / move child upc *= 2; / move down a levelheapc/2 = y;/-class bbnode public:templatefriend Typep Knapsack(Typep p,Typew w,Typew c,int n, int bestx);bbnode * parent; /指向父节点的指针bool LChild; /左儿子节点标识;templateclass HeapNode public:operato
14、r Typep() const return uprofit; Typep uprofit, /节点的价值上界profit; /节点所相应的价值Typew weight; /节点所相应的重量int level; /活节点在子集树中所处的层序号bbnode *ptr; /指向活节点在子集中相应节点的指针;/-templateclass Knap public:Typep MaxKnapsack();MaxHeap *H;Typep Bound(int i);void AddLiveNode(Typep up,Typep cp,Typew cw,bool ch,int lev);bbnode *E; /指向扩展节点的指针Typew c; /背包容量int n; /物品数Typew
