数据结构与算法 贪婪法.ppt

《数据结构与算法 贪婪法.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算法过程例每次扩