算法导论课件第15讲分支定界法
42页1、第6章 分支限界法,理解分支限界法的剪枝搜索策略。 掌握分支限界法的算法框架: (1)队列式(FIFO)分支限界法 (2)优先队列式分支限界法 通过应用范例学习分支限界法的设计策略。,学习要点,分支限界法的基本思想,分支限界法与回溯法,(1)求解目标:回溯法的求解目标是找出解空间树中满足约束条件的所有解,而分支限界法的求解目标则是找出满足约束条件的一个解,或是在满足约束条件的解中找出在某种意义下的最优解。,(2)搜索方式的不同:回溯法以深度优先的方式搜索解空间树,而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。,分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树。,此后,从活结点表中取下一结点成为当前扩展结点,并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。,在分支限界法中,每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点,就一次性产生其所有儿子结点。在这些儿子结点中,导致不可行解或导致非最优解的儿子结点被舍弃,其余儿子结点被加入活结点表中。,分支限界法的基本思想,分支限界法的基本思想,常见的两种分支限界法,(
2、1)队列式(FIFO)分支限界法 按照队列先进先出(FIFO)原则选取下一个节点为扩展节点。,(2)优先队列式分支限界法 按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。,分支限界法首先确定一个合理的限界函数,并根据限界函数确定目标函数的界down, up 。然后,按照广度优先策略遍历问题的解空间树,在分支结点上,依次搜索该结点的所有孩子结点,分别估算这些孩子结点的目标函数的可能取值。 如果某孩子结点的目标函数可能取得的值超出目标函数的界,则将其丢弃,因为从这个结点生成的解不会比目前已经得到的解更好;否则,将其加入待处理结点表中。依次从表PT中选取使目标函数的值取得极值的结点成为当前扩展结点,重复上述过程,直到找到最优解。,随着这个遍历过程的不断深入,表PT中所估算的目标函数的界越来越接近问题的最优解。 当搜索到一个叶子结点时,如果该结点的目标函数值是表PT中的极值(对于最小化问题,是极小值;对于最大化问题,是极大值),则该叶子结点对应的解就是问题的最优解;否则,根据这个叶子结点调整目标函数的界(对于最小化问题,调整上界;对于最大化问题,调整下界),依次考察表PT中的结
3、点,将超出目标函数界的结点丢弃,然后从表PT中选取使目标函数取得极值的结点继续进行扩展。,单源最短路径问题,单源最短路径问题,1. 问题描述,下面以一个例子来说明单源最短路径问题:在下图所给的有向图G中,每一边都有一个非负边权。要求图G的从源顶点s到目标顶点t之间的最短路径。,单源最短路径问题,2. 剪枝策略,在算法扩展结点的过程中,一旦发现一个结点的下界不小于当前找到的最短路长,则算法剪去以该结点为根的子树。 在算法中,利用结点间的控制关系进行剪枝。从源顶点s出发,2条不同路径到达图G的同一顶点。由于两条路径的路长不同,因此可以将路长长的路径所对应的树中的结点为根的子树剪去。,单源最短路径问题,3. 算法思想,解单源最短路径问题的优先队列式分支限界法用一极小堆来存储活结点表。其优先级是结点所对应的当前路长。,算法从图G的源顶点s和空优先队列开始。结点s被扩展后,它的儿子结点被依次插入堆(待处理结点表,以下简称表PT)中。此后,算法从堆中取出具有最小当前路长的结点作为当前扩展结点,并依次检查与当前扩展结点相邻的所有顶点。如果从当前扩展结点i到顶点j有边可达,且从源出发,途经顶点i再到顶
4、点j的所相应的路径的长度小于当前最优路径长度,则将该顶点作为活结点插入到活结点优先队列中。这个结点的扩展过程一直继续到活结点优先队列为空时为止。,单源最短路径问题,1. 问题描述,下图是用优先队列式分支限界法解有向图G的单源最短路径问题产生的解空间树。其中,每一个结点旁边的数字表示该结点所对应的当前路长。,第1层,第2层,第4层,第5层,第3层,目前的最短路径是8,一旦发现某个节点的下界不小于这个最短路进,则剪枝。,利用节点的控制关系剪枝,将会产生重复的子树,剪枝,while (true) for (int j = 1; j N; N.node=j; /顶点编号为j N.length=distj; H.Insert(N); try H.DeleteMin(E); / 取下一扩展结点 catch (OutOfBounds) break; / 优先队列空 ,顶点i和j间有边,且此路径长小于原先从原点到j的路径长。 这个判断,实现了剪枝,dist:最短距离数组 prev: 前驱顶点数组 E:当前的扩展节点 c: 邻接矩阵 H: 活节点优先队列,记载最短路径,缺乏上界 函数减枝,优先权队列 V
《算法导论课件第15讲分支定界法》由会员E****分享,可在线阅读,更多相关《算法导论课件第15讲分支定界法》请在金锄头文库上搜索。
逍遥游复习 知识点整理
近现代法德关系史 高三展示课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页