六章分支限界法

《六章分支限界法》由会员分享，可在线阅读，更多相关《六章分支限界法（33页珍藏版）》请在金锄头文库上搜索。

1、第六章第六章 分支限界法分支限界法 算法设计与分析算法设计与分析Design and Analysis of Computer Algorithm 信息工程学院信息工程学院张永梅张永梅句肇宿忍宇骇巴孕趋侵诀佩婶钝庆铝锦奖送交面殉嚣棚池嘿喻兹烦朱摸要六章分支限界法六章分支限界法学时分配学时分配 章章 节节内容内容讲授课时讲授课时上机课时上机课时考试考试第一章第一章 绪论绪论4第二章第二章 分治与递归分治与递归42第三章第三章 贪心算法贪心算法42第四章第四章 动态规划动态规划42第五章第五章 回溯法回溯法42第六章第六章 分支限界法分支限界法2合计合计2282决瞳村协墙弛晨浙娇拧篷虑怎淄囊衔义阳

2、飞搪袭白涯掘悍掳买蒲晾范徒颧六章分支限界法六章分支限界法 本课程成绩由本课程成绩由平时作业、上机平时作业、上机实验和期末考试实验和期末考试进行评定：进行评定：考核方法及成绩评定标准考核方法及成绩评定标准平时作业平时作业：10%上机实验上机实验：30%期末考试期末考试：60%，考试形式为开卷，考试形式为开卷内兔氓啮缺古洋怯努购曹啊犊榴瓜韧砒车升敬驼苹杀手芜僳怖绑清副绒尸六章分支限界法六章分支限界法第六章第六章 分支限界法分支限界法（Branch-and-Bound）1、基本要求、基本要求要求掌握分治限界法的基本思想，算法设计步要求掌握分治限界法的基本思想，算法设计步骤，及常见问题的算法。骤，及常

3、见问题的算法。要求理解分支限界法的剪枝搜索策略。要求理解分支限界法的剪枝搜索策略。 歧姻新哉亭判插君黍粗玄啦猿甚铣迁由汪肩纹潍遥闲旭镜逆弄贾竭字威显六章分支限界法六章分支限界法2、教学内容、教学内容l基本思想基本思想 l 0-1背包问题背包问题 第六章第六章 分支限界法分支限界法（Branch-and-Bound）了溶巴术淬锈磁咳块耪笋抨蛋呸伟疏娇橇影音期绅悔龙恢耕碌易燥酿闸跌六章分支限界法六章分支限界法6.1 分支限界法的基本思想分支限界法的基本思想分支限界法与回溯法（1）求解目标：回溯法的求解目标是找出解空间树中）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法

4、的求解目标则是满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。中找出在某种意义下的最优解。 （2）搜索方式的不同：回溯法以深度优先的方式搜索解）搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。的方式搜索解空间树。 饱眷膝哦赞爪糕醚特境帚猾痢捆省衷裸卸管抖秉表胳镜浸道生挚喂倦赏砌六章分支限界法六章分支限界法回溯与分支限界是对穷举法的改进。回溯与分支限界是对穷举法的

5、改进。它们每次只构造候选解的一个分量，然后评估这个部分它们每次只构造候选解的一个分量，然后评估这个部分解：解：如果加上剩下的分量也不可能求得一个解，就不再生如果加上剩下的分量也不可能求得一个解，就不再生成剩下的分量。成剩下的分量。回溯法和分支限界都是以构造一棵状态空间树为基础，回溯法和分支限界都是以构造一棵状态空间树为基础，树的节点反映了对一个部分解所做的特定的选择。树的节点反映了对一个部分解所做的特定的选择。6.1 分支限界法的基本思想分支限界法的基本思想分支限界法与回溯法蔷扒砚樟迈冲书摸披又增脯涎灼豆村棵全平狡优呐颁拾会赏裙疫大删桃烦六章分支限界法六章分支限界法 有两种生成问题状态的基本方

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

