六章分支限界法-ppt课件

1、第六章第六章 分支限界法分支限界法 算法设计与算法设计与分析分析Design and Design and Analysis of Analysis of Computer Computer Algorithm Algorithm 信息工程学院信息工程学院张永梅张永梅学时分配学时分配 章章 节节内容内容讲授课时讲授课时上机课时上机课时考试考试第一第一章章绪论绪论4第二第二章章分治与递归分治与递归42第三第三章章贪心算法贪心算法42第四第四章章动态规划动态规划42第五第五章章回溯法回溯法42第六第六章章分支限界法分支限界法2合计合计2282 本课程成果由平常作业、上机实验和期末考试进展评定：考核

2、方法及成果评定规范考核方法及成果评定规范 平常作业：平常作业：10% 上机实验：上机实验：30% 期末考试：期末考试：60%，考试方式为开卷，考试方式为开卷第六章第六章 分支限界法分支限界法Branch-and-Bound1、根本要求、根本要求要求掌握分治限界法的根本思想，要求掌握分治限界法的根本思想，算法设计步骤，及常见问题的算法。算法设计步骤，及常见问题的算法。要求了解分支限界法的剪枝搜索战要求了解分支限界法的剪枝搜索战略。略。 2、教学内容、教学内容根本思想根本思想 0-1背包问题背包问题 第六章第六章 分支限界法分支限界法Branch-and-Bound6.1 分支限界法的根本思想分支

3、限界法的根本思想分支限界法与回溯法1求解目的：回溯法的求解目的是找出解空间树中求解目的：回溯法的求解目的是找出解空间树中满足约束条件的一切解，而分支限界法的求解目的那么满足约束条件的一切解，而分支限界法的求解目的那么是找出满足约束条件的一个解，或是在满足约束条件的是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。解中找出在某种意义下的最优解。 2搜索方式的不同：回溯法以深度优先的方式搜索解搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法那么以广度优先或以最小耗费优空间树，而分支限界法那么以广度优先或以最小耗费优先的方式搜索解空间树。先的方式搜索解空间

4、树。 回溯与分支限界是对穷举法的改良。回溯与分支限界是对穷举法的改良。 它们每次只构造候选解的一个分量，然后评价这个部分它们每次只构造候选解的一个分量，然后评价这个部分解：解： 假设加上剩下的分量也不能够求得一个解，就不再生成假设加上剩下的分量也不能够求得一个解，就不再生成剩下的分量。剩下的分量。 回溯法和分支限界都是以构造一棵形状空间树为根底，回溯法和分支限界都是以构造一棵形状空间树为根底，树的节点反映了对一个部分解所做的特定的选择。树的节点反映了对一个部分解所做的特定的选择。6.1 分支限界法的根本思想分支限界法的根本思想分支限界法与回溯法 有两种生成问题形状的根本方法。它们都是从根结点有

5、两种生成问题形状的根本方法。它们都是从根结点开场然后生成形状空间树上的其它结点。开场然后生成形状空间树上的其它结点。 6.1 分支限界法的根本思想分支限界法的根本思想 假设已生成一个结点而它的一切儿子结点还没有全部假设已生成一个结点而它的一切儿子结点还没有全部生成，那么这个结点叫做活结点生成，那么这个结点叫做活结点Live node。当前正。当前正在生成其儿子结点的活结点叫在生成其儿子结点的活结点叫E-结点正在扩展的结结点正在扩展的结点点,Expanded node。不再进一步扩展或者其儿子结点已。不再进一步扩展或者其儿子结点已全部生成的结点就是死结点全部生成的结点就是死结点Dead node

