六章分支限界法

《六章分支限界法》由会员分享，可在线阅读，更多相关《六章分支限界法（33页珍藏版）》请在装配图网上搜索。

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

2、平时作业：10%上机实验上机实验：30%期末考试期末考试：60%，考试形式为开卷，考试形式为开卷第六章第六章 分支限界法分支限界法（Branch-and-Bound）1、基本要求、基本要求要求掌握分治限界法的基本思想，算法设计要求掌握分治限界法的基本思想，算法设计步骤，及常见问题的算法。步骤，及常见问题的算法。要求理解分支限界法的剪枝搜索策略。要求理解分支限界法的剪枝搜索策略。2、教学内容、教学内容l基本思想基本思想 l 0-1背包问题背包问题 第六章第六章 分支限界法分支限界法（Branch-and-Bound）6.1 分支限界法的基本思想分支限界法的基本思想分支限界法与回溯法（1）求解目标

3、：回溯法的求解目标是找出解空间树中）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。中找出在某种意义下的最优解。（2）搜索方式的不同：回溯法以深度优先的方式搜索解）搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。的方式搜索解空间树。回溯与分支限界是对穷举法的改进。回溯与分支

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

5、成状态空间树上的其它结点。开始然后生成状态空间树上的其它结点。6.1 分支限界法的基本思想分支限界法的基本思想 如果已生成一个结点而它的所有儿子结点还没有全部如果已生成一个结点而它的所有儿子结点还没有全部生成，则这个结点叫做生成，则这个结点叫做活结点（活结点（Live node）。当前正在。当前正在生成其儿子结点的活结点叫生成其儿子结点的活结点叫E-结点结点（正在扩展的结（正在扩展的结点点,Expanded node）。不再进一步扩展或者其儿子结点已）。不再进一步扩展或者其儿子结点已全部生成的结点就是全部生成的结点就是死结点死结点（Dead node）。）。n在生成问题状态的两种方法中，都要有

6、一张活结点表。在生成问题状态的两种方法中，都要有一张活结点表。问问题状态的生成可以采用两种不同的方法：题状态的生成可以采用两种不同的方法：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 分支限界法的基本思想分支限界法的基本思想n在这两种方法中，为了避免生成那些不可能产生最佳解在这两种方法中，为了避免生成那些不可能产生最佳解（或所需解）的问题状态，将用（或所需解）的问题状态，将用限界函数限界函数去

9、杀死那些实去杀死那些实际上不可能产生所需解的活结点，以减少问题的计算工际上不可能产生所需解的活结点，以减少问题的计算工作量。作量。n这样做要非常小心，以使得在处理结束时至少能生成一这样做要非常小心，以使得在处理结束时至少能生成一个答案结点；如果这个问题要求找出全部解，则要能生个答案结点；如果这个问题要求找出全部解，则要能生成所有的答案结点。使用限界函数的深度优先结点生成成所有的答案结点。使用限界函数的深度优先结点生成方法称为方法称为回溯法回溯法（backtracking）。）。nE-结点一直保持到死为止的状态生成方法导致结点一直保持到死为止的状态生成方法导致分枝分枝-限限界方法界方法（bran

10、ch-and-bound）。6.1 分支限界法的基本思想分支限界法的基本思想6.1 分支限界法的基本思想分支限界法的基本思想 分支限界法常以广度优先或以最小耗费（最分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。对已处大效益）优先的方式搜索问题的解空间树。对已处理的各结点根据限界函数估算目标函数的可能取值，理的各结点根据限界函数估算目标函数的可能取值，从中选取使目标函数取得极值（极大从中选取使目标函数取得极值（极大/极小）的结极小）的结点优先进行点优先进行广度广度优先搜索优先搜索不断调整搜索方向，尽不断调整搜索方向，尽快找到解。快找到解。特点：特点：限界函数常基于问

11、题的目标函数，适用限界函数常基于问题的目标函数，适用于求解最优化问题。于求解最优化问题。6.1 分支限界法的基本思想分支限界法的基本思想 分支限界法常以广度优先或以最小耗费（最大效益）优分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。先的方式搜索问题的解空间树。此后，从活结点表中取下一结点成为当前扩展结点，并此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止或活结点表为空时为止。在分支限界法中，每一个活结点只有一次机会成为扩展在分支限界法中，每一

