算法课件六分支定界.ppt

1、LOGO1v1 1 概述概述v2 2 分支限界法分支限界法v3 3 应用举例应用举例LOGO21. 1. 概述概述v搜索法搜索法 在动态产生问题的解空间，并搜索问题的可行在动态产生问题的解空间，并搜索问题的可行解或最优解。解或最优解。 在生成的结点中，抛弃那些不满足约束条件在生成的结点中，抛弃那些不满足约束条件（或者说不可能导出最优可行解）的结点。（或者说不可能导出最优可行解）的结点。v搜索方式搜索方式 深度优先搜索深度优先搜索 广度优先搜索广度优先搜索LOGO31. 1. 概述概述v方法方法1 1：深度优先搜索：深度优先搜索 通常深度优先搜索法不全部保留结点，扩展完通常深度优先搜索法不全部保

2、留结点，扩展完的结点从数据存储结构栈中弹出删去，这样，的结点从数据存储结构栈中弹出删去，这样，一般在数据栈中存储的结点数就是解空间树的一般在数据栈中存储的结点数就是解空间树的深度，因此它占用空间较少。深度，因此它占用空间较少。 所以，当搜索树的结点较多，用其它方法易产所以，当搜索树的结点较多，用其它方法易产生内存溢出时，深度优先搜索不失为一种有效生内存溢出时，深度优先搜索不失为一种有效的求解方法。的求解方法。LOGO41. 1. 概述概述v方法方法2 2：广度优先搜索：广度优先搜索 广度优先搜索算法，一般需存储产生的所有结广度优先搜索算法，一般需存储产生的所有结点，占用的存储空间要比深度优先搜

3、索大得多，点，占用的存储空间要比深度优先搜索大得多，因此，程序设计中，必须考虑溢出和节省内存因此，程序设计中，必须考虑溢出和节省内存空间的问题。空间的问题。 但广度优先搜索法一般无回溯操作，即入栈和但广度优先搜索法一般无回溯操作，即入栈和出栈的操作，所以运行速度比深度优先搜索快。出栈的操作，所以运行速度比深度优先搜索快。LOGO52.2. 分支限界法分支限界法采用广度优先产生状态空间树的结点，并使用剪采用广度优先产生状态空间树的结点，并使用剪枝函数的方法称为枝函数的方法称为分支限界法分支限界法。 所谓所谓“分支分支”是采用广度优先的策略，依次生是采用广度优先的策略，依次生成扩展结点的所有分支（

4、即：儿子结点）。成扩展结点的所有分支（即：儿子结点）。 所谓所谓“限界限界”是在结点扩展过程中，计算结点是在结点扩展过程中，计算结点的的上界上界（或（或下界下界），边搜索边减掉搜索树的某），边搜索边减掉搜索树的某些分支，从而提高搜索效率些分支，从而提高搜索效率LOGO6LOGO7不同的活结点表形成不同的分枝限界法：不同的活结点表形成不同的分枝限界法： FIFOFIFO分支限界法分支限界法（队列式分支限界法）：活结（队列式分支限界法）：活结点表是先进先出队列点表是先进先出队列 LIFOLIFO分支限界法分支限界法: :活结点表是堆栈活结点表是堆栈 最小耗费或最大收益法最小耗费或最大收益法分支限界

5、法分支限界法（优先队列（优先队列式分支限界法）式分支限界法）: :活结点表是优先权队列，活结点表是优先权队列，LCLC分支限界法将选取具有最高优先级的活结点出分支限界法将选取具有最高优先级的活结点出队列，成为新的扩展结点。队列，成为新的扩展结点。几种常见的分支限界法几种常见的分支限界法LOGO8LOGO92035201535301515LOGO10LOGO11 个元素的序列个元素的序列n,21nkkk 当且仅当满足下述关系时，称之为堆当且仅当满足下述关系时，称之为堆122iiiikkkk 或或122iiiikkkk 2, 2 , 1ni堆LOGO12不可行的解：不可行的解：D D【1 1，1

6、1，1 1】, , J J【1 1，0 0，1 1】20201530LOGO13LOGO14【定界函数定界函数】如果一个如果一个节点的定界值不比当前节点的定界值不比当前最优旅行更小，则将被最优旅行更小，则将被删除而不被展开！删除而不被展开！306424141126【注注】活节点表采用堆结构活节点表采用堆结构35 4055211929LOGOv假设有4个物品，重量分别是（4,7,5,3），价值分别是（40,42,25,12），背包容量是W=10。v单位重量价值分别为：（10,6,5,4）LOGOLOGO17o队列式分支限界法程序框架队列式分支限界法程序框架o设设T为状态空间树的根结点；初始化队列

