算法课件(六)分支定界

《算法课件(六)分支定界》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1分支限界法21概述2分支限界法3应用举例31.概述搜索法在动态产生问题的解空间，并搜索问题的可行解或最优解。在生成的结点中，抛弃那些不满足约束条件（或者说不可能导出最优可行解）的结点。搜索方式深度优先搜索广度优先搜索41.概述方法1：深度优先搜索通常深度优先搜索法不全部保留结点，扩展完的结点从数据存储结构栈中弹出删去，这样，一般在数据栈中存储的结点数就是解空间树的深度，因此它占用空间较少。所以，当搜索树的结点较多，用其它方法易产生内存溢出时，深度优先搜索不失为一种有效的求解方法。51.概述方法2：广度优先搜索广度优先搜索

2、算法，一般需存储产生的所有结点，占用的存储空间要比深度优先搜索大得多，因此，程序设计中，必须考虑溢出和节省内存空间的问题。但广度优先搜索法一般无回溯操作，即入栈和出栈的操作，所以运行速度比深度优先搜索快。62.分支限界法采用广度优先产生状态空间树的结点，并使用剪枝函数的方法称为分支限界法。所谓“分支”是采用广度优先的策略，依次生成扩展结点的所有分支（即：儿子结点）。所谓“限界”是在结点扩展过程中，计算结点的上界（或下界），边搜索边减掉搜索树的某些分支，从而提高搜索效率7分支限界算法思想对E-节点的扩充方式：引入活节点表【思

3、想】每个活节点有且仅有一次机会变成E-节点。当一个节点变为E-节点时，则生成从该节点移动一步即可到达的所有新节点。在生成的节点中，抛弃那些不可能导出（最优）可行解的节点，其余节点加入活节点表，然后从表中选择一个节点作为下一个E-节点。从活节点表中取出所选择的节点并进行扩充，直到找到解或活动表为空，扩充过程才结束。8不同的活结点表形成不同的分枝限界法：FIFO分支限界法（队列式分支限界法）：活结点表是先进先出队列LIFO分支限界法:活结点表是堆栈最小耗费或最大收益法分支限界法（优先队列式分支限界法）:活结点表是优先权队列，L

4、C分支限界法将选取具有最高优先级的活结点出队列，成为新的扩展结点。几种常见的分支限界法9FIFO分支定界法在解空间树上的FIFO法，类似从根节点出发的BFS方法；与BFS的区别在于：在FIFO分支定界中，不可行的节点不会被搜索！10示例1：0/1背包问题解1FIFO分支定界n=3,w=[20,15,15],p=[40,25,25],c=30E-节点活节点表ABCBCECEFGEFG解1：[1,0,0],收益40FG解2：[0,1,1],收益50GNULL2035×201535×30151511最大收益-分支定界思想使用一个

5、最大堆：其中的E-节点按照每个活节点收益值的降序，或是按照活节点任意子树的叶节点所能获得的收益估计值的降序从队列中取出。FIFO分支-限界算法用队存储活结点，优先队列式分支限界法用堆存储活结点，以保证比较优良的结点先被扩展。且对于优先队列式分支限界算法，一旦扩展到叶结点就已经找到最优解，可以停止搜索。采用广度优先搜索策略的目的是:尽早发现剪枝点。12个元素的序列当且仅当满足下述关系时，称之为堆或堆130-1背包问题解2：最大收益法E-节点活节点表ABCBECEC解1：[1,0,0],收益40C解2：[0,1,1],收益50

6、GNULLn=3,w=[20,15,15],p=[40,25,25],c=30FGFG不可行的解：D【1，1，1】,J【1，0，1】202015××3014示例2：旅行商问题FIFO分支定界E-节点活节点表BCDEFGCDEEFGHIJKF路径12341，59G路径12431，66H路径13241，25IJK路径1342，不展开路径14231，25路径1432，不展开××15示例2解法2：最小耗费法使用最小堆存储活节点E-节点活节点表BEDCEDJKCDHJKICH路径13241，25【定界函数】如果一个节点的定界值不比当

7、前最优旅行更小，则将被删除而不被展开！306424141126【注】活节点表采用堆结构3540552119290-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优先队列式分支限

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