第2章 婪法.pptVIP

第 2 章 贪婪法 贪婪法的设计思想 贪婪法解背包问题 MST（最小生成树）问题 Prim（普里姆）算法 Kruskal（克鲁斯卡尔）算法 单源（单起点）最短路径问题 Dijkstra（狄斯奎诺）算法 本章习题 敌朱仟钝窃鹰披雁篇剐锣昼疫柏葫智孪干厂湾桨劈质矩朱觉词刑频主匙巨第2章 婪法第2章 婪法 贪婪法设计思想 贪婪法（Greedy algorithms）设计思想 贪婪法常用来解决最优化问题。犹如登山一样，一步一步向前推进。 从某个初始点出发，根据当前局部的而不是全局的最优决策，以满足 约束方程为条件，使目标函数值增加最快或最慢为规则，决定本步的 局部最优解。如最速上山法各步的方向选择 —— 梯度。计算机学家 把贪婪法作为一种通用设计技术，通过一系列步骤来构造问题的解， 每一步对当前获得的局部最优解进行扩展，直到全局最优解为止。 每一步选择满足（与动态规划法不同）： 1. 可行解：满足约束条件。 2. 局部最优；当前步骤下，所有选择中的局部最佳选择（贪婪）。 3. 不可取消：当前局部解一旦得到，后续步骤无法改变。 贪婪法认为，全局最优解是由一系列步骤的局部最优解构成。优点：比动态规划法的时间和空间效率高，算法设计也较简单。但对于某些 问题，贪婪法不能获得全局最优解。因此，算法设计时，需考虑问题 是否适合用贪婪法解，即贪婪法得到的解是否全局最优解。 峭扦颓上拘方谍锨记商千虎绥玉挫社恤肯芽以厄炮盒阶劣柔挣惭纷峻砰空第2章 婪法第2章 婪法 简例：找零钱 简例：找零钱 已知：有4种面额的硬币：25分、10分、5分、1分。 要求：用最少数量的硬币支付48分零钱。（目标值48：问题规模） 算法步骤： 1. 支付面额满足约束条件（≤48分）的最大硬币（25分）；（贪婪） 2. 计算目标函数值48-25=23；判断是否达到要求（0分）： 若是，算法停止，否则，返回1步。 计算结果：25，10，10，1，1，1。——6个钱币 算法策略： 总是作出当前最佳选择——局部最优。每一步选择最大硬币，是为了 把余下的数量减到最小。 结果讨论： 针对这4种面额，贪婪法的确能给出全局最优解。现在换为3种面额： 7分、5分、1分，找零钱11分。贪婪法结果：7,1,1,1,1 共5个钱币。 最优解：5,5,1共3个钱币。因此，贪婪法不一定能得到全局最优解。 跌张墩轿瓜悉育秒酥赤历吓靶幼潦悍起怨渝苗陕帜屡莉膊联恕食翟窟碎标第2章 婪法第2章 婪法 贪婪法的两个性质（基本要素） 用贪婪法的两个性质判断问题是否适用贪婪法求解 贪婪选择： 所求问题的全局最优解，可通过一系列的局部最优选择来达到。每次 选择就得到一个局部最优解，将所求问题化简为规模更小的子问题。 最优子结构： 问题的最优解中包含它的子问题最优解。换句话说，全局最优解是由局部最优解组成。 贪婪法与动态规划法的区别 动态规划法，第 k 步所作出的选择依赖于第k-1步内若干个子问题解 （与未来选择有关），只有在解出k-1步所有子问题后，才能作出选择。 贪婪法仅在当前状态下作局部最优选择（与未来选择无关）。然后， 再去解作出这个选择后产生的子问题。正由于这种差别，动态规划法 通常以自底向上方式求解各个子问题，而贪婪法则通常以自顶向下的方式进行。贪婪法不能得到最优解时，动态规划法可以得到最优解。 用前面讲过的“数塔”、“多段图”等问题来比较这两种算法的不同。 掺怪挣独技日喧惶与陵魂贬软蛊筛颠壬襄辞气案驭讽催键殉叶阑言汁书帅第2章 婪法第2章 婪法 背包问题 背包问题 （Knapsack Problem） 两类背包问题： 1. 物品可以分割的背包问题。贪婪法求得最优解。 2. 物品不可以分割的0-1背包问题。贪婪法不一定能求得最优解。 背包问题：承重W的背包，n个重量为 w1...wn、价值v1...vn的物品。 求这些物品中最有价值子集，且能装入背包中。 最优化模型： xk (0≤xk≤1)表示物品 k (k=1,...,n) 放入背包的比例系数 三种贪婪装入的策略： 1. 价值最大：满足约束条件下，每次装入价值最大的物品。不一定能 找到最优解，原因是背包承重量消耗太快。 2. 重量最小：满足约束条件下，每次装入重量最轻的物品。不一定能 找到最优解，原因是装入的物品总价值增加太慢。 3. 单位价值最大：满足约束条