12、个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。结点。在这些儿子结点中，导致不可行解或导致非最优解的在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。儿子结点被舍弃，其余儿子结点被加入活结点表中。分支限界法是最佳优先搜索法分支限界法是最佳优先搜索法 分支限界法就是最佳优先（包括广度优先在内）分支限界法就是最佳优先（包括广度优先在内）的搜索法。的搜索法。分支限界法将要搜索的结点按评价函数的优劣分支限界法将要搜索的结点按评价函数的优劣排序，让好的结点优先搜索，将坏的结

13、点剪去。排序，让好的结点优先搜索，将坏的结点剪去。所以准确说，此方法应称为界限剪支法。所以准确说，此方法应称为界限剪支法。分支限界法中有两个要点：分支限界法中有两个要点：n评价函数的构造；评价函数的构造；n搜索路径的构造。搜索路径的构造。6.1 分支限界法的基本思想分支限界法的基本思想评价函数的构造评价函数的构造 评价函数要能够提供一个评定候选扩展结点的评价函数要能够提供一个评定候选扩展结点的方法，以便确定哪个结点最有可能在通往目标方法，以便确定哪个结点最有可能在通往目标的最佳路径上。的最佳路径上。6.1 分支限界法的基本思想分支限界法的基本思想搜索路径的构造搜索路径的构造 在回溯法中，每次仅

14、考察一条路径，因在回溯法中，每次仅考察一条路径，因而只需要构造这一条路径即可：前进时而只需要构造这一条路径即可：前进时记下相应结点，回溯时删去最末尾结点记下相应结点，回溯时删去最末尾结点的记录。这比较容易实现。的记录。这比较容易实现。在分支限界法中，是同时考察若干条路在分支限界法中，是同时考察若干条路径，那么又该如何构造搜索的路径呢？径，那么又该如何构造搜索的路径呢？n对每一个扩展的结点，建立三个信息：对每一个扩展的结点，建立三个信息：n(1)该结点的名称；该结点的名称；n(2)它的评价函数值；它的评价函数值；n(3)指向其前驱的指针；指向其前驱的指针；n这样一旦找到目标，即可逆向构造其路径。

15、这样一旦找到目标，即可逆向构造其路径。6.1 分支限界法的基本思想分支限界法的基本思想界限界限(Bounding)评价函数评价函数f(d)关系着算法的效率乃至成败。关系着算法的效率乃至成败。因为在大多数问题中因为在大多数问题中f(d)只是个估计值，所以单只是个估计值，所以单靠靠f(d)是不够的。通常还要设计它的上、下界函是不够的。通常还要设计它的上、下界函数数U(d)和和L(d)。L(d)f(d)U(d)。所谓分支限界法就是通过评价函数及其上、下所谓分支限界法就是通过评价函数及其上、下界函数的计算，将状态空间中不可能产生最佳界函数的计算，将状态空间中不可能产生最佳解的子树剪去，减少搜索的范围，

16、提高效率。解的子树剪去，减少搜索的范围，提高效率。因而更准确的称呼应是因而更准确的称呼应是“界限剪支法界限剪支法”。6.1 分支限界法的基本思想分支限界法的基本思想对评价函数的讨论对评价函数的讨论 分支限界法总耗时为分支限界法总耗时为O(n22n)，它与回溯法、动态，它与回溯法、动态规划法等在时间复杂性上没有本质的区别。规划法等在时间复杂性上没有本质的区别。然而，如果评价函数选择得好，采用分支限界法可然而，如果评价函数选择得好，采用分支限界法可能有一个小得多的常数因子。能有一个小得多的常数因子。好的评价函数应该有一个尽可能高的下界估计和一好的评价函数应该有一个尽可能高的下界估计和一个尽可能低的

17、上界估计，从而使得搜索空间能够得个尽可能低的上界估计，从而使得搜索空间能够得到有效的压缩，从而提高效率。到有效的压缩，从而提高效率。在理论上可以证明好的评价函数所搜索的结点不会在理论上可以证明好的评价函数所搜索的结点不会多于坏的评价函数所搜索的结点。多于坏的评价函数所搜索的结点。6.1 分支限界法的基本思想分支限界法的基本思想6.1 分支限界法的基本思想分支限界法的基本思想常见的两种分支限界法（1）队列式）队列式(FIFO)分支限界法分支限界法 按照队列先进先出（按照队列先进先出（FIFO）原则选取下一个节点）原则选取下一个节点为扩展节点。为扩展节点。（2）优先队列式分支限界法）优先队列式分支

