六章分支限界法.ppt

《六章分支限界法.ppt》由会员分享，可在线阅读，更多相关《六章分支限界法.ppt（33页珍藏版）》请在三一办公上搜索。

1、,第六章 分支限界法,算法设计与分析Design and Analysis of Computer Algorithm,信息工程学院张永梅,学时分配,本课程成绩由平时作业、上机实验和期末考试进行评定：,考核方法及成绩评定标准,平时作业：10%上机实验：30%期末考试：60%，考试形式为开卷,第六章 分支限界法（Branch-and-Bound）,1、基本要求要求掌握分治限界法的基本思想，算法设计步骤，及常见问题的算法。要求理解分支限界法的剪枝搜索策略。,2、教学内容基本思想 0-1背包问题,第六章 分支限界法（Branch-and-Bound）,6.1分支限界法的基本思想,分支限界法与回溯法,

2、（1）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。,（2）搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。,回溯与分支限界是对穷举法的改进。它们每次只构造候选解的一个分量，然后评估这个部分解：如果加上剩下的分量也不可能求得一个解，就不再生成剩下的分量。回溯法和分支限界都是以构造一棵状态空间树为基础，树的节点反映了对一个部分解所做的特定的选择。,6.1分支限界法的基本思想,分支限界法与回溯法,有两种生成问题状态的

3、基本方法。它们都是从根结点开始然后生成状态空间树上的其它结点。,6.1分支限界法的基本思想,如果已生成一个结点而它的所有儿子结点还没有全部生成，则这个结点叫做活结点（Live node）。当前正在生成其儿子结点的活结点叫E-结点（正在扩展的结点,Expanded node）。不再进一步扩展或者其儿子结点已全部生成的结点就是死结点（Dead node）。,在生成问题状态的两种方法中，都要有一张活结点表。问题状态的生成可以采用两种不同的方法：如果对一个E-结点R一旦生成了它的一个新的儿子C，就把C当作新的扩展结点，在完成对子树C（以C为根的子树）的穷尽搜索之后。将R结点重新变成 E-结点，继续生成

4、R的下一个儿子（如果存在）。这称做深度优先的问题状态生成法。在另一种状态生成方法中，一个E-结点一直保持到变成死结点为止。即在一个E-结点变成死结点之前，它一直是扩展结点。这实际上是一种宽度优先的问题状态生成法。,6.1分支限界法的基本思想,广度优先遍历(BFS)方法：从图的某一顶点V0出发，访问此顶点后，依次访问V0的各个未曾访问过的邻接点；然后分别从这些邻接点出发，广度优先遍历图，直至图中所有已被访问的顶点的邻接点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止。,广度遍历：V1 V2 V3 V4 V5 V6 V7 V8

5、,6.1分支限界法的基本思想,在这两种方法中，为了避免生成那些不可能产生最佳解（或所需解）的问题状态，将用限界函数去杀死那些实际上不可能产生所需解的活结点，以减少问题的计算工作量。这样做要非常小心，以使得在处理结束时至少能生成一个答案结点；如果这个问题要求找出全部解，则要能生成所有的答案结点。使用限界函数的深度优先结点生成方法称为回溯法（backtracking）。E-结点一直保持到死为止的状态生成方法导致分枝-限界方法（branch-and-bound）。,6.1分支限界法的基本思想,6.1分支限界法的基本思想,分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。对已

6、处理的各结点根据限界函数估算目标函数的可能取值，从中选取使目标函数取得极值（极大/极小）的结点优先进行广度优先搜索不断调整搜索方向，尽快找到解。,特点：限界函数常基于问题的目标函数，适用于求解最优化问题。,6.1分支限界法的基本思想,分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。,此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。,在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍

