ACM培训第十讲-贪心算法.ppt

4、贪心算法的总结 [贪心算法小结] a) 如何贪心 贪心算法有两大难点： 怎样用一个小规模的解构造更大规模的解呢?总体上，这与问题本身有关。但是大部分都是有规律的。 一般而言，单纯的贪心算法是顺序处理问题的；而且每个结果是可以在处理完一个数据后即时输出的。 4、贪心算法的总结 [贪心算法小结] b) 贪心的正确性 贪心算法有两大难点： 要证明贪心性质的正确性，才是贪心算法的真正挑战，因为并不是每次局部最优解都会与整体最优解之间有联系。 因为贪心算法的适用范围并不大，而且有一部分极难证明，若是没有把握，最好不要冒险，还有其他算法会比它要保险。 4、贪心算法的总结 [小结] （1）归纳、分析、选择贪心准则是解决贪心问题的关键。 （2）胆大心细，努力掌握。 相关习题 基础题：1045，1257，2021，1789 进阶题：2037，4864，1969 做出当前最好选择时，目标不再是整体的目标，当前选择的标准就要发生变化。 最原始的方法是有哪些信誉好的足球投注网站（穷举）法。当然，为了尽快有哪些信誉好的足球投注网站出解，我们往往会利用限制条件进行可行性判断剪枝，或利用目标函数的上界（或下界）进行分枝定界。第二种解决此类问题的方法是动态规划。当然，使用动态规划必须要满足一些条件，如无后效性和最优子结构等等。 　　　贪心策略是指从问题的初始状态出发，通过若干次的贪心选择而得出最优值(或较优解)的一种解题方法。其实，从“贪心策略”一词我们便可以看出，贪心策略总是做出在当前看来是最优的选择，也就是说贪心策略并不是从整体上加以考虑，它所做出的选择只是在某种意义上的局部最优解，而许多问题自身的特性决定了该题运用贪心策略可以得到最优解或较优解。如果有正确贪心性质存在，那么一定要采用。因为它容易编写，容易调试，速度极快，并且节约空间。几乎可以说，此时它是所有算法中最好的。 ACM程序设计第十讲-贪心算法 湖南工学院 张新玉 zhangxinyu247@163.com 引言 [引言] 贪婪是一种人类本能的东西，贪心算法也是最接近人类日常思维的一种解题策略。其实，在解决一些日常问题时，我们本能就怀着对目标最直观、最简单、最高效的思路，其中往往就带有贪心思想的影子。虽然它不能保证求得的最后解一定是最佳的，但是它可以为某些问题确定一个可行性范围。在某些范围内，贪心算法是我们的最佳选择。 引例——找零钱 [问题描述] 假设提供了数目不限的面值为2 5美分、1 0美分、5美分、及1美分的硬币。 一个小孩买了价值少于1美元的糖，并将1美元的钱交给售货员。售货员希望用数目最少的硬币找给小孩。 假设小孩买了33美分的糖果 （需要找给小孩6 7美分） 找钱的方法：25+25+10+5+1+1 我们有种直觉的倾向： 在找零钱时，直觉告诉我们使用面值大的硬币，剩余的金额就越少。 什么是贪心算法？ 将问题的求解过程看作是一系列选择，每次选择一个输入，每次选择都是当前状态下的最好选择(局部最优解)。每作一次选择后，所求问题会简化为一个规模更小的子问题。从而通过每一步的最优解逐步达到整体的最优解。 [贪心算法的示意图] 其中： ·红箭头表示当前最优决策； ·蓝箭头表示其他决策； ·小球表示当前状态。 [贪心算法基本思想：] 贪心算法的概念 这样转化的直觉：使用越多的大面值的硬币，最后硬币总数就会越少 [标准转化] 找一个硬币的时候： 找的硬币总数最少→使剩余金额最少 原 现 顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。 贪心猜想（贪心策略） 贪心算法的概念 从问题的某一初始解出发；? while?能朝给定总目标前进一步? do?求出可行解的一个解元素；? 由所有解元素组合成问题的一个可行解； [贪心算法步骤] 真正意义要求解原问题 将原问题变成更小子问题的步骤 整理解 【标准转化】 实例——小鼠迷宫问题 [问题描述] 每次老鼠a可以向八个方向移动，要求到达迷宫出口b的最少步数。 实例——小鼠迷宫问题 [算法分析] 算法：贪心策略的应用 每次沿着尽可能减小到终点距离的方向走。 实例——小鼠迷宫问题 [问题描述] 每次老鼠a可以向八个方向移动，要求到达迷宫出口b的最少步数。 要求解的原问题： [a到b的路径] 变成更小子问题的步骤： [移动一次] 标准转化： [最小步数]-[距离最短的方向] 引例——小鼠迷宫问题 [变化] 每次老鼠a可以向八个方向移动，不能移动到陷阱（黄色的格子），要求到达迷宫出口b的最少步数。 贪心概念 [最优化问题] 最优化问题包含一组限制条件（约束条件）和一个目标函