18、限界法 按照优先队列中规定的优先级选取优先级最高的节按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。点成为当前扩展节点。最大优先队列：使用最大堆，体现最大效益优先最大优先队列：使用最大堆，体现最大效益优先最小优先队列：使用最小堆，体现最小费用优先最小优先队列：使用最小堆，体现最小费用优先解空间树的动态搜索 利用回溯法求解问题，虽然剪枝减少了搜索空利用回溯法求解问题，虽然剪枝减少了搜索空间，但整个搜索按深度优先机械进行，是盲目搜索间，但整个搜索按深度优先机械进行，是盲目搜索（不可预测本结点以下的结点进行得如何）。（不可预测本结点以下的结点进行得如何）。6.1 分支限界法的基本思想

19、分支限界法的基本思想解空间树的动态搜索 分支限界法分支限界法首先首先确定一个合理的限界函数，并根确定一个合理的限界函数，并根据限界函数确定目标函数的界据限界函数确定目标函数的界down,up；然后然后按照广度优先策略遍历问题的解空间树，在按照广度优先策略遍历问题的解空间树，在某一分支上，依次搜索该结点的所有孩子结点，分别某一分支上，依次搜索该结点的所有孩子结点，分别估算这些孩子结点的目标函数的可能取值（对最小化估算这些孩子结点的目标函数的可能取值（对最小化问题，估算结点的问题，估算结点的down，对最大化问题，估算结点的，对最大化问题，估算结点的up）。）。如果某孩子结点的目标函数值超出目标函

20、数的界，如果某孩子结点的目标函数值超出目标函数的界，则将其丢弃（从此结点生成的解不会比目前已得到的则将其丢弃（从此结点生成的解不会比目前已得到的更好），否则入待处理表。更好），否则入待处理表。6.1 分支限界法的基本思想分支限界法的基本思想 路径查找终止条件路径查找终止条件 该节点的边界值超越目前目标函数的界。该节点的边界值超越目前目标函数的界。该节点无法代表任何可行解，因为它已违反了问该节点无法代表任何可行解，因为它已违反了问题的约束。题的约束。226.1 分支限界法的基本思想分支限界法的基本思想6.1 分支限界法的基本思想分支限界法的基本思想 在问题的边带权解空间树中进行在问题的边带权解空

21、间树中进行广度优先搜索广度优先搜索。找一个答找一个答案结点使对应路径权最小。案结点使对应路径权最小。当搜索到一个扩展结点时，一当搜索到一个扩展结点时，一次性扩展它的所有儿子，将满足约束条件且次性扩展它的所有儿子，将满足约束条件且最小耗费函数最小耗费函数 目标目标函数限界函数限界的儿子，插入的儿子，插入活结点表活结点表中，再从活结点表中取下一结中，再从活结点表中取下一结点同样扩展，点同样扩展，直到找到所需的解或活动结点表为空。直到找到所需的解或活动结点表为空。（用于求解最优化问题）（用于求解最优化问题）结点结点x的最小耗费函数的最小耗费函数c(x):以以x为根的子树所包含的答案结为根的子树所包含

22、的答案结点中，路径权最小者的权值。若点中，路径权最小者的权值。若x是答案结点是答案结点,则则c(x)为该点的为该点的目标函数值目标函数值;若若x是根结点是根结点,则则c(x)为最优解值。为最优解值。c(x)为单调递增为单调递增函数。函数。通常采用优先队列方式组织，通常采用优先队列方式组织，c(x)小者优先。小者优先。目标函数限界目标函数限界U:初始初始U可取可取，若若x*是任一答案结点，且是任一答案结点，且c(x*)U时，时，x将不必扩展（剪枝）。将不必扩展（剪枝）。活动结点表活动结点表:6.1 分支限界法的基本思想分支限界法的基本思想（用于求解最优化问题）（用于求解最优化问题）1.确定解空间

23、结构；确定解空间结构；2.确定约束条件和目标函数；确定约束条件和目标函数；3.取取U=U(T)；4.扩展根结点的所有儿子，对每一子结点扩展根结点的所有儿子，对每一子结点x判定其是否满足约束判定其是否满足约束 条件，对满足约束条件的条件，对满足约束条件的 x 计算计算 ,将将 U的的x 加入活加入活 结点表；结点表；5.x为叶结点时，检查是否为叶结点时，检查是否c(x)U，是，则用是，则用c(x)更新更新U；6.取活结点表中的第一个结点为根取活结点表中的第一个结点为根,重复重复4。解题步骤解题步骤 最小耗费函数最小耗费函数c(x)的估算的估算:c(x)不能即时求得不能即时求得,为此取能即时为此取

24、能即时计算的下界函数计算的下界函数 代替代替,应具有单调性应具有单调性,且在答案结点且在答案结点上上 =c(x)(xc)(xc)(xc)(xc)(xc6.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)