7、弃，其余儿子结点被加入活结点表中。,分支限界法是最佳优先搜索法,分支限界法就是最佳优先（包括广度优先在内）的搜索法。分支限界法将要搜索的结点按评价函数的优劣排序，让好的结点优先搜索，将坏的结点剪去。所以准确说，此方法应称为界限剪支法。分支限界法中有两个要点：,评价函数的构造；搜索路径的构造。,6.1分支限界法的基本思想,评价函数的构造,评价函数要能够提供一个评定候选扩展结点的方法，以便确定哪个结点最有可能在通往目标的最佳路径上。,6.1分支限界法的基本思想,搜索路径的构造,在回溯法中，每次仅考察一条路径，因而只需要构造这一条路径即可：前进时记下相应结点，回溯时删去最末尾结点的记录。这比较容易实

8、现。在分支限界法中，是同时考察若干条路径，那么又该如何构造搜索的路径呢？,对每一个扩展的结点，建立三个信息：,(1)该结点的名称；(2)它的评价函数值；(3)指向其前驱的指针；,这样一旦找到目标，即可逆向构造其路径。,6.1分支限界法的基本思想,界限(Bounding),评价函数f(d)关系着算法的效率乃至成败。因为在大多数问题中f(d)只是个估计值，所以单靠f(d)是不够的。通常还要设计它的上、下界函数U(d)和L(d)。L(d)f(d)U(d)。所谓分支限界法就是通过评价函数及其上、下界函数的计算，将状态空间中不可能产生最佳解的子树剪去，减少搜索的范围，提高效率。因而更准确的称呼应是“界限

9、剪支法”。,6.1分支限界法的基本思想,对评价函数的讨论,分支限界法总耗时为O(n22n)，它与回溯法、动态规划法等在时间复杂性上没有本质的区别。然而，如果评价函数选择得好，采用分支限界法可能有一个小得多的常数因子。好的评价函数应该有一个尽可能高的下界估计和一个尽可能低的上界估计，从而使得搜索空间能够得到有效的压缩，从而提高效率。在理论上可以证明好的评价函数所搜索的结点不会多于坏的评价函数所搜索的结点。,6.1分支限界法的基本思想,6.1分支限界法的基本思想,常见的两种分支限界法,（1）队列式(FIFO)分支限界法 按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。,（2）优先队列式分

10、支限界法 按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。,最大优先队列：使用最大堆，体现最大效益优先最小优先队列：使用最小堆，体现最小费用优先,解空间树的动态搜索,利用回溯法求解问题，虽然剪枝减少了搜索空间，但整个搜索按深度优先机械进行，是盲目搜索（不可预测本结点以下的结点进行得如何）。,6.1分支限界法的基本思想,解空间树的动态搜索,分支限界法首先确定一个合理的限界函数，并根据限界函数确定目标函数的界down,up；然后按照广度优先策略遍历问题的解空间树，在某一分支上，依次搜索该结点的所有孩子结点，分别估算这些孩子结点的目标函数的可能取值（对最小化问题，估算结点的down，

11、对最大化问题，估算结点的up）。如果某孩子结点的目标函数值超出目标函数的界，则将其丢弃（从此结点生成的解不会比目前已得到的更好），否则入待处理表。,6.1分支限界法的基本思想,路径查找终止条件该节点的边界值超越目前目标函数的界。该节点无法代表任何可行解，因为它已违反了问题的约束。,22,6.1分支限界法的基本思想,6.1 分支限界法的基本思想,在问题的边带权解空间树中进行广度优先搜索。找一个答案结点使对应路径权最小。当搜索到一个扩展结点时，一次性扩展它的所有儿子，将满足约束条件且最小耗费函数目标函数限界的儿子，插入活结点表中，再从活结点表中取下一结点同样扩展，直到找到所需的解或活动结点表为空。

12、,（用于求解最优化问题）,结点x的最小耗费函数c(x):以x为根的子树所包含的答案结点中，路径权最小者的权值。若x是答案结点,则c(x)为该点的目标函数值;若x是根结点,则c(x)为最优解值。c(x)为单调递增函数。,通常采用优先队列方式组织，c(x)小者优先。,目标函数限界U:初始U可取，若x*是任一答案结点，且c(x*)U时，x将不必扩展（剪枝）。,活动结点表:,6.1 分支限界法的基本思想,（用于求解最优化问题）,1.确定解空间结构；2.确定约束条件和目标函数；3.取U=U(T)；4.扩展根结点的所有儿子，对每一子结点x判定其是否满足约束 条件，对满足约束条件的 x 计算,将 U的x 加

