算法设计与分析分支限界法01.pdf

智能信息处理研究中心 （RCIIP ） P 第6章 分支限界法 a 潘海为 n 1 智能信息处理研究中心 （RCIIP ） 学习要点 学习要点  理解分支限界法的剪枝有哪些信誉好的足球投注网站策略 PP  掌握分支限界法的算法框架  队列式(FIFO)分支限界法  优先队列式分支限界法  通过应用范例学习分支限界法的设计策略 aa  单源最短路径问题  装载问题；  0-1背包问题； nn  最大团问题；  旅行售货员问题  批处理作业调度问题 2 智能信息处理研究中心 （RCIIP ） 分支限界法的背景——理查德.卡普 • 1955年文学学士学位 • 1956年理科硕士学位 P • 1959年应用数学博士学位(哈佛大学) • Yorktown Heights的IBM沃森研究中心 • 1985年获得ACM 的图灵奖 在IBM期间，深入研究了与实际应用有密切联系的一系列数学问题，如路径问题、 背包问题、覆盖问题、匹配问题、分区问题、调度问题等，取得了许多出色的成 a 果。这些问题有一个共同的特点，即如果用图来表示问题，那么当图中增加一个 结点时，需要考察的可能的解的数目就急剧增加，形成所谓“组合爆炸” (combinatorial explosion)，使计算机的计算工作量大大增加，到一定程度就根 本无法实现。 以路径问题中最著名的旅行商问题为例，在卡普以前，最好的结果是Rand公司的 丹齐格(George Benard Dantzig)、福格森(R．Fulkerson)和约翰逊(S．Johnson) n 用手工和计算机相结合的办法，求出了包含49个城市的旅行商的最佳路线。卡普 和他的同事海尔特(M．Held)经过反复研究，终于提出了一种称为“分支限界 法” (branch—and—bound method)的新方法，用这种新方法实现的算法使旅行推 销员能周游的城市数达到65个，从而打破了由Rand公司保持的记录。 3 智能信息处理研究中心 （RCIIP ） 分支限界法的基本思想  分支限界法常以广度优先或以最小耗费（最大效益）优 P 先的方式有哪些信誉好的足球投注网站问题的解空间树。 a n