25、/W(i)P(i+1)/W(i+1)的衡量标准排序，的衡量标准排序，以此顺序读入物品。并且定义一个大小为物品多少的解向量以此顺序读入物品。并且定义一个大小为物品多少的解向量X，X的一个分量就代表某个物品的装入情况。的一个分量就代表某个物品的装入情况。背包问题的贪心算法及说明背包问题的贪心算法及说明 问题描述问题描述 设有设有n个物体和一个背包，物体个物体和一个背包，物体i的重量为的重量为wi，价值为价值为pi，背包的载荷为，背包的载荷为M，找一个装载方案，使得能放入，找一个装载方案，使得能放入背包的物体总价值最高。背包的物体总价值最高。算法思路算法思路 将问题的解表示为将问题的解表示为n元向量

26、元向量:x1,.xn,xi 0,1 用排序树表示解空间用排序树表示解空间,在树中做广度优先搜索在树中做广度优先搜索,约束条件约束条件:M ;目标函数目标函数:;目标函数限界初值目标函数限界初值:U=0；c(x):以以x为根的子树所包含的叶子中，路径权值最大者；为根的子树所包含的叶子中，路径权值最大者；:以以x为根的子树的部分路径的权值。为根的子树的部分路径的权值。iinixp1iniixw16.2 0-1背包问题背包问题(0-1 Knapsack Problem)(xc算法的思想 首先，要对输入数据进行预处理，将各物品依其单位重首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进行

27、排列。量价值从大到小进行排列。对于优先队列分支限界法，结点的优先级由已装袋的物对于优先队列分支限界法，结点的优先级由已装袋的物品价值加上剩下的最大单位重量价值的物品装满剩余容量的品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值和。价值和。算法首先检查当前扩展结点的左儿子结点的可行性。如算法首先检查当前扩展结点的左儿子结点的可行性。如果该左儿子结点是可行结点，则将它加入到子集树和活结点果该左儿子结点是可行结点，则将它加入到子集树和活结点优先队列中。当前扩展结点的右儿子结点一定是可行结点，优先队列中。当前扩展结点的右儿子结点一定是可行结点，仅当右儿子结点满足上界约束时才将它加入子集树和活结

28、点仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列。优先队列。当扩展到叶结点时为问题的最优值。当扩展到叶结点时为问题的最优值。6.2 0-1背包问题背包问题(0-1 Knapsack Problem)算法的思想 算法首先检查当前扩展结点的左儿子结点的可行性。如算法首先检查当前扩展结点的左儿子结点的可行性。如果该左儿子结点是可行结点，则将它加入到子集树和活结点果该左儿子结点是可行结点，则将它加入到子集树和活结点优先队列中。当前扩展结点的右儿子结点一定是可行结点，优先队列中。当前扩展结点的右儿子结点一定是可行结点，仅当右儿子结点满足上界约束时才将它加入子集树和活结点仅当右儿子结点满足上

29、界约束时才将它加入子集树和活结点优先队列。优先队列。当扩展到叶结点时为问题的最优值。当扩展到叶结点时为问题的最优值。6.2 0-1背包问题背包问题(0-1 Knapsack Problem)为了便于计算上界函数，可以先将物品按照其单位重量为了便于计算上界函数，可以先将物品按照其单位重量价值从大到小排序，此后只要顺序考察各个物品即可。在实价值从大到小排序，此后只要顺序考察各个物品即可。在实现时，有函数现时，有函数Bound来计算当前结点处的上界。在解空间树来计算当前结点处的上界。在解空间树的当前扩展结点处，仅当要进入右子树时才计算上界函数的当前扩展结点处，仅当要进入右子树时才计算上界函数Boun

30、d，以判断是否可以将右子树剪去。进入左子树时不需，以判断是否可以将右子树剪去。进入左子树时不需要计算上界，因为其上界与其父结点的上界相同。要计算上界，因为其上界与其父结点的上界相同。0/1背包的分支限界法过程背包的分支限界法过程问题描述问题描述物品物品 重重(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背包的分支限界法过程背包的分支限界

31、法过程求解过程求解过程上界上界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&wi=cleft)/n表示物品总数，表示物品总数，cleft为剩余空间为剩余空间 cleft-=wi;/wi表示表示i所占空间所占空间 b+=pi;/pi表示表示i的价值的价值 i+;/装满背包装满背包if(i=n)b+=pi/wi*cleft;/装填剩余容量装满背包装填剩余容量装满背包return b;/b为上界函数为上界函数6.2 0-1背包问题背包问题(0-1 Knapsack Problem)