狄斯奎诺算法 c语言,数据结构与算法 贪婪法.ppt

狄斯奎诺算法 c语言,数据结构与算法 贪婪法.ppt

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

西华大学数学与计算机学院 黄襄念 西华大学数学与计算机学院计算机系 黄襄念 编 eMail: huangxn@ Tel第 8 章 贪婪法 贪婪法的设计思想 贪婪法解背包问题 MST(最小生成树)问题 Prim(普里姆)算法 Kruskal(克鲁斯卡尔)算法 单源(单起点)最短路径问题 Dijkstra(狄克斯特拉 )算法 本章习题 贪婪法设计思想 贪婪法(Greedy algorithms) 贪婪法常用来解决最优化问题。犹如登山一样，一步一步向前推进。 从某个初始点出发，根据当前局部的而不是全局的最优决策，以满足 约束方程为条件，使目标函数值增加最快或最慢为规则，决定本步的 局部最优解。如最速上山法各步的方向选择 —— 梯度。计算机学家 把贪婪法作为一种通用设计技术，通过一系列步骤来构造问题的解， 每一步对当前获得的局部最优解进行扩展，直到全局最优解为止。 每一步选择满足(与动态规划法不同)： —— 是可行解：满足约束条件 —— 局部最优：当前步骤下，所有选择中的局部最佳选择(贪婪) —— 不可修改：当前局部解一旦得到，后续步骤无法改变它 贪婪法：全局最优解是由一系列步骤的局部最优解构成。 优点：比动态规划法的时间和空间效率高，算法设计较简单。对某些 问题，贪婪法不能获得全局最优解。算法设计时，需要考虑问题是否 适合用贪婪法解，即贪婪法是否能够得到全局最优解！ 简例：找零钱 【简例】找零钱 已知：有 4 种面额硬币：25分、10分、5分、1分 要求：用最少数量的硬币支付 48 分零钱。(48：问题规模) 算法步骤 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 个钱币。贪婪法不一定能得到全局最优解。 贪婪法的两个性质(基本要素) 贪婪法的两个性质 —— 判断贪婪法是否适用 最优子结构 当前规模的最优解包含其子问题的最优解。 贪婪选择 一系列局部最优选择可达到全局最优，每次选择得到一个局部最优解。 动态规划法与贪婪法 动态规划法：全局最优解与各步所有子问题都有关，而非仅限于最优 子问题(未来决策)。自底向上计算(规模↑) 贪婪法的视界局限：当前状态的局部最优选择，不能预见未来。 自顶向下计算(规模↓) —— 贪婪法不能得到最优解时，动态规划法可以得到最优解。 —— 贪婪算法设计简单，时空效率比动态规划法高。 —— 比较 “数塔”、“多段图” 问题的两种算法过程。 背包问题 背包问题(Knapsack Problem) 两类背包 连续背包 —— 物品可任意比例切分 (贪婪法能求得最优解) 01 背包 —— 物品不可切分 (贪婪法不一定能求得最优解) 连续背包的最优化模型(实数 xk 表示物品 k 放入背包的比例系数) 三种贪婪策略 价值最大：满足约束条件下，每次装入价值最大的物品。 —— 不一定能找到最优解(背包承重量消耗太快) 重量最小：满足约束条件下，每次装入重量最轻的物品。 —— 不一定能找到最优解(装入总价值增加太慢) 单位价值最大：满足约束条件下，每次装入 价值 / 重量 最大的物品 —— 能找到最优解 背包问题的贪婪算法 连续背包的贪婪算法 // 解向量初始 = 0，空背包 // 背包的当前承重量 // 背包中物品总价值 // 对 w , v 按 价值/重量 降序排序 // n个物品循环，当前物品为第 i 个 // 当前物品未超重 // 当前物品整个装入背包：xi = 1 // 背包当前承重量减小 // 当前物品价值记入总价值 // 当前物品超重：放入一部分