欢迎来到天天文库
浏览记录
ID:56373780
大小:619.00 KB
页数:28页
时间:2020-06-14
《数据结构与算法 贪婪法.ppt》由会员上传分享,免费在线阅读,更多相关内容在PPT专区-天天文库。
1、第8章贪婪法贪婪法的设计思想贪婪法解背包问题MST(最小生成树)问题Prim(普里姆)算法Kruskal(克鲁斯卡尔)算法单源(单起点)最短路径问题Dijkstra(狄克斯特拉)算法本章习题贪婪法设计思想贪婪法(Greedyalgorithms)贪婪法常用来解决最优化问题。犹如登山一样,一步一步向前推进。从某个初始点出发,根据当前局部的而不是全局的最优决策,以满足约束方程为条件,使目标函数值增加最快或最慢为规则,决定本步的局部最优解。如最速上山法各步的方向选择——梯度。计算机学家把贪婪法作为一种通用设计技术,通过一系列步骤来构造问题的解,每一步对当前获
2、得的局部最优解进行扩展,直到全局最优解为止。每一步选择满足(与动态规划法不同):——是可行解:满足约束条件——局部最优:当前步骤下,所有选择中的局部最佳选择(贪婪)——不可修改:当前局部解一旦得到,后续步骤无法改变它贪婪法:全局最优解是由一系列步骤的局部最优解构成。优点:比动态规划法的时间和空间效率高,算法设计较简单。对某些问题,贪婪法不能获得全局最优解。算法设计时,需要考虑问题是否适合用贪婪法解,即贪婪法是否能够得到全局最优解!简例:找零钱【简例】找零钱已知:有4种面额硬币:25分、10分、5分、1分要求:用最少数量的硬币支付48分零钱。(48:问题
3、规模)算法步骤1.支付满足约束条件(≤48分)的最大硬币(25分)——贪婪2.检查余额(48–25)=0?YES:算法停止;NO:返回1计算结果:(25,10,10,1,1,1)共用6个硬币算法策略总是作出当前最佳选择——局部最优。每一步选择最大硬币,是为了把余额减到最小——追求“最速”结果讨论针对这4种面额,贪婪法的确能给出全局最优解。现在换3种面额:7分、5分、1分,找零钱11分。贪婪法结果:7,1,1,1,1共5个钱币。最优解:5,5,1共3个钱币。贪婪法不一定能得到全局最优解。贪婪法的两个性质(基本要素)贪婪法的两个性质——判断贪婪法是否适用最
4、优子结构当前规模的最优解包含其子问题的最优解。贪婪选择一系列局部最优选择可达到全局最优,每次选择得到一个局部最优解。动态规划法与贪婪法动态规划法:全局最优解与各步所有子问题都有关,而非仅限于最优子问题(未来决策)。自底向上计算(规模↑)贪婪法的视界局限:当前状态的局部最优选择,不能预见未来。自顶向下计算(规模↓)——贪婪法不能得到最优解时,动态规划法可以得到最优解。——贪婪算法设计简单,时空效率比动态规划法高。——比较“数塔”、“多段图”问题的两种算法过程。背包问题背包问题(KnapsackProblem)两类背包连续背包——物品可任意比例切分(贪婪法
5、能求得最优解)01背包——物品不可切分(贪婪法不一定能求得最优解)连续背包的最优化模型(实数xk表示物品k放入背包的比例系数)三种贪婪策略价值最大:满足约束条件下,每次装入价值最大的物品。——不一定能找到最优解(背包承重量消耗太快)重量最小:满足约束条件下,每次装入重量最轻的物品。——不一定能找到最优解(装入总价值增加太慢)单位价值最大:满足约束条件下,每次装入价值/重量最大的物品——能找到最优解背包问题的贪婪算法连续背包的贪婪算法//解向量初始=0,空背包//背包的当前承重量//背包中物品总价值//对w,v按价值/重量降序排序//n个物品循环,当前物
6、品为第i个//当前物品未超重//当前物品整个装入背包:xi=1//背包当前承重量减小//当前物品价值记入总价值//当前物品超重:放入一部分,装满背包问:当前物品超重时,为什么不取后面的物品,而是取当前物品的一部分装入背包?最小生成树(MST)问题最小生成树问题(MinimumSpanningTree,MST)应用举例:城市交通道路网、通信线路网的花费最低生成树:包含连通图全部顶点的连通无环子图,或称:支撑树最小生成树:带权连通图权重最小的一棵生成树树的权重:所有边的权重之和最小生成树问题:求带权连通图的最小生成树的问题生成树、最小生成树图例:ADCB1
7、235ADCB123有环连通图w(T1)=6w(T2)=9w(T3)=8T1:最小生成树(MST)ADCB135ADCB125普里姆(Prim)算法Prim(普里姆)算法不断扩展子树→逐步生成MST1.初始树:从图中任选一个顶点v0作为初始生成树2.扩展树:把不在树中、与树距离最近的顶点加入树中(贪婪)与树的距离:到树中所有顶点的距离3.算法停止:全部顶点都包含于树中。每次只扩展一个顶点,扩展次数=
8、V
9、-1=n-1//输入图G=,生成树T=//任选顶点v0作为初始生成树//u*移入VT,v*是树中顶点//边移入ET//返回边集
10、普里姆(Prim)算法子树TkMST扩展过程示意图Prim算法过程图例Prim算法过程例每次扩
此文档下载收益归作者所有