6、。n在生成问题形状的两种方法中，都要有一张活结点表。问在生成问题形状的两种方法中，都要有一张活结点表。问题形状的生成可以采用两种不同的方法：题形状的生成可以采用两种不同的方法：n假设对一个假设对一个E-结点结点R一旦生成了它的一个新的儿子一旦生成了它的一个新的儿子C，就，就把把C当作新的扩展结点，在完成对子树当作新的扩展结点，在完成对子树C以以C为根的子为根的子树的穷尽搜索之后。将树的穷尽搜索之后。将R结点重新变成结点重新变成 E-结点，继续生结点，继续生成成R的下一个儿子假设存在。这称做深度优先的问题的下一个儿子假设存在。这称做深度优先的问题形状生成法。形状生成法。n在另一种形状生成方法中，

7、一个在另一种形状生成方法中，一个E-结点不断坚持到变成死结点不断坚持到变成死结点为止。即在一个结点为止。即在一个E-结点变成死结点之前，它不断是扩结点变成死结点之前，它不断是扩展结点。这实践上是一种宽度优先的问题形状生成法。展结点。这实践上是一种宽度优先的问题形状生成法。6.1 分支限界法的根本思想分支限界法的根本思想 广度优先遍历广度优先遍历(BFS) 方法：从图的某一顶点方法：从图的某一顶点V0出发，访问此顶点后，依出发，访问此顶点后，依次访问次访问V0的各个未曾访问过的邻接点；然后分别从的各个未曾访问过的邻接点；然后分别从这些邻接点出发，广度优先遍历图，直至图中一切这些邻接点出发，广度优

8、先遍历图，直至图中一切已被访问的顶点的邻接点都被访问到；假设此时图已被访问的顶点的邻接点都被访问到；假设此时图中尚有顶点未被访问，那么另选图中一个未被访问中尚有顶点未被访问，那么另选图中一个未被访问的顶点作起点，反复上述过程，直至图中一切顶点的顶点作起点，反复上述过程，直至图中一切顶点都被访问为止。都被访问为止。V1V2V4V5V3V7V6V8例例广度遍历：广度遍历：V1 V2 V3 V4 V5 V6 V7 V86.1 分支限界法的根本思想分支限界法的根本思想在这两种方法中，为了防止生成那些不能够产生最正确解或所需解的问题形状，将用限界函数去杀死那些实践上不能够产生所需解的活结点，以减少问题的

9、计算任务量。这样做要非常小心，以使得在处置终了时至少能生成一个答案结点；假设这个问题要求找出全部解，那么要能生成一切的答案结点。运用限界函数的深度优先结点生成方法称为回溯法backtracking。E-结点不断坚持到死为止的形状生成方法导致分枝-限界方法branch-and-bound。6.1 分支限界法的根本思想分支限界法的根本思想6.1 分支限界法的根本思想分支限界法的根本思想 分支限界法常以广度优先或以最小耗费最大效益优先的方式搜索问题的解空间树。对已处置的各结点根据限界函数估算目的函数的能够取值，从中选取使目的函数获得极值极大/极小的结点优先进展广度优先搜索不断调整搜索方向，尽快找到解

10、。 特点：限界函数常基于问题的目的函数，适用特点：限界函数常基于问题的目的函数，适用于求解最优化问题。于求解最优化问题。6.1 分支限界法的根本思想分支限界法的根本思想 分支限界法常以广度优先或以最小耗费最大效益优先的方式搜索问题的解空间树。 以后，从活结点表中取下一结点成为当前扩展结点，并以后，从活结点表中取下一结点成为当前扩展结点，并反复上述结点扩展过程。这个过程不断继续到找到所需的解反复上述结点扩展过程。这个过程不断继续到找到所需的解或活结点表为空时为止。或活结点表为空时为止。 在分支限界法中，每一个活结点只需一次时机成为扩展结点。活结点一旦成为扩展结点，就一次性产生其一切儿子结点。在这