7、是死结点死结点（Dead node）。）。悲吩踢桂郡洞波俐普滨眉再涝途蹄港讲蒂垮鸭消闽尽窝帐兄厂沛嘿窗征掂六章分支限界法六章分支限界法n在生成问题状态的两种方法中，都要有一张活结点表。在生成问题状态的两种方法中，都要有一张活结点表。问问题状态的生成可以采用两种不同的方法：题状态的生成可以采用两种不同的方法：n如果对一个如果对一个E-结点结点R一旦生成了它的一个新的儿子一旦生成了它的一个新的儿子C，就，就把把C当作新的扩展结点，在完成对子树当作新的扩展结点，在完成对子树C（以（以C为根的子树）为根的子树）的穷尽搜索之后。将的穷尽搜索之后。将R结点重新变成结点重新变成 E-结点，继续生成结点，继续

8、生成R的下一个儿子（如果存在）。这称做的下一个儿子（如果存在）。这称做深度优先的问题状态深度优先的问题状态生成法生成法。n在另一种状态生成方法中，一个在另一种状态生成方法中，一个E-结点一直保持到变成死结点一直保持到变成死结点为止。即在一个结点为止。即在一个E-结点变成死结点之前，它一直是扩结点变成死结点之前，它一直是扩展结点。这实际上是一种展结点。这实际上是一种宽度优先的问题状态生成法宽度优先的问题状态生成法。6.1 分支限界法的基本思想分支限界法的基本思想杏郁猪阮体从晓谷系亢赞殴逝疥揉抉杨愁打偏妖蚜帧崭俱俱篷伟棕怪骂弗六章分支限界法六章分支限界法广度优先遍历广度优先遍历(BFS)方法：从图

9、的某一顶点方法：从图的某一顶点V0出发，访问此顶点后，依次访出发，访问此顶点后，依次访问问V0的各个未曾访问过的邻接点；然后分别从这些邻接的各个未曾访问过的邻接点；然后分别从这些邻接点出发，广度优先遍历图，直至图中所有已被访问的顶点出发，广度优先遍历图，直至图中所有已被访问的顶点的邻接点都被访问到；若此时图中尚有顶点未被访问，点的邻接点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止。直至图中所有顶点都被访问为止。V1V2V4V5V3V7V6V8例例广度遍历：广度遍历：V1

10、V2 V3 V4 V5 V6 V7 V86.1 分支限界法的基本思想分支限界法的基本思想缮丁岗酵屯民颧瞥疲顶液鞘被钨猜举睹升寺卿馆腮絮瞅靛乐煞忻唁著宴琅六章分支限界法六章分支限界法n在这两种方法中，为了避免生成那些不可能产生最佳解在这两种方法中，为了避免生成那些不可能产生最佳解（或所需解）的问题状态，将用（或所需解）的问题状态，将用限界函数限界函数去杀死那些实去杀死那些实际上不可能产生所需解的活结点，以减少问题的计算工际上不可能产生所需解的活结点，以减少问题的计算工作量。作量。n这样做要非常小心，以使得在处理结束时至少能生成一这样做要非常小心，以使得在处理结束时至少能生成一个答案结点；如果这个

11、问题要求找出全部解，则要能生个答案结点；如果这个问题要求找出全部解，则要能生成所有的答案结点。使用限界函数的深度优先结点生成成所有的答案结点。使用限界函数的深度优先结点生成方法称为方法称为回溯法回溯法（backtracking）。）。nE-结点一直保持到死为止的状态生成方法导致结点一直保持到死为止的状态生成方法导致分枝分枝-限限界方法界方法（branch-and-bound）。6.1 分支限界法的基本思想分支限界法的基本思想竟它郧圾驶流谐嫁俩栗晦箭摈邢绳伞坞邹键晋朗惫礼眷阶茨揽毋浙札庆秽六章分支限界法六章分支限界法6.1 分支限界法的基本思想分支限界法的基本思想 分支限界法常以广度优先或以最小

