第6章 分支限界法VIP免费

第6章分枝-限界法学习要点理解分支限界法的剪枝搜索策略。掌握分支限界法的算法框架（1）队列式(FIFO)分支限界法（2）优先队列式分支限界法通过应用范例学习分支限界法的设计策略。（1）单源最短路径问题（2）装载问题；（3）布线问题（4）0-1背包问题；（5）最大团问题；（6）旅行售货员问题（7）电路板排列问题（8）批处理作业调度问题6.1分支限界法的基本思想分支限界法与回溯法（1）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。（2）搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。6.1分支限界法的基本思想分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。6.1分支限界法的基本思想两类常用的方法选择下一个E-结点：（1）先进先出(FIFO)：从活结点表中取出结点的顺序与加入结点的顺序相同。后进先出(LIFO)：从活结点表中取出结点的顺序与加入结点的顺序相反。（2）优先队列式分支限界法按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。堆堆((HeapHeap))优先级队列优先级队列每次出队列的是优先权最高的元素每次出队列的是优先权最高的元素优先级队列支持以下操作：优先级队列支持以下操作：找出一个具有最高优先级的元素找出一个具有最高优先级的元素删除一个具有最高优先级的元素删除一个具有最高优先级的元素添加一个元素到集合中添加一个元素到集合中完全二叉树完全二叉树数组表示数组表示KKiiKK22ii+1+1&&KKiiKK22ii+2+2完全二叉树完全二叉树数组表示数组表示KKiiKK22ii+1+1&&KKiiKK22ii+2+2堆的定义堆的定义0909878778784545656531315323235317179176523457887533187785345659311723自下向上逐步调整为最小堆自下向上逐步调整为最小堆将一组用数组存放的任意数据调整成堆将一组用数组存放的任意数据调整成堆5353171778780923456587i0923456587i5317782345658795317789456587235353171778780923456587i0923456587i5317659457887235396517457887235353171778780923456587i0923456587i095396517457887235353171778780923456587i0923456587i1791765234578875353171778780923456587i0923456587j11在堆中插入新元素1153j1123i最小堆的向上调整最小堆的向上调整917652345788753115317117878094565870917456587j115323i2317ji911651745788753235311782331456587在堆中删除根元素0953117823314565870953117809314565872323116531457887535323781131456587在堆中删除根元素0953237811314565871123653145788753例1：n=3时的0-1背包问题，w=[20,15,15]p=[40,25,25]c=30E-结点和活结点死结点FIFO队列CBXX20403050152515250CECGFEGFG例1：n=3时的0-1背包问题，w=[20,15,15]p=[40,25,25]c=30E-结点和活结点死结点LIFO队列BCXX20403050152515250BBFGBFBE例1：n=3时的0-1背包问题，w=[20,15,15]p=[40,25,25]c=30E-结点和活结点死结点优先队列20403050152515250XXCBCECGFG例2：旅行商问题1423301020654旅行线路(1,2,4,3,1)(1,3,2,4,1)(1,4,3,2,1)例2：旅行商问题:FIFO(1,2,3,4,1)v=59(1,2,4,3,1)v=66(1,3,2,4,1)v=25X(1,4,2,3,1)V=25(1,4,3,2,1)V=591423301020654例2：旅行商问题:优先队列1423301020654(1,3,2,4,1)V=25(1,4,2,3,1)V=25XXX6.2单源最短路径问题1.问题描述下面以一个例子来说明单源最短路径问题：在下图所给的有向图G中，每一边都有一个非负边权。要求图G的从源顶点s到目标顶点t之间的最短路径。6.2单源最短路径问题2.算法思想解单源最短路径问题的优先...