11、些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其他儿子结点被参与活结点表中。分支限界法是最正确优先搜索分支限界法是最正确优先搜索法法 分支限界法就是最正确优先包括广度优先在分支限界法就是最正确优先包括广度优先在内的搜索法。内的搜索法。 分支限界法将要搜索的结点按评价函数的优劣分支限界法将要搜索的结点按评价函数的优劣排序，让好的结点优先搜索，将坏的结点剪去。排序，让好的结点优先搜索，将坏的结点剪去。所以准确说，此方法应称为界限剪支法。所以准确说，此方法应称为界限剪支法。 分支限界法中有两个要点：分支限界法中有两个要点：n评价函数的构造；评价函数的构造；n搜索途径的构造。搜索途径的构造

12、。6.1 分支限界法的根本思想分支限界法的根本思想评价函数的构造评价函数的构造 评价函数要可以提供一个评定候选扩展结点的评价函数要可以提供一个评定候选扩展结点的方法，以便确定哪个结点最有能够在通往目的方法，以便确定哪个结点最有能够在通往目的的最正确途径上。的最正确途径上。6.1 分支限界法的根本思想分支限界法的根本思想搜索途径的构造搜索途径的构造 在回溯法中，每次仅调查一条途径，因在回溯法中，每次仅调查一条途径，因此只需求构造这一条途径即可：前进时此只需求构造这一条途径即可：前进时记下相应结点，回溯时删去最末尾结点记下相应结点，回溯时删去最末尾结点的记录。这比较容易实现。的记录。这比较容易实现

13、。 在分支限界法中，是同时调查假设干条在分支限界法中，是同时调查假设干条途径，那么又该如何构造搜索的途径呢？途径，那么又该如何构造搜索的途径呢？n对每一个扩展的结点，建立三个信息：对每一个扩展的结点，建立三个信息：n(1)该结点的称号；该结点的称号；n(2)它的评价函数值；它的评价函数值；n(3)指向其前驱的指针；指向其前驱的指针；n这样一旦找到目的，即可逆向构造其途径。这样一旦找到目的，即可逆向构造其途径。6.1 分支限界法的根本思想分支限界法的根本思想界限界限(Bounding) 评价函数评价函数f(d)关系着算法的效率乃至成败。关系着算法的效率乃至成败。 由于在大多数问题中由于在大多数问

14、题中f(d)只是个估计值，所以单只是个估计值，所以单靠靠f(d)是不够的。通常还要设计它的上、下界函是不够的。通常还要设计它的上、下界函数数U(d)和和L(d)。 L(d)f(d)U(d)。 所谓分支限界法就是经过评价函数及其上、下所谓分支限界法就是经过评价函数及其上、下界函数的计算，将形状空间中不能够产生最正界函数的计算，将形状空间中不能够产生最正确解的子树剪去，减少搜索的范围，提高效率。确解的子树剪去，减少搜索的范围，提高效率。因此更准确的称谓应是因此更准确的称谓应是“界限剪支法。界限剪支法。6.1 分支限界法的根本思想分支限界法的根本思想对评价函数的讨论对评价函数的讨论 分支限界法总耗时

15、为分支限界法总耗时为O(n22n)，它与回溯法、动态，它与回溯法、动态规划法等在时间复杂性上没有本质的区别。规划法等在时间复杂性上没有本质的区别。 然而，假设评价函数选择得好，采用分支限界法能然而，假设评价函数选择得好，采用分支限界法能够有一个小得多的常数因子。够有一个小得多的常数因子。 好的评价函数应该有一个尽能够高的下界估计和一好的评价函数应该有一个尽能够高的下界估计和一个尽能够低的上界估计，从而使得搜索空间可以得个尽能够低的上界估计，从而使得搜索空间可以得到有效的紧缩，从而提高效率。到有效的紧缩，从而提高效率。 在实际上可以证明好的评价函数所搜索的结点不会在实际上可以证明好的评价函数所搜

