算法9_分枝限界法
第9章 分枝限界法,学习要点:理解分枝限界法的剪枝搜索策略。分枝限界法与回溯法的异同。掌握几种常见的分枝限界法思想:(1)FIFO(先进先出)分枝限界法(2)LIFO(堆栈,即D-检索)分枝限界法(3)LC(优先权队列)分枝限界法 分枝限界法的算法框架。通过应用范例学习分枝限界法的设计策略。(1)15谜问题(2)带时限的作业排序(3)0/1背包,章节内容:9.1 一般方法9.2 求最优解的分枝限界法9.3 带时限的作业排序9.4 0/1背包,9.1分枝限界法的一般方法,采用广度优先产生状态空间树的结点,并使用剪枝函数的方法称为分枝限界法。分枝限界法的基本做法是:以广度优先的方式搜索问题的状态空间树。每一个活结点只有一次机会成为扩展结点。按照广度优先的原则,活结点一旦成为扩展结点(E结点)R后,就依次生成它的所有孩子结点。在这些孩子结点中,导致不可行解或导致非最优解的孩子结点被舍弃,其余孩子结点被一一加入活结点表中。 此后,R自身成为死结点,从活结点表中取下一结点成为当前扩展结点,并重复上述结点扩展过程。 这个过程一直持续到找到所需的解或活结点表为空时为止。,分枝限界法与回溯法的异同,一、分枝限界法与回溯法的共同点都是在问题的状态空间树上搜索问题解的算法,都通过活结点表实现。都用约束函数剪去不含答案结点的分枝,用限界函数剪去不含最优解的分枝.二、分枝限界法与回溯法的区别(1)求解目标不同:回溯法的求解目标是找出解空间树中满足约束条件的所有可行解;而分枝限界法的求解目标则是找出满足约束条件的一个可行解,或某种意义下的最优解。(2)搜索方式不同:回溯法以深度优先的方式搜索解空间树,而分枝限界法则以广度优先的方式搜索解空间树。(3)对当前扩展结点的扩展方式不同:回溯法中的每个活结点可能多次成为当前扩展结点,纵深方向扩展其一个儿子,然后再回溯后扩展其他儿子;而分枝限界法中每一个活结点只有一次机会成为扩展结点,一次产生所有孩子结点,自身成为死结点,之后无需再返回该结点处。,分枝限界法的种类,根据从活结点中选择下一个扩展结点的不同次序,将分枝限界法分为三类:,(1)队列式(FIFO)分枝限界法:将活结点表组织成一个队列,按队列的先进先出(FIFO)原则选取下一个结点为当前扩展结点;(2)堆栈式(LIFO)分枝限界法:将活结点表组织成一个堆栈,按堆栈的后进先出(LIFO)原则选取下一个结点为当前扩展结点;(3)优先队列式(LC)分枝限界法:将活结点表组织成一个优先队列,并按优先队列中规定的结点优先级选取优先级最高的下一个结点为当前扩展结点。,程序9-1 分枝限界法的算法框架 (为简化起见,用指针代表所指向的结点)void BranchBound(Node *t) /t是指向状态空间树的根结点指针 do /lst为活结点表,表中元素为指针类型; for (对结点E的每个不受限的孩子) x=new Node;x->parent=E;/构造E的孩子结点x if (x是一个答案结点) 输出从x到t的一条路径; return; /输出一个可行解后,算法终止 lst.Append(x);/否则(x不是答案结点)x进活结点表if (lst.IsEmpty()/活结点表lst为空时 cout<<“没有答案结点”; return; /搜索失败终止lst.Serve(E);/从活结点表lst中输出一个活结点为E-结点 while(1);,求得一个可行解后终止,利用FIFO分枝限界法求解4-皇后问题时,实际生成的部分状态空间树如图9-1所示 (请与P182 图8-6比较) :,比较图8-6和图9-1可以看到:(n-皇后问题求第一个可行解时) FIFO分枝限界法并不占优势.,LC分枝限界法,从活结点表中选择下一个扩展结点(E结点)时,通过衡量一个活结点的搜索代价,来确定哪个活结点能够尽快到达一个答案结点。,答案结点X的搜索代价cost(X):从根结点开始,直到搜索到答案结点X为止所耗费的搜索时间.,代价函数 :从根结点到X的搜索代价。若X是答案结点,则 是从根结点到X的搜索代价;若X不是答案结点且子树X上不含任何答案结点,则 =;若X不是答案结点但子树X上包含答案结点,则 等于子树X上具有最小搜索代价的答案结点的代价.(见图9-2 (a) ),定义4个相关函数:,相对代价函数 :衡量一个结点X的相对代价。衡量标准一:生成答案结点前,子树X上需要生成的结点数目衡量标准二:子树X上离X最近的答案结点到X的路径长度(见图9-2 (b) ),相对代价估计函数 :估计结点X的相对代价。 是 的估计值,是X到达一个答案结点所需代价的估计一般的,若Y是X的孩子,则 。,结点的代价和相对代价都难以计算,因此通常采用它们的估计值作为评价函数:,代价估计函数 :由两个部分组成:从根到X的代价f(X)和从X到答案结点的估计代价 ,即 。一般的,f(X)为X在树中的层次。,以代价估计函数 最小的活结点作为下一个扩展结点(E结点)的搜索策略称为最小成本检索,简称LC-检索。,如果 ,则 ,LC-检索表现出深度优先搜索特性,成为D-检索(LIFO检索)。,如果 ,且f(X)等于X在树中的层次,则LC-检索表现出宽度优先搜索特性,成为FIFO检索。,15谜问题,问题描述:在一个4×4的方形棋盘上放置了15块编了号的牌,还剩下一个空格。号牌的一次合法移动是指将位于空格四周(上、下、左、右)的一块号牌移入空格位置的四种移动方式。要求:对于任意给定的一种初始排列,通过一系列的合法移动,将给定的初始排列转换成如图9-3 (c)所示的目标排列:,注意:(一个4×4的棋盘有16!种不同的排列)并非所有可能的状态作为初始状态都能到达目标状态。,采用广度优先搜索由初始状态图9-3(b)移动号牌得到目标状态图9-3(c)的过程。(见图9-4状态空间树),由于移动号牌和移动空格是等价的,因此从父状态到子状态的一次转换可以视为空格的一次向上、下、左或右的合法移动。图中剪去了那些与双亲状态重复的孩子结点及其子树。(即不能和上一步移动方向刚好相反)到达边界时,也无法继续移向界外方向。,第一种搜索方式: FIFO分枝限界法,采用深度优先搜索(回溯法)生成状态空间树的方式。(见图9-5部分状态空间树)深度优先搜索沿着状态生成树中最左边的路径搜索,离目标状态越来越远。,第二种搜索方式:LIFO分枝限界法(D-检索),第三种搜索方式:LC分枝限界法,定义代价估计函数: 作为搜索代价进行LC检索。(见图9-6状态空间树)其中: 是从根到结点X的路径长度, 是不在其位的非空白牌数目。 可以看到这种代价估计函数对这一实例十分有效。,课堂作业,判断由如图(a)所示的初始状态出发,经过一系列合法的号牌移动能否到达图(b)所示的目标状态?为什么?如果可以到达目标状态,请画出其LC分枝限界法实际生成的那部分状态空间树。,(a),(b),课外提高题,请编程实现用LC分枝限界法求解15迷问题。,9.2 求最优解的分枝限界法,定义一个与最优化问题的目标函数有关的代价函数(不同于上一节的搜索代价)和上下界函数:,用分枝限界法求最优解时,需要使用上下界函数作为限界函数(也即一种剪枝函数),以剪去不含最优解的分枝。,定义9-1: 状态空间树上一个结点X的代价函数 定义为:若X是答案结点,则c(X)为X所代表的可行解的目标函数值;若X为非可行解结点,则c(X)=;若X代表部分向量,则c(X)是以X为根的子树上具有最小代价的结点代价。,定义9-2: 函数 和 分别是代价函数 的上界和下界函数。对所有结点X,总有,难以计算,基于上下界函数的分枝限界法,对任意结点X,若 ,则X子树可以剪枝。,因为c(X)是X子树上最小代价答案结点的代价, 是其下界。而U是迄今已知的最小代价答案结点的代价值(即:整个树最小代价的上界值)。现若有 ,必可断定:X子树上不含最小代价答案结点。,(假定目标函数取最小值时为最优解。)设定一个上界变量U,记录迄今为止已知的最小代价答案结点的代价值(即最小代价的上界值,最小代价答案结点的代价值不会超过U)。,基于上下界函数的分枝限界法,对任意结点X,若 ,则X子树可以剪枝。,(假定目标函数取最小值时为最优解。)设定一个上界变量U,记录迄今为止已知的最小代价答案结点的代价值(即最小代价的上界值,最小代价答案结点的代价值不会超过U)。,U的值是不断修改的,根据搜索中获取的越来越多关于最小代价的上界信息,逐渐逼近最小代价答案结点的代价值(即整棵树的最小目标函数值最优解值)。,在算法已经搜索到一个答案结点之后,所有满足 的子树X都可以剪除。,基于上下界函数的分枝限界法,求最优解的限界方法:(按以下原则修正U的值)如果X是答案结点,cost(X)是X所代表的可行解的目标函数值,则U =mincost(X),U;如果X代表部分分量,u(X)是该子树上最小代价答案结点代价的上界值,则U=minu(X)+,U;于是,算法可使用 作为剪枝条件尽可能剪除多余分枝。,Livelist lst(mSize);Node *ans=null,*x,*E=t;/lst为FIFO队列do for ( 对结点E的每个孩子) x=new Node;x->parent=E;if ( )/若 ,则x不会被限界函数剪枝 lst.Append(x);/x进FIFO队列lst if (x是一个答案结点 ,基于上下界函数的FIFO分枝限界法:,Livelist lst(mSize);Node *ans=null,*x,*E=t;/lst为优先权队列do for ( 对结点E的每个孩子) x=new Node;x->parent=E;if ( )/若 ,则x不会被限界函数剪枝 lst.Append(x);/x进优先权队列lst if (x是一个答案结点 ,基于上下界函数的LC分枝限界法:,9.3 带时限的作业排序,n个作业,每个作业i处理所需时间为ti,如果能够在时限di内完成将可收益pi。将每个作业所需的处理时间、要求时限和收益用三元组(ti,di,pi) 0i<n表示。求使得总收益最大的作业子集J。,采用可变大小元组(x0,x1,.,xk)表示解,xi为作业编号。,例9-1 设有带时限的作业排序实例:n=4,(p0,d0,t0)=(5,1,1),(p1,d1,t1)=(10,3,2),(p2,d2,t2)=(6,2,1),(p3,d3,t3)=(3,1,1),求使得总收益最大的作业子集J。,显式约束:xi0, 1, ., n-1 且 xi<xi+1隐式约束:对入选子集J的作业(x0,x1,.,xk)存在一种作业排列使J中作业均能如期完成。,