算法课件(六)分支定界VIP免费

分支限界法LOGO1概述2分支限界法3应用举例LOGO1.概述搜索法在动态产生问题的解空间，并搜索问题的可行解或最优解。在生成的结点中，抛弃那些不满足约束条件（或者说不可能导出最优可行解）的结点。搜索方式深度优先搜索广度优先搜索LOGO1.概述方法1：深度优先搜索通常深度优先搜索法不全部保留结点，扩展完的结点从数据存储结构栈中弹出删去，这样，一般在数据栈中存储的结点数就是解空间树的深度，因此它占用空间较少。所以，当搜索树的结点较多，用其它方法易产生内存溢出时，深度优先搜索不失为一种有效的求解方法。LOGO1.概述方法2：广度优先搜索广度优先搜索算法，一般需存储产生的所有结点，占用的存储空间要比深度优先搜索大得多，因此，程序设计中，必须考虑溢出和节省内存空间的问题。但广度优先搜索法一般无回溯操作，即入栈和出栈的操作，所以运行速度比深度优先搜索快。LOGO2.分支限界法采用广度优先产生状态空间树的结点，并使用剪枝函数的方法称为分支限界法。所谓“分支”是采用广度优先的策略，依次生成扩展结点的所有分支（即：儿子结点）。所谓“限界”是在结点扩展过程中，计算结点的上界（或下界），边搜索边减掉搜索树的某些分支，从而提高搜索效率LOGO分支限界算法思想分支限界算法思想对对E-E-节点的扩充方式：引入节点的扩充方式：引入活节点表活节点表【【思想思想】】每个活节点有且仅有一次机会变成每个活节点有且仅有一次机会变成E-E-节节点。点。当一个节点变为当一个节点变为E-E-节点时，则生成从该节点移节点时，则生成从该节点移动一步即可到达的所有新节点。动一步即可到达的所有新节点。在生成的节点中，在生成的节点中，抛抛弃弃那些不可能导出（最优）可行解的节点，其余节点那些不可能导出（最优）可行解的节点，其余节点加入加入活节点表，然后从表中选择一个节点作为下一个活节点表，然后从表中选择一个节点作为下一个E-E-节点。节点。从活节点表中取出所选择的节点并进行扩充，直到找从活节点表中取出所选择的节点并进行扩充，直到找到解或活动表为空，扩充过程才结束。到解或活动表为空，扩充过程才结束。LOGO不同的活结点表形成不同的分枝限界法：FIFO分支限界法（队列式分支限界法）：活结点表是先进先出队列LIFO分支限界法:活结点表是堆栈最小耗费或最大收益法分支限界法（优先队列式分支限界法）:活结点表是优先权队列，LC分支限界法将选取具有最高优先级的活结点出队列，成为新的扩展结点。几种常见的分支限界法LOGOFIFOFIFO分支定界法分支定界法在解空间树上的在解空间树上的FIFOFIFO法，类似从根节点出发的法，类似从根节点出发的BFSBFS方法；方法；与与BFSBFS的区别在于：在的区别在于：在FIFOFIFO分支定界中，不可分支定界中，不可行的节点不会被搜索！行的节点不会被搜索！LOGO示例示例11：：0/10/1背包问题解背包问题解11FIFOFIFO分支定界分支定界n=3,w=[20,15,15],p=[40,25,25],c=30n=3,w=[20,15,15],p=[40,25,25],c=30E-E-节点活节节点活节点表点表AABBCCBBCCEECCEEFFGGEEFFGG解解11：：[1,0,0],[1,0,0],收益收益4040FFGG解解22：：[0,1,1],[0,1,1],收益收益5050GGNULLNULL2035×201535×301515LOGO最大收益最大收益--分支定界思想分支定界思想使用一个最大堆：其中的使用一个最大堆：其中的E-E-节点按照每个活节点收益值节点按照每个活节点收益值的的降序降序，或是按照活节点任意子树的叶节点所能获得的收，或是按照活节点任意子树的叶节点所能获得的收益估计值的益估计值的降序降序从队列中取出。从队列中取出。FIFOFIFO分支分支--限界算法用队存储活结点，优先队列式分支限界算法用队存储活结点，优先队列式分支限界法用堆存储活结点，以保证比较优良的结点先被扩限界法用堆存储活结点，以保证比较优良的结点先被扩展。且对于优先队列式分支限界算法，一旦扩展到叶结点展。且对于优先队列式分支限界算法，一旦扩展到叶结点就已经找到最优解，可以停止搜索。就已经找到最优解，可以停止搜索。采用广度优先搜索策略的目的是采用广度优先搜索策略的目的是::...