16、索的结点不会多于坏的评价函数所搜索的结点。多于坏的评价函数所搜索的结点。6.1 分支限界法的根本思想分支限界法的根本思想6.1 分支限界法的根本思想分支限界法的根本思想常见的两种分支限界法1队列式队列式(FIFO)分支限界法分支限界法 按照队列先进先出按照队列先进先出FIFO原那么选取下原那么选取下一个节点为扩展节点。一个节点为扩展节点。 2优先队列式分支限界法优先队列式分支限界法 按照优先队列中规定的优先级选取优先级按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。最高的节点成为当前扩展节点。最大优先队列：运用最大堆，表达最大效益优先最大优先队列：运用最大堆，表达最大效益优先最

17、小优先队列：运用最小堆，表达最小费用优先最小优先队列：运用最小堆，表达最小费用优先解空间树的动态搜索 利用回溯法求解问题，虽然剪枝减少了搜索空利用回溯法求解问题，虽然剪枝减少了搜索空间，但整个搜索按深度优先机械进展，是盲目搜索间，但整个搜索按深度优先机械进展，是盲目搜索不可预测本结点以下的结点进展得如何。不可预测本结点以下的结点进展得如何。6.1 分支限界法的根本思想分支限界法的根本思想解空间树的动态搜索 分支限界法首先确定一个合理的限界函数，并根分支限界法首先确定一个合理的限界函数，并根据限界函数确定目的函数的界据限界函数确定目的函数的界down, up； 然后按照广度优先战略遍历问题的解空

18、间树，在然后按照广度优先战略遍历问题的解空间树，在某一分支上，依次搜索该结点的一切孩子结点，分别某一分支上，依次搜索该结点的一切孩子结点，分别估算这些孩子结点的目的函数的能够取值对最小化估算这些孩子结点的目的函数的能够取值对最小化问题，估算结点的问题，估算结点的down，对最大化问题，估算结点的，对最大化问题，估算结点的up。 假设某孩子结点的目的函数值超出目的函数的界，假设某孩子结点的目的函数值超出目的函数的界，那么将其丢弃从此结点生成的解不会比目前已得到那么将其丢弃从此结点生成的解不会比目前已得到的更好，否那么入待处置表。的更好，否那么入待处置表。6.1 分支限界法的根本思想分支限界法的根

19、本思想 途径查找终止条件途径查找终止条件 该节点的边境值超越目前目的函数的界。该节点的边境值超越目前目的函数的界。 该节点无法代表任何可行解，由于它已违反该节点无法代表任何可行解，由于它已违反了问题的约束。了问题的约束。226.1 分支限界法的根本思想分支限界法的根本思想6.1 分支限界法的根本思想分支限界法的根本思想 在问题的边带权解空间树中进展广度优先搜索。找一个答在问题的边带权解空间树中进展广度优先搜索。找一个答案结点使对应途径权最小。当搜索到一个扩展结点时，一次性案结点使对应途径权最小。当搜索到一个扩展结点时，一次性扩展它的一切儿子，将满足约束条件且最小耗费函数扩展它的一切儿子，将满足

20、约束条件且最小耗费函数目的函目的函数限界的儿子，插入活结点表中，再从活结点表中取下一结点数限界的儿子，插入活结点表中，再从活结点表中取下一结点同样扩展，同样扩展， 直到找到所需的解或活动结点表为空。直到找到所需的解或活动结点表为空。用于求解最优化问题用于求解最优化问题 结点结点x的最小耗费函数的最小耗费函数c(x):以以x为根的子树所包含的答案结为根的子树所包含的答案结点中，途径权最小者的权值。假设点中，途径权最小者的权值。假设x是答案结点是答案结点, 那么那么c(x)为该为该点的目的函数值点的目的函数值; 假设假设x是根结点是根结点, 那么那么c(x)为最优解值。为最优解值。c(x)为为单调