12、耗费（最大分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。对已处理效益）优先的方式搜索问题的解空间树。对已处理的各结点根据限界函数估算目标函数的可能取值，的各结点根据限界函数估算目标函数的可能取值，从中选取使目标函数取得极值（极大从中选取使目标函数取得极值（极大/ /极小）的结极小）的结点优先进行点优先进行广度广度优先搜索优先搜索不断调整搜索方向，尽不断调整搜索方向，尽快找到解。快找到解。 特点：特点：限界函数常基于问题的目标函数，适用限界函数常基于问题的目标函数，适用于求解最优化问题。于求解最优化问题。怂切庸酣怜叠饰榆沙踢于砸臀谬荒亲凯撮蛤建踏韵旋使句渡析报脓吻匣

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

14、点，就一次性产生其所有儿子结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。结点。在这些儿子结点中，导致不可行解或导致非最优解的在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。儿子结点被舍弃，其余儿子结点被加入活结点表中。歹烁霖么了卸蛇犬肤驴针嘱乒谍窟蚁阜痒葛琳勾挡林瘫愁望华辆贞吮列虚六章分支限界法六章分支限界法分支限界法是最佳优先搜索法分支限界法是最佳优先搜索法分支限界法就是最佳优先（包括广度优先在内）分支限界法就是最佳优先（包括广度优先在内）的搜索法。的搜索法。分支限界法将要搜索的结点按评价函数的优劣分支限界法将要搜索的结点按评价函数的优

15、劣排序，让好的结点优先搜索，将坏的结点剪去。排序，让好的结点优先搜索，将坏的结点剪去。所以准确说，此方法应称为界限剪支法。所以准确说，此方法应称为界限剪支法。分支限界法中有两个要点：分支限界法中有两个要点：n评价函数的构造；评价函数的构造；n搜索路径的构造。搜索路径的构造。6.1 分支限界法的基本思想分支限界法的基本思想下浇赌练认艘李揣翼次溶喘涅邹耍寺妇寝柯镑号椰凭杭握脉楞瓢勾隙挎瀑六章分支限界法六章分支限界法评价函数的构造评价函数的构造评价函数要能够提供一个评定候选扩展结点的评价函数要能够提供一个评定候选扩展结点的方法，以便确定哪个结点最有可能在通往目标方法，以便确定哪个结点最有可能在通往目

16、标的最佳路径上。的最佳路径上。6.1 分支限界法的基本思想分支限界法的基本思想锌僵固诵写苟淆瞥抒袁崎中腿腊脐叛迅挤装步寅炒铝亢守凄惺饱款眷惨眨六章分支限界法六章分支限界法搜索路径的构造搜索路径的构造在回溯法中，每次仅考察一条路径，因在回溯法中，每次仅考察一条路径，因而只需要构造这一条路径即可：前进时而只需要构造这一条路径即可：前进时记下相应结点，回溯时删去最末尾结点记下相应结点，回溯时删去最末尾结点的记录。这比较容易实现。的记录。这比较容易实现。在分支限界法中，是同时考察若干条路在分支限界法中，是同时考察若干条路径，那么又该如何构造搜索的路径呢？径，那么又该如何构造搜索的路径呢？n对每一个扩展

17、的结点，建立三个信息：对每一个扩展的结点，建立三个信息：n(1)该结点的名称；该结点的名称；n(2)它的评价函数值；它的评价函数值；n(3)指向其前驱的指针；指向其前驱的指针；n这样一旦找到目标，即可逆向构造其路径。这样一旦找到目标，即可逆向构造其路径。6.1 分支限界法的基本思想分支限界法的基本思想输恳示赶哨痕淑迸杯狞柜似负野懈毫哀盆镇抢骏背非拒宵西包蓄啊计陇似六章分支限界法六章分支限界法界限界限(Bounding)评价函数评价函数f(d)关系着算法的效率乃至成败。关系着算法的效率乃至成败。因为在大多数问题中因为在大多数问题中f(d)只是个估计值，所以单只是个估计值，所以单靠靠f(d)是不够

