分枝-限界(Branch Bound).ppt

* * * * * When inserting a node into the queue, one needs to judge whether it is a feasible solution or not Extend to bound function? * * * * * * * * * * * * * * * * * * * 分枝-限界(Branch Bound) 计算机科学与技术学院 主要内容 引论 主要思想 求解步骤 应用 作业调度问题(Job Scheduling) 旅行商问题(TSP) 算法思路(1) 分支限界法常以广度优先或以最小耗费（最大效益）优先的方式有哪些信誉好的足球投注网站问题的解空间树 在分支限界法中，每一个活结点只有一次机会成为扩展结点 活结点一旦成为扩展结点，就一次性产生其所有儿子结点。 在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中 此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止 活节点选取规则 FIFO LIFO Max Profit（MP） Least Cost (LC) 算法思路(2) 分支限界法与回溯法的不同 求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。 有哪些信誉好的足球投注网站方式的不同：回溯法以深度优先的方式有哪些信誉好的足球投注网站解空间树，而分支限界法则以广度优先或以最小耗费优先的方式有哪些信誉好的足球投注网站解空间树。 迷宫问题：问题描述 问题描述：内有障碍物的长方形格子，含有一个入口和一个出口，找到一个从入口到出口，能绕过所有障碍物的路径 矩阵表示 0 0 0 0 1 1 0 0 0 迷宫问题：FIFO Search 1,1 1,2 1,3 2,1 2,2 2,3 3,1 3,2 3,3 扩展节点 活节点队列 解空间按宽度优先有哪些信誉好的足球投注网站 活结点列表存储于队列中 (1,1) (1,2) (2,1) (3,1) (3,3) (1,3) (3,2) 0/1Knapsack FIFO Search Nodes are expended in a breadth-first manner Live nodes are stored in a queue Max-profit search Nodes are expended in a max-profit manner Live nodes are stored in a max heap 0/1Knapsack:status of SP n=3，c= 30 w= [ 20 , 15 , 15 ] p= [ 40 , 25 , 25 ] TSP FIFO search Least-cost search（min-heap） 应用问题 作业调度问题(Job Scheduling) 旅行商问题(TSP) Least Cost Search (Bounding function) 成本函数(Cost function) 设Cost(x)为可行解的成本，(最小)优化问题要求找有最小成本的可行解 定义状态空间树上任一结点x的成本函数 c(x)如下: 如x为可行叶结点则 c(x)=cost(x); 如x为非叶结点 c(x)=状态空间树上以x为根的子树中可行解成本的最小值 如其子树中无可行解则c(x)=∞ LC-检索过程 每次从活节点表中取出最小成本节点作为E-节点并展开其全部子节点 但在展开前不知道c(x)的值 以c(x)的下界估值?(x)做LC-检索-启发式 要求?(x)满足: ?(x)=Cost(x),当x为可行叶节点时 LC-限界 令U为当前最优成本值 对当前的选取的扩展节点E，当?(E)≥U时算法结束。因为，这时活节点表中其它节点的下界估计也≥U， 展开这些活节点不能产生更好的解 对正在展开的子节点x， 如?(x)≥U，则停止产生子节点x， 即不将其放入活节点表 这种限界方法也可用于FIFO活结点表上，称为FIFO分枝-限界。U初始为∞ ，其后用新得到的可行解值加以修改 带截止期的作业调度问题（1） n个作业，1台处理机，每个作业i对应一个三元组(pi,di,ti) pi－罚款额 di－截止期 ti －需要的处理机时间 求可行的作业子集J，使得罚款额Σpj最小,其中j为不在J中的作业 定长元组表示可行作业子集:(x(1),┅,x(n)) 设X=(x(1),…x(k))为状态空间树的节点 下界?(x)可估计为已确知的罚款额: Σ(1-x(j))pj ,求和范围为1≤j≤k 带截止期的作业调度问题（2） 限界 可行解的必要条件： Σij=1