算法课件(六)分支定界.ppt

1,分支限界法,2,1 概述 2 分支限界法 3 应用举例,3,1. 概述,搜索法 在动态产生问题的解空间，并搜索问题的可行解或最优解。 在生成的结点中，抛弃那些不满足约束条件（或者说不可能导出最优可行解）的结点。 搜索方式 深度优先搜索 广度优先搜索,4,1. 概述,方法1：深度优先搜索 通常深度优先搜索法不全部保留结点，扩展完的结点从数据存储结构栈中弹出删去，这样，一般在数据栈中存储的结点数就是解空间树的深度，因此它占用空间较少。 所以，当搜索树的结点较多，用其它方法易产生内存溢出时，深度优先搜索不失为一种有效的求解方法。,5,1. 概述,方法2：广度优先搜索 广度优先搜索算法，一般需存储产生的所有结点，占用的存储空间要比深度优先搜索大得多，因此，程序设计中，必须考虑溢出和节省内存空间的问题。 但广度优先搜索法一般无回溯操作，即入栈和出栈的操作，所以运行速度比深度优先搜索快。,6,2. 分支限界法,采用广度优先产生状态空间树的结点，并使用剪枝函数的方法称为分支限界法。 所谓“分支”是采用广度优先的策略，依次生成扩展结点的所有分支（即：儿子结点）。 所谓“限界”是在结点扩展过程中，计算结点的上界（或下界），边搜索边减掉搜索树的某些分支，从而提高搜索效率,7,分支限界算法思想,对E-节点的扩充方式：引入活节点表 【思想】每个活节点有且仅有一次机会变成 E-节点。当一个节点变为E-节点时，则生成从该节点移动一步即可到达的所有新节点。在生成的节点中，抛弃那些不可能导出（最优）可行解的节点，其余节点加入活节点表，然后从表中选择一个节点作为下一个E-节点。 从活节点表中取出所选择的节点并进行扩充，直到找到解或活动表为空，扩充过程才结束。,8,不同的活结点表形成不同的分枝限界法： FIFO分支限界法（队列式分支限界法）：活结点表是先进先出队列 LIFO分支限界法:活结点表是堆栈 最小耗费或最大收益法分支限界法（优先队列式分支限界法）:活结点表是优先权队列，LC分支限界法将选取具有最高优先级的活结点出队列，成为新的扩展结点。,几种常见的分支限界法,9,FIFO分支定界法,在解空间树上的FIFO法，类似从根节点出发的BFS方法； 与BFS的区别在于：在FIFO分支定界中，不可行的节点不会被搜索！,10,示例1：0/1背包问题解1,FIFO分支定界,n=3, w=20,15,15, p=40,25,25, c=30,E-节点 活节点表,A,B,C,E,解1：1,0,0, 收益40,F,G,解2：0,1,1, 收益50,G,NULL,20,35,×,20,15,35,×,30,15,15,11,最大收益-分支定界思想,使用一个最大堆：其中的 E-节点按照每个活节点收益值的降序，或是按照活节点任意子树的叶节点所能获得的收益估计值的降序从队列中取出。 FIFO分支-限界算法用队存储活结点，优先队列式分支限界法用堆存储活结点，以保证比较优良的结点先被扩展。且对于优先队列式分支限界算法，一旦扩展到叶结点就已经找到最优解，可以停止搜索。 采用广度优先搜索策略的目的是:尽早发现剪枝点。,12,或,堆,13,0-1背包问题解2：最大收益法,E-节点 活节点表,A,B,E,C,解1：1,0,0, 收益40,C,解2：0,1,1, 收益50,G,NULL,n=3, w=20,15,15, p=40,25,25, c=30,F,G,不可行的解：D【1，1，1】, J【1，0，1】,20,20,15,×,×,30,14,示例2：旅行商问题,FIFO分支定界,E-节点 活节点表,B,C,E,F,路径12341，59,G,路径12431，66,H,路径13241，25,I,J,K,路径1342，不展开,路径14231，25,路径1432，不展开,×,×,15,示例2解法2：最小耗费法,使用最小堆存储活节点,E-节点 活节点表,B,E,D,H,路径13241，25,【定界函数】如果一个节点的定界值不比当前最优旅行更小，则将被删除而不被展开！,30,6,4,24,14,11,26,【注】活节点表采用堆结构,35,40,55,21,19,29,0-1背包问题解3：最大收益法,假设有4个物品，重量分别是（4,7,5,3），价值分别是（40,42,25,12），背包容量是W=10。 单位重量价值分别为：（10,6,5,4）,18,队列式分支限界法程序框架 设T为状态空间树的根结点；初始化队列Q； 将T入队； 循环，直到队列Q空（无解）： 结点e出队； 若e是回答结点，则 输出解或求解路径； 否则 检查e的所有子结点x： 若x满足约束条件，则 将x入队； 记录搜索路径；,19,优先队列式分支限界法程序框架 设T为状态空间树的根结点；C(x)为耗费估计函数；初始化优先队列Q； 计算C(T)，并将T入队； 循环，直到队列Q空（无解）： 结点e出队； 若e是回答结点，则 输出解或求解路径，求解结束； 否则 检查e的所有子结点x： 若x满足约束条件，则 计算C(x)，并将x入队； 记录搜索路径；,示例3 ：装载问题,1. 问题描述,有一批共个集装箱要装上2艘载重量分别为C1和C2的轮船，其中集 装箱i的重量为Wi，且,装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。如果有，找出一种装载方案。,容易证明：如果一个给定装载问题有解，则采用下面的策略可得到最优装载方案。 (1)首先将第一艘轮船尽可能装满； (2)将剩余的集装箱装上第二艘轮船。,问题描述：印刷电路板将布线区域划分成n*m个方格阵列。精确的电路布线问题要求确定连接方格a的中点到方格b的中点的最短布线方案。在布线时，电路只能沿直线或直角布线。为了避免线路相交，已布了线的方格做了封锁标记，其他线路不允许穿过被封锁的方格,示例4：布线问题,布线问题适合采用队列式分支限界法来解决。 从起始位置a开始将它作为第一个扩展结点。与该结点相邻并且可达的方格被加入到活结点队列中，并且将这些方格标记为1，表示它们到a的距离为1 接着从活结点队列中取出队首作为下一个扩展结点，并将与当前扩展结点相邻且未标记过的方格标记为2，并存入活节点队列。这个过程一直继续到算法搜索到目标方格b或活结点队列为空时为止（表示没有通路）,最开始，队列中的活结点为标1的格子，随后经过一个轮次，活结点变为标2的格子，以此类推，一旦b方格成为活节点便表示找到了最优方案。为什么这条路径一定就是最短的呢？这是由于我们这个搜索过程的特点所决定的，假设存在一条由a至b的更短的路径，b结点一定会更早地被加入到活结点队列中并得到处理。,问题：FIFO搜索或LIFO搜索也可以通过加入“限界”策略加速搜索，与优先队列式分支限界法LC-检索的区别在哪儿呢？,答案：由于FIFO搜索或LIFO搜索是盲目地扩展结点，当前最优解距真正的最优解距离较大，作为“界”所起到的剪枝作用很有限，不能有效提高搜索速度。,26,作业,实现旅行商问题的分支限界FIFO、优先队列求解 实现0-1背包问题的分支限界FIFO、优先队列求解 *印刷电路板排列问题 要求： 必做：旅行商问题、0-1背包问题任选一题完成 选做：印刷电路板排列问题 提交代码和报告 报告内容：分析所实现问题的程序执行过程,