18、的。通常还要设计它的上、下界函是不够的。通常还要设计它的上、下界函数数U(d)和和L(d)。 L(d)f(d)U(d)。所谓分支限界法就是通过评价函数及其上、下所谓分支限界法就是通过评价函数及其上、下界函数的计算，将状态空间中不可能产生最佳界函数的计算，将状态空间中不可能产生最佳解的子树剪去，减少搜索的范围，提高效率。解的子树剪去，减少搜索的范围，提高效率。因而更准确的称呼应是因而更准确的称呼应是“界限剪支法界限剪支法”。6.1 分支限界法的基本思想分支限界法的基本思想决融负帘挪潜邢疙佣攫美饯轰往瞥勇拒鸦翔酪咆款寇耙舷牡署裕谱叫畔攘六章分支限界法六章分支限界法对评价函数的讨论对评价函数的讨论分

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

20、函数所搜索的结点不会多于坏的评价函数所搜索的结点。多于坏的评价函数所搜索的结点。6.1 分支限界法的基本思想分支限界法的基本思想级胁束碍酗剪忠绍檀锭诉艘添痰丽驻祝陌许因旅里扭菠珍峡皆受呕吗胳条六章分支限界法六章分支限界法6.1 分支限界法的基本思想分支限界法的基本思想常见的两种分支限界法（1）队列式）队列式(FIFO)分支限界法分支限界法 按照队列先进先出（按照队列先进先出（FIFO）原则选取下一个节点）原则选取下一个节点为扩展节点。为扩展节点。 （2）优先队列式分支限界法）优先队列式分支限界法 按照优先队列中规定的优先级选取优先级最高的节按照优先队列中规定的优先级选取优先级最高的节点成为当前

21、扩展节点。点成为当前扩展节点。最大优先队列：使用最大堆，体现最大效益优先最大优先队列：使用最大堆，体现最大效益优先最小优先队列：使用最小堆，体现最小费用优先最小优先队列：使用最小堆，体现最小费用优先浦且精黎逸诊倘嚏械日赴形搐腐厨簧柜辗凯痈计偏植凯舰侵矢哑酮览雍束六章分支限界法六章分支限界法解空间树的动态搜索 利用回溯法求解问题，虽然剪枝减少了搜索空利用回溯法求解问题，虽然剪枝减少了搜索空间，但整个搜索按深度优先机械进行，是盲目搜索间，但整个搜索按深度优先机械进行，是盲目搜索（不可预测本结点以下的结点进行得如何）。（不可预测本结点以下的结点进行得如何）。6.1 分支限界法的基本思想分支限界法的基

22、本思想岸雏咋辑聋朗猛啊褪坛以钱碑听蹄沿胀昏责囱吩鞠动豆琼氛鹃蕴声噪嚼厘六章分支限界法六章分支限界法解空间树的动态搜索 分支限界法分支限界法首先首先确定一个合理的限界函数，并根确定一个合理的限界函数，并根据限界函数确定目标函数的界据限界函数确定目标函数的界down, up； 然后然后按照广度优先策略遍历问题的解空间树，在按照广度优先策略遍历问题的解空间树，在某一分支上，依次搜索该结点的所有孩子结点，分别某一分支上，依次搜索该结点的所有孩子结点，分别估算这些孩子结点的目标函数的可能取值（对最小化估算这些孩子结点的目标函数的可能取值（对最小化问题，估算结点的问题，估算结点的down，对最大化问题，估

23、算结点的，对最大化问题，估算结点的up）。）。 如果某孩子结点的目标函数值超出目标函数的界，如果某孩子结点的目标函数值超出目标函数的界，则将其丢弃（从此结点生成的解不会比目前已得到的则将其丢弃（从此结点生成的解不会比目前已得到的更好），否则入待处理表。更好），否则入待处理表。6.1 分支限界法的基本思想分支限界法的基本思想达摹犯初匠翱珐尊咨旷募拱祁待战恶递究十擦徒腐巫赫郑畜找割抢撩氮证六章分支限界法六章分支限界法路径查找终止条件路径查找终止条件该节点的边界值超越目前目标函数的界。该节点的边界值超越目前目标函数的界。该节点无法代表任何可行解，因为它已违反了问该节点无法代表任何可行解，因为它已违反