13、入活 结点表；5.x为叶结点时，检查是否c(x)U，是，则用c(x)更新U；6.取活结点表中的第一个结点为根,重复4。,解题步骤,最小耗费函数c(x)的估算:c(x)不能即时求得,为此取能即时计算的下界函数 代替,应具有单调性,且在答案结点上=c(x),6.1 分支限界法的基本思想,6.2 0-1背包问题(0-1 Knapsack Problem),问题描述,背包问题中的xj限定只能取0或1值，用KNAP(1,j,X)来表示这个问题,效益值,背包容量,则0/1背包问题就是KNAP(1,n,M),6.2 0-1背包问题(0-1 Knapsack Problem),首先把物品按照P(i)/W(i)

14、P(i+1)/W(i+1)的衡量标准排序，以此顺序读入物品。并且定义一个大小为物品多少的解向量X，X的一个分量就代表某个物品的装入情况。,背包问题的贪心算法及说明,问题描述 设有n个物体和一个背包，物体i的重量为wi，价值为pi，背包的载荷为M，找一个装载方案，使得能放入背包的物体总价值最高。,算法思路将问题的解表示为n元向量:x1,.xn,xi0,1 用排序树表示解空间,在树中做广度优先搜索,约束条件:M;目标函数:;目标函数限界初值:U=0；c(x):以x为根的子树所包含的叶子中，路径权值最大者；:以x为根的子树的部分路径的权值。,6.2 0-1背包问题(0-1 Knapsack Prob

15、lem),算法的思想,首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列。,对于优先队列分支限界法，结点的优先级由已装袋的物品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值和。,算法首先检查当前扩展结点的左儿子结点的可行性。如果该左儿子结点是可行结点，则将它加入到子集树和活结点优先队列中。当前扩展结点的右儿子结点一定是可行结点，仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列。当扩展到叶结点时为问题的最优值。,6.2 0-1背包问题(0-1 Knapsack Problem),算法的思想,算法首先检查当前扩展结点的左儿子结点的可行性。如果该左儿子结点是可

16、行结点，则将它加入到子集树和活结点优先队列中。当前扩展结点的右儿子结点一定是可行结点，仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列。当扩展到叶结点时为问题的最优值。,6.2 0-1背包问题(0-1 Knapsack Problem),为了便于计算上界函数，可以先将物品按照其单位重量价值从大到小排序，此后只要顺序考察各个物品即可。在实现时，有函数Bound来计算当前结点处的上界。在解空间树的当前扩展结点处，仅当要进入右子树时才计算上界函数Bound，以判断是否可以将右子树剪去。进入左子树时不需要计算上界，因为其上界与其父结点的上界相同。,0/1背包的分支限界法过程,问题描述,物品

17、 重(w)价(v)价/重(v/w),1 4 40 10 2 7 42 6 3 5 25 5 4 3 12 4,容量w=10,贪心法的解(1,0,0,0)，价值为40，可作为0/1背包的下界。,6.2 0-1背包问题(0-1 Knapsack Problem),0/1背包的分支限界法过程,求解过程,上界up可用最好情况来代替up=w*(v1/w1)=10*10=100目标函数的界40,100，一般解空间树中第i层的各结点，代表对物1i的选择，可这样定限界函数：up=V+(W-w)*(vi+1/wi+1),已装入价值,剩余容量,剩下物品最大单位价值vi+1/wi+1的积,6.2 0-1背包问题(0-1 Knapsack Problem),上界函数/以物品单位重量价值递减顺序装入物品while(i=n/b为上界函数,6.2 0-1背包问题(0-1 Knapsack Problem),