第6章 分支限界法.ppt

《第6章 分支限界法.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第6章分枝-限界法1学习要点理解分支限界法的剪枝搜索策略。掌握分支限界法的算法框架（1）队列式(FIFO)分支限界法（2）优先队列式分支限界法通过应用范例学习分支限界法的设计策略。（1）单源最短路径问题（2）装载问题；（3）布线问题（4）0-1背包问题；（5）最大团问题；（6）旅行售货员问题（7）电路板排列问题（8）批处理作业调度问题26.1分支限界法的基本思想分支限界法与回溯法（1）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最

2、优解。（2）搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。36.1分支限界法的基本思想分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。

3、46.1分支限界法的基本思想两类常用的方法选择下一个E-结点：（1）先进先出(FIFO)：从活结点表中取出结点的顺序与加入结点的顺序相同。后进先出(LIFO)：从活结点表中取出结点的顺序与加入结点的顺序相反。（2）优先队列式分支限界法按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。5堆(Heap)优先级队列每次出队列的是优先权最高的元素优先级队列支持以下操作：找出一个具有最高优先级的元素删除一个具有最高优先级的元素添加一个元素到集合中6完全二叉树数组表示KiK2i+1&&KiK2i+2完全二叉树数组表示KiK2i+1&&

4、KiK2i+2堆的定义09098787787845456565313153232353171791765234578875331877853456593117237自下向上逐步调整为最小堆将一组用数组存放的任意数据调整成堆5353171778780923456587i0923456587i53177823456587953177894565872385353171778780923456587i0923456587i53176594578872353965174578872395353171778780923456587i092345658

5、7i09539651745788723105353171778780923456587i0923456587i179176523457887531153171778780923456587i0923456587j11在堆中插入新元素1153j1123i最小堆的向上调整91765234578875311125317117878094565870917456587j115323i2317ji91165174578875323135311782331456587在堆中删除根元素095311782331456587095311780931456587

6、232311653145788753145323781131456587在堆中删除根元素095323781131456587112365314578875315例1：n=3时的0-1背包问题，w=[20,15,15]p=[40,25,25]c=30E-结点和活结点死结点FIFO队列CBXX20403050152515250CECGFEGFG16例1：n=3时的0-1背包问题，w=[20,15,15]p=[40,25,25]c=30E-结点和活结点死结点LIFO队列BCXX20403050152515250BBFGBFBE17例1：n=3时的0

7、-1背包问题，w=[20,15,15]p=[40,25,25]c=30E-结点和活结点死结点优先队列20403050152515250XXCBCCECGFG18例2：旅行商问题1423301020654旅行线路(1,2,4,3,1)(1,3,2,4,1)(1,4,3,2,1)19例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=59142330102065420例2：旅行商问题:优先队列1423301020654(1,3

8、,2,4,1)V=25(1,4,2,3,1)V=25XXX216.2单源最短路径问题1.问题描述下面以一个例子来说明单源最短路径问题：在下图所给的有向图G中，每一边