7、为状态空间树的根结点；初始化队列Q；o将将T入队；入队；o循环，直到队列循环，直到队列Q空（无解）：空（无解）：o 结点结点e出队；出队；o 若若e是回答结点，则是回答结点，则o 输出解或求解路径；输出解或求解路径；o 否则否则o 检查检查e的所有子结点的所有子结点x：o 若若x满足约束条件，则满足约束条件，则 o 将将x入队；入队；o 记录搜索路径；记录搜索路径；LOGO18v优先队列式分支限界法程序框架优先队列式分支限界法程序框架p设T为状态空间树的根结点；C(x)为耗费估计函数；初始化优先队列Q；p计算C(T)，并将T入队；p循环，直到队列Q空（无解）：p 结点e出队；p 若e是回答结点

8、，则p 输出解或求解路径，求解结束；p 否则p 检查e的所有子结点x：p 若x满足约束条件，则p 计算C(x)，并将x入队；p 记录搜索路径；LOGOLOGO示例3 ：装载问题1. 问题描述有一批共个集装箱要装上有一批共个集装箱要装上2 2艘载重量分别为艘载重量分别为C1C1和和C2C2的轮船，其中集的轮船，其中集装箱装箱i i的重量为的重量为WiWi，且，且211ccwnii装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这这2 2艘轮船。如果有，找出一种装载方案。艘轮船。如果有，找出一种装载方案。 容易证明：容易证明：如果

9、一个给定装载问题有解，则采用下面的策略可得到如果一个给定装载问题有解，则采用下面的策略可得到最优装载方案。最优装载方案。 (1)(1)首先将第一艘轮船尽可能装满；首先将第一艘轮船尽可能装满；(2)(2)将剩余的集装箱装上第二艘轮船。将剩余的集装箱装上第二艘轮船。 LOGO 问题描述：印刷电路板将布线区域划分成问题描述：印刷电路板将布线区域划分成n n* *m m个方格阵列。精确个方格阵列。精确的电路布线问题要求确定连接方格的电路布线问题要求确定连接方格a a的中点到方格的中点到方格b b的中点的最短布的中点的最短布线方案。在布线时，电路只能沿直线或直角布线。为了避免线路相线方案。在布线时，电路

10、只能沿直线或直角布线。为了避免线路相交，已布了线的方格做了封锁标记，其他线路不允许穿过被封锁的交，已布了线的方格做了封锁标记，其他线路不允许穿过被封锁的方格方格LOGO 布线问题适合采用队列式分支限界法来解决。布线问题适合采用队列式分支限界法来解决。 从起始位置从起始位置a a开始将它作为第一个扩展结点。与该结点相邻并且可达开始将它作为第一个扩展结点。与该结点相邻并且可达的方格被加入到活结点队列中，并且将这些方格标记为的方格被加入到活结点队列中，并且将这些方格标记为1 1，表示它们到，表示它们到a a的的距离为距离为1 1 接着从活结点队列中取出队首作为下一个扩展结点，并将与当前扩展接着从活结

11、点队列中取出队首作为下一个扩展结点，并将与当前扩展结点相邻且未标记过的方格标记为结点相邻且未标记过的方格标记为2 2，并存入活节点队列。这个过程一直，并存入活节点队列。这个过程一直继续到算法搜索到目标方格继续到算法搜索到目标方格b b或活结点队列为空时为止（表示没有通路）或活结点队列为空时为止（表示没有通路）LOGO最开始，队列中的活结点为标最开始，队列中的活结点为标1 1的格的格子，随后经过一个轮次，活结点变为标子，随后经过一个轮次，活结点变为标2 2的格子，以此类推，一旦的格子，以此类推，一旦b b方格成为活节方格成为活节点便表示找到了最优方案。为什么这条路点便表示找到了最优方案。为什么这

12、条路径一定就是最短的呢？这是由于我们这个径一定就是最短的呢？这是由于我们这个搜索过程的特点所决定的，假设存在一条搜索过程的特点所决定的，假设存在一条由由a a至至b b的更短的路径，的更短的路径，b b结点一定会更早结点一定会更早地被加入到活结点队列中并得到处理。地被加入到活结点队列中并得到处理。 LOGO问题：问题：FIFO搜索或搜索或LIFO搜索也可以通过加入搜索也可以通过加入“限界限界”策略加速搜索，与优先队列式分支限界法策略加速搜索，与优先队列式分支限界法LC-检索检索的区别在哪儿呢？的区别在哪儿呢？ 答案：答案：由于由于FIFO搜索或搜索或LIFO搜索是盲目地扩展结点，搜索是盲目地扩展结点，当前最优解距真正的最优解距离较大，作为当前最优解距真正的最优解距离较大，作为“界界”所起所起到的剪枝作用很有限，不能有效提高搜索速度。到的剪枝作用很有限，不能有效提高搜索速度。LOGO25LOGOLOGOLOGOLOGOLOGOLOGO