算法课件2015第6章分支限界法
47页1、1,第6章 分支限界法,马志强,2,学习要点,分支限界法的算法框架 队列式(FIFO)分支限界法 优先队列式分支限界法堆式分支限界法 应用分支限界法解决 单源最短路径问题 装载问题; 0-1背包问题; 旅行售货员问题 批处理作业调度问题,3,分支限界法的背景理查德.卡普,在IBM期间,深入研究了与实际应用有密切联系的一系列数学问题,如路径问题、背包问题、覆盖问题、匹配问题、分区问题、调度问题等,取得了许多出色的成果。这些问题有一个共同的特点,即如果用图来表示问题,那么当图中增加一个结点时,需要考察的可能的解的数目就急剧增加,形成所谓“组合爆炸” (combinatorial explosion),使计算机的计算工作量大大增加,到一定程度就根本无法实现。 以路径问题中最著名的旅行商问题为例,在卡普以前,最好的结果是Rand公司的丹齐格(George Benard Dantzig)、福格森(RFulkerson)和约翰逊(SJohnson)用手工和计算机相结合的办法,求出了包含49个城市的旅行商的最佳路线。卡普和他的同事海尔特(MHeld)经过反复研究,终于提出了一种称为“分支限界法”(b
2、ranchandbound method)的新方法,用这种新方法实现的算法使旅行推销员能周游的城市数达到65个,从而打破了由Rand公司保持的记录。,1955年文学学士学位 1956年理科硕士学位 1959年应用数学博士学位(哈佛大学) Yorktown Heights的IBM沃森研究中心 1985年获得ACM的图灵奖,4,分支限界法基础,8-Puzzle问题 输入: 具有8个编号小方块的魔方 输出: 移动序列, 经过这些移动, 魔方达目标状态,5,分支限界法基础,队列式(FIFO)分支限界法 广度优先搜索解空间树,A,B,C,D,E,F,G,A,B,C,D,E,F,G,6,分支限界法基础,优先队列式分支限界法堆式分支限界 为解空间树中的每个节点指定一个优先级测度函数 每次扩展树中优先级最高的节点 用最大(最小)堆来保存待搜索节点 8-Puzzle问题 测度函数 f (v) =节点v中处于错误位置的方块数 每次扩展 f (v) 值最小的节点,7,B(3),C(3),D(4),E(4),F(2),G(4),H(1),I(0),J(2),A,A,B,C,D,E,F,G,H,最小堆,8,分支
3、限界法基础,思想 广度优先或者优先级优先搜索解空间树 实现 每个节点只有一次机会成为扩展节点 一旦节点v成为扩展节点 将 v 的所有孩子加入到队列或者堆中 接着选取队列顶或堆顶节点作为下一个扩展节点 效率 耗时比回溯法少 需要空间比回溯法多,9,常见的两种分支限界法,(1)队列式分支限界法 按照队列先进先出(FIFO)或者后进先出(LIFO)原则选取下一个结点为扩展结点。,(2)优先队列式分支限界法 队列式分支限界法对结点的选择规则相当死板,具有一定的 “盲目”性。这种选择规则不利于快速检索到一个能够到达答案的结点。 对活结点使用一个“有智能”的排序函数C()来选取下一个结点,往往可以加快获取答案的速度。 按照优先队列中规定的优先级选取优先级最高的结点成为当前扩展结点。常用方法是LC(Least Cost)方法。,分支限界法基础,10,画出下图的解题过程(按优先队列方式),11,源最短路径问题,输入 有向带权图G=(V, E) 图中顶点s 输出 s到图中其它顶点的最短路径,12,源最短路径问题,解空间树,13,源最短路径问题,优先队列式分支限界法 优先级测度:当前路径长度 (最小堆),
4、14,源最短路径问题,剪枝策略 节点b:50控制b:60 将b:60 及其子树剪去 当前扩展节点有儿子v: x 如果x=distv,不扩展v 如果xdistv,扩展v,将v的孩子加入堆中,15,0-1背包问题,输入: , , 和C 输出: (x1, x2, , xn),xi0, 1满足 优化目标:,16,0-1背包问题,解空间树,w=16,15,15 v=45,25,25 背包容量30,17,0-1背包问题,FIFO队列式分支限界法,FIFO队列,A, B,D, E, F,J, K, L, M, N,节点C对应:x1=1, x2=1 节点K对应:x1=0, x2=1, x3=1,18,0-1背包问题,对于树中的第i层节点V 已经完成了对物品1, i的取舍,剩余物品为i+1, ., n 设已选择的物品价值为p,背包剩余容量为C 限界函数bound(V) = p + q 其中q是针对输入i+1, ., n和C的一般背包问题的最优解 可以按价重比顺序依次向背包中装入物品得到q 以V为根的子树中节点的价值不会超过bound(V),物品按价重比排序为1, , n,19,0-1背包问题,优先队列式
《算法课件2015第6章分支限界法》由会员E****分享,可在线阅读,更多相关《算法课件2015第6章分支限界法》请在金锄头文库上搜索。
逍遥游复习 知识点整理
近现代法德关系史 高三展示课3稿
当代大学生人生信仰及追求的调查研究
长相思 纳兰性德-ppt课件
课件:危机意识 一
英语ppt演讲关于阿甘正传
发达国家基础教育改革的动向与趋势 修改版
中国民间美术 课件.ppt
生物质发电技术与系统 课程ppt 第1章 生物质发电技术现状及发展趋势 2学时 -----2016
现代信号处理思考题 含答案
执业药师继续教育 抑郁症的药物治疗 100分
小学生的成长档案模板不用修改 万能型
增订六版 现代汉语 上册 第二章文字 思考与练习答案
国家财政ppt课件
加拿大英语介绍
六年级统计图的选择课件
中学生成长档案ppt
中国现代文学史期末复习整理
lohi和hihilo训练对女子赛艇运动员运动能力影响的比较研究
风雨贾平凹阅读答案
2024-04-11 25页
2024-04-11 37页
2024-04-11 28页
2024-04-11 31页
2024-04-11 36页
2024-04-11 29页
2024-04-11 22页
2024-04-11 27页
2024-04-11 34页
2024-04-11 32页