《分枝-限界BranchBound--精品PPT课件.ppt》由会员分享，可在线阅读，更多相关《分枝-限界BranchBound--精品PPT课件.ppt（27页珍藏版）》请在三一文库上搜索。
1、分枝-限界(Branch & Bound),宫秀军 天津大学计算机科学与技术学院 ,主要内容,引论 主要思想 求解步骤 应用 作业调度问题(Job Scheduling) 旅行商问题(TSP),算法思路(1),分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树 在分支限界法中，每一个活结点只有一次机会成为扩展结点 活结点一旦成为扩展结点，就一次性产生其所有儿子结点。 在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中 此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空
2、时为止 活节点选取规则 FIFO LIFO Max Profit（MP） Least Cost (LC),算法思路(2),分支限界法与回溯法的不同 求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。 搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。,迷宫问题：问题描述,问题描述：内有障碍物的长方形格子，含有一个入口和一个出口，找到一个从入口到出口，能绕过所有障碍物的路径 矩阵表示 0 0 0 0 1 1 0 0 0,
3、迷宫问题：FIFO Search,1,1,1,2,1,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
4、 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(
5、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， 即不将其放入活节点表 这种限界方
6、法也可用于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 ,求和范围为1jk,带截止期的作业调度问题（2）,限界 可行解的必要条件： ij=1xjtjdi 为能较早地使用(x) U的限界功能,可以在每
7、个结点x计算c(x)的上界u(x),并用u(x)修改U值 u(x)可取x为根的子树下包含的任一可行解的值 例如取x(k+1)=x(n)=0,或用贪心法快速得到一个可行解 算法每生成一个子节点时就用u(x)修改U,调度问题的定长元组表示,已知4个作业的三元组(pi,di,ti)分别为 (5,1,1) (10,3,2) (6,2,1) (3,1,1),调度问题的另一种状态空间树,LC-检索限界,可行条件(截至期)作为一种限界方法,优化解为2,3，罚款额为8,(x),u(x):该点对应的可行解的值,非可行节点,被限界掉的节点,货郎担问题(TSP),状态空间树(Permutation Tree) 费用
8、矩阵表示 周游路线包括的边在邻接矩阵中不同行不同列 归约矩阵和归约数（作为(X)）,TSP的状态空间树,一种计算(X)的方法,设f=(e1,en)为一条周游路线 ei为来自邻接矩阵的第i行的边，所有ei不同列 cost(ei)=A(i,ji) 行归约 ri=minA(i,j)|1jn 1jnrj 为行归约数 设(i,j)=A(i,j)-ri ,为行归约后的矩阵 Cost(f)1jnrj Cost(f)=以为成本矩阵时f的长度+1jnrj 列归约 ci=minA(j,i)|1jn 1jncj 为列归约数. 对做列归约得到矩阵R和归约数1jncj Cost(f)=f在R中的成本+ 1jnrj+ 1
9、jncj,归约矩阵和归约数,每行每列均含有0的矩阵称为归约阵 矩阵归约 假设第i行的约数为ti,第j列的约数为rj, 1i, jn, 那么各行、列的约数之和称为矩阵约数,归约矩阵和归约数:例子,行约数等于102234=21,列归约数10300=4,根节点的约数r=25 (1)=25,(X)计算,令S为R的子节点且S不是叶节点(S)=(R)+A(i,j)+r,r为节点S处的归约数. A(i,j)为R的归约矩阵中边的权值. 将R的归约矩阵中i行j列置为(禁止再选择节点i的出边和的j入边);将A(j,i)置为.得到的S处的矩阵.对其归约得到r. 如S为叶节点,(S)=根到此叶节点的周游路线成本,(X)计算,节点2处的矩阵 已是归约矩阵 (2)=25+10=35,(X)计算,节点3处的矩阵 对其归约得归约数11 (3)=25+17+11=53,算法LCBB生成的状态空间树,