21、递增函数。单调递增函数。通常采用优先队列方式组织，通常采用优先队列方式组织， c(x)小者优先。小者优先。目的函数限界目的函数限界U: 初始初始U可取可取，假设，假设x*是任一答案结点，且是任一答案结点，且c(x*)U时，时， x将不用扩展剪枝。将不用扩展剪枝。活动结点表活动结点表: :6.1 分支限界法的根本思想分支限界法的根本思想用于求解最优化问题用于求解最优化问题1.确定解空间构造；确定解空间构造；2.确定约束条件和目的函数；确定约束条件和目的函数；3.取取U=U(T)；4.扩展根结点的一切儿子，对每一子结点扩展根结点的一切儿子，对每一子结点x断定其能否满足约束断定其能否满足约束 条件，

22、对满足约束条件的条件，对满足约束条件的 x 计算计算 , 将将 U的的x 参与活参与活 结点表；结点表；5. x为叶结点时，检查能否为叶结点时，检查能否c(x)U， 是，那么用是，那么用c(x)更新更新U；6. 取活结点表中的第一个结点为根取活结点表中的第一个结点为根, 反复反复4。 解题步骤解题步骤 最小耗费函数最小耗费函数c(x)的估算的估算: c(x)不能即时求得不能即时求得, 为此取能即时为此取能即时计算的下界函数计算的下界函数 替代替代, 应具有单调性应具有单调性, 且在答案结点且在答案结点上上 =c(x) )( (xc) )( (xc) )( (xc) )( (xc) )( (xc

23、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)P(i+1)/W(i+1)的衡量规范排序，以此顺序读入物品。并且定义一个大小为物品多少的解向量X，X的一个分量就代表某个物品的装入情况。背包

24、问题的贪婪算法及阐明背包问题的贪婪算法及阐明 问题描画问题描画 设有设有n n个物体和一个背包，物体个物体和一个背包，物体i i的分量为的分量为wi wi ， 价值为价值为pi pi ，背包的载荷为，背包的载荷为M M，找一个装载方案，使得能放入，找一个装载方案，使得能放入背包的物体总价值最高。背包的物体总价值最高。 算法思绪算法思绪 将问题的解表示为将问题的解表示为n n元向量元向量:x1, . xn , :x1, . xn , xixi0,1 0,1 用排序树表示解空间用排序树表示解空间, , 在树中做广度优先搜索在树中做广度优先搜索, ,约束条件约束条件: M ;: M ;目的函数目的函

25、数: ; : ; 目的函数限界初值目的函数限界初值:U=0:U=0；c(x):c(x):以以x x为根的子树所包含的叶子中，途径权值最大者；为根的子树所包含的叶子中，途径权值最大者； : :以以x x为根的子树的部分途径的权值。为根的子树的部分途径的权值。iinixp1iniixw16.2 0-1背包问题背包问题 (0-1 Knapsack Problem) )( (xc算法的思想 首先，要对输入数据进展预处置，将各物品依其单位分量价值从大到小进展陈列。 对于优先队列分支限界法，结点的优先级由已装袋的物品价值加上剩下的最大单位分量价值的物品装满剩余容量的价值和。 算法首先检查当前扩展结点的左儿

26、子结点的可行性。假设该左儿子结点是可行结点，那么将它参与到子集树和活结点优先队列中。当前扩展结点的右儿子结点一定是可行结点，仅当右儿子结点满足上界约束时才将它参与子集树和活结点优先队列。当扩展到叶结点时为问题的最优值。6.2 0-1背包问题背包问题 (0-1 Knapsack Problem)算法的思想 算法首先检查当前扩展结点的左儿子结点的可行性。假设该左儿子结点是可行结点，那么将它参与到子集树和活结点优先队列中。当前扩展结点的右儿子结点一定是可行结点，仅当右儿子结点满足上界约束时才将它参与子集树和活结点优先队列。当扩展到叶结点时为问题的最优值。6.2 0-1背包问题背包问题 (0-1 Knapsack Problem) 为了便于计算上界函数，可以先将物品按照其单位分量价值从大到小排序，以后只需顺序