24、了问题的约束。题的约束。226.1 分支限界法的基本思想分支限界法的基本思想叫丘孟踞济侯倾啮施楔戒牺坝眉淘兢蛙翁且署述辜注肖切遂伦芹唾轩哀珠六章分支限界法六章分支限界法6.1 分支限界法的基本思想分支限界法的基本思想 在问题的边带权解空间树中进行在问题的边带权解空间树中进行广度优先搜索广度优先搜索。找一个答找一个答案结点使对应路径权最小。案结点使对应路径权最小。当搜索到一个扩展结点时，一当搜索到一个扩展结点时，一次性扩展它的所有儿子，将满足约束条件且次性扩展它的所有儿子，将满足约束条件且最小耗费函数最小耗费函数 目标目标函数限界函数限界的儿子，插入的儿子，插入活结点表活结点表中，再从活结点表中

25、取下一结中，再从活结点表中取下一结点同样扩展，点同样扩展， 直到找到所需的解或活动结点表为空。直到找到所需的解或活动结点表为空。（用于求解最优化问题）（用于求解最优化问题） 结点结点x的最小耗费函数的最小耗费函数c(x):以以x为根的子树所包含的答案结为根的子树所包含的答案结点中，路径权最小者的权值。若点中，路径权最小者的权值。若x是答案结点是答案结点, 则则c(x)为该点的为该点的目标函数值目标函数值; 若若x是根结点是根结点, 则则c(x)为最优解值。为最优解值。c(x)为单调递增为单调递增函数。函数。晒哆常若茂烙贴沤恨牲屁瓢虎铲骋搀离峭购耘顷捆茹怨浊院昧墩烃咖粥喧六章分支限界法六章分支限

26、界法通常采用优先队列方式组织，通常采用优先队列方式组织， c(x)小者优先。小者优先。目标函数限界目标函数限界U: 初始初始U可取可取 ，若若x*是任一答案结点，且是任一答案结点，且c(x*)U时，时， x将不必扩展（剪枝）。将不必扩展（剪枝）。活动结点表活动结点表: :6.1 分支限界法的基本思想分支限界法的基本思想（用于求解最优化问题）（用于求解最优化问题）鸦憎拔恤郊蔷吼纵袜烩催松倔扔荆舌市追串彼怎抓至库魂从蘑媳俏努液啪六章分支限界法六章分支限界法1.确定解空间结构；确定解空间结构；2.确定约束条件和目标函数；确定约束条件和目标函数；3.取取U=U(T)；4.扩展根结点的所有儿子，对每一子

27、结点扩展根结点的所有儿子，对每一子结点x判定其是否满足约束判定其是否满足约束 条件，对满足约束条件的条件，对满足约束条件的 x 计算计算 , 将将 U的的x 加入活加入活 结点表；结点表；5. x为叶结点时，检查是否为叶结点时，检查是否c(x)U， 是，则用是，则用c(x)更新更新U；6. 取活结点表中的第一个结点为根取活结点表中的第一个结点为根, 重复重复4。 解题步骤解题步骤 最小耗费函数最小耗费函数c(x)的估算的估算: c(x)不能即时求得不能即时求得, 为此取能即时为此取能即时计算的下界函数计算的下界函数 代替代替, 应具有单调性应具有单调性, 且在答案结点且在答案结点上上 =c(x

28、)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 Proble

29、m) 首先把物品按照首先把物品按照P(i)/W(i)P(i+1)/W(i+1)的衡量标准排的衡量标准排序，序，以此顺序读入物品。并且定义一个大小为物品多少的解向量以此顺序读入物品。并且定义一个大小为物品多少的解向量X，X的一个分量就代表某个物品的装入情况。的一个分量就代表某个物品的装入情况。背包问题的贪心算法及说明背包问题的贪心算法及说明赴摇顾紧翅狡甘腊间扫贿扰后恨旗镁暖莽讼陶跺蚜伞祭润搪忽抡莆吐丰蓟六章分支限界法六章分支限界法 问题描述问题描述 设有设有n个物体和一个背包，物体个物体和一个背包，物体i的重量为的重量为wi ， 价值为价值为pi ，背包的载荷为，背包的载荷为M，找一个装载方案，

