《贪婪算法》课件.pptVIP

贪婪算法贪婪算法是一种简单直观的算法设计策略，在许多问题中都能找到应用。它在每一步选择都选择当前看来最优的方案，最终希望得到全局最优解。

什么是贪婪算法？选择最佳局部解贪婪算法在每一步选择看起来最优的方案，而不考虑全局最优解。逐步构建最优解贪婪算法以“一步一步”的方式，逐步构建最终的解，而不是一次性计算出全局最优解。可能无法找到最优解贪婪算法并非总是能找到全局最优解，有时会陷入局部最优解。

贪婪算法的特点11.贪心选择算法在每个步骤都选择当前看起来最优的选项，而不考虑未来。22.局部最优贪心算法总是做出局部最优的选择，希望最终得到全局最优解。33.简单易懂贪心算法的思路简洁明了，易于实现。44.效率较高贪心算法通常具有较高的运行效率，能够快速解决问题。

贪婪算法解决的问题找零问题给定一组面值的硬币，计算最少硬币数量以支付特定金额。活动安排问题给定一组活动，每个活动都有开始时间和结束时间，选择最大数量的互不相容的活动。哈夫曼编码问题给定一组字符及其频率，构建最优的二进制前缀编码，以最小化编码后的总长度。最短路径问题给定一个带权重的图，找到从源节点到目标节点的最短路径。

贪婪算法的基本步骤定义问题清晰地定义要解决的问题，确定目标函数和约束条件。构建贪婪选择根据当前状态选择看起来最好的选择，而不考虑未来的影响。构建解重复贪婪选择步骤，逐步构建问题的解。检查解验证构建的解是否满足问题的约束条件，并评估其质量。

贪婪算法的代价:局部最优解局部最优解贪婪算法选择当前看起来最好的方案，不一定能得到全局最优解。例子例如，找零问题中，如果只考虑当前面值最大的货币，可能无法找到最少的硬币数量。适用场景贪婪算法适用于能快速找到局部最优解，并且局部最优解也能带来较好效果的问题。

贪婪算法的应用场景找零问题银行自动售货机找零，以最小数量的硬币找零。使用不同面值的硬币来找零。活动安排问题一个房间可以安排多场活动，安排最多不相冲突的活动。选取最早结束的活动。哈夫曼编码问题使用二进制编码来压缩数据，用最短的平均码长。将最小的两个字符合并成一个新的节点。其他场景最短路径问题，最小生成树问题，背包问题等。贪婪算法可用于优化许多工程和科学领域的决策。

例子一:找零问题贪婪算法在找零问题中有着广泛的应用。例如，在商店付款时，收银员会使用尽可能多的面额较大的货币来找零，这体现了贪婪算法的基本思想。

找零问题的描述问题场景假设顾客购买商品后，需要用现金支付。收银员需要根据顾客支付的金额和商品的价格，计算出应找回的零钱。目标如何用最少的硬币数量，找回顾客支付的金额。约束条件收银员只有有限的几种硬币面值，例如1元、5角、1角。

找零问题的贪婪算法1选择最大面额首先选择面额最大的货币，并判断该面额是否小于或等于需要找的零钱。2计算剩余零钱如果选择的面额小于或等于需要找的零钱，则将该面额从需要找的零钱中减去，并记录使用该面额的货币数量。3重复步骤重复步骤1和2，直到需要找的零钱为0。

找零问题的贪婪算法实现1输入金额顾客需要找回的金额。2可用面值商店可以使用的货币面值。3贪婪算法选择最大面值不超过剩余金额的货币。4输出找零返回最优的找零方案。贪婪算法通过循环迭代，每次选择最大面值不超过剩余金额的货币，并将其从剩余金额中减去。直到剩余金额为零，算法结束，返回找零方案。

找零问题的代价分析时间复杂度贪婪算法的时间复杂度通常很低，它取决于可用面额的数量和所需金额的大小。空间复杂度贪婪算法的空间复杂度也较低，主要取决于储存面额信息的所需空间。局限性贪婪算法无法保证找到最优解，因为它只考虑局部最优解，而不考虑全局最优解。

例子二:活动安排问题活动安排问题是一个经典的贪婪算法应用场景。它要求在给定的时间段内，安排尽可能多的活动，并且这些活动之间不能互相冲突。

活动安排问题的描述活动安排问题是经典的贪婪算法应用场景。假设有一些活动，每个活动都有开始时间和结束时间。我们需要选择一些活动，使得这些活动之间不会冲突，并且选出的活动数量最多。活动安排问题在现实生活中有很多应用，例如会议安排、任务调度、考试安排等。

活动安排问题的贪婪算法1排序根据活动结束时间进行排序2选择选择最早结束的活动3迭代重复选择直到没有更多活动贪婪算法选择最早结束的活动，以此类推。每次选择都尽量选择最早结束的活动，以最大化活动数量。这种方法能保证在活动结束后，有更多时间安排后续活动。

活动安排问题的贪婪算法实现排序根据活动结束时间排序，将活动按结束时间升序排列。选择从排序后的活动列表中选择第一个活动，并将其加入活动安排集合中。迭代遍历剩余活动，如果当前活动开始时间大于等于已安排活动结束时间，则选择当前活动，并将其加入活动安排集合中。结束重复迭代步骤，直到所有活动都被遍历完。

活动安排问题的代价分析时间复