30、使得能放入，找一个装载方案，使得能放入背包的物体总价值最高。背包的物体总价值最高。算法思路算法思路将问题的解表示为将问题的解表示为n元向量元向量:x1, . xn , xi 0,1 用排序树表示解空间用排序树表示解空间, 在树中做广度优先搜索在树中做广度优先搜索,约束条件约束条件: M ;目标函数目标函数: ; 目标函数限界初值目标函数限界初值:U=0；c(x):以以x为根的子树所包含的叶子中，路径权值最大者；为根的子树所包含的叶子中，路径权值最大者； :以以x为根的子树的部分路径的权值。为根的子树的部分路径的权值。6.2 0-1背包问题背包问题 (0-1 Knapsack Problem)慎

31、疏益曝深隙溯茫镊怪垣弟添瘦撒擒距溃粟颜秆鱼刚鸣把萨秉酪希堡橱租六章分支限界法六章分支限界法算法的思想 首先，要对输入数据进行预处理，将各物品依其单位重量首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列。价值从大到小进行排列。 对于优先队列分支限界法，结点的优先级由已装袋的物品对于优先队列分支限界法，结点的优先级由已装袋的物品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值价值加上剩下的最大单位重量价值的物品装满剩余容量的价值和。和。 算法首先检查当前扩展结点的左儿子结点的可行性。如算法首先检查当前扩展结点的左儿子结点的可行性。如果该左儿子结点是可行结点，则将它加入到

32、子集树和活结点果该左儿子结点是可行结点，则将它加入到子集树和活结点优先队列中。当前扩展结点的右儿子结点一定是可行结点，优先队列中。当前扩展结点的右儿子结点一定是可行结点，仅当右儿子结点满足上界约束时才将它加入子集树和活结点仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列。优先队列。当扩展到叶结点时为问题的最优值。当扩展到叶结点时为问题的最优值。6.2 0-1背包问题背包问题 (0-1 Knapsack Problem)袱咬至妙癌哉泄魏器扁超臂眺拇温疚乐地蹈竞吏静磅图烫匣授珐追茎压厕六章分支限界法六章分支限界法算法的思想 算法首先检查当前扩展结点的左儿子结点的可行性。如算法首先检查当

33、前扩展结点的左儿子结点的可行性。如果该左儿子结点是可行结点，则将它加入到子集树和活结点果该左儿子结点是可行结点，则将它加入到子集树和活结点优先队列中。当前扩展结点的右儿子结点一定是可行结点，优先队列中。当前扩展结点的右儿子结点一定是可行结点，仅当右儿子结点满足上界约束时才将它加入子集树和活结点仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列。优先队列。当扩展到叶结点时为问题的最优值。当扩展到叶结点时为问题的最优值。6.2 0-1背包问题背包问题 (0-1 Knapsack Problem) 为了便于计算上界函数，可以先将物品按照其单位重量为了便于计算上界函数，可以先将物品按照其单位

34、重量价值从大到小排序，此后只要顺序考察各个物品即可。在实价值从大到小排序，此后只要顺序考察各个物品即可。在实现时，有函数现时，有函数Bound来计算当前结点处的上界。在解空间树来计算当前结点处的上界。在解空间树的当前扩展结点处，仅当要进入右子树时才计算上界函数的当前扩展结点处，仅当要进入右子树时才计算上界函数Bound，以判断是否可以将右子树剪去。进入左子树时不需，以判断是否可以将右子树剪去。进入左子树时不需要计算上界，因为其上界与其父结点的上界相同。要计算上界，因为其上界与其父结点的上界相同。蝶帝呛赛堡篱零斯庭遏遍蟹今大柳殴辊讣具甜化刷眯全快区浑寐吊诲舵努六章分支限界法六章分支限界法0/1背

35、包的分支限界法过程背包的分支限界法过程问题描述问题描述物品物品 重重(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/w

36、1)=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)蒸鳖靠翁宿押剐肛驴飘梭产韦郊席捏蒂赠窒阂枉谅何唤呆电蝉沪些擦资艘六章分支限界法六章分支限界法