《贪婪算法》课件

贪婪算法贪婪算法是一种简单直观的算法设计策略，在许多问题中都能找到应用。它在每一步选择都选择当前看来最优的方案，最终希望得到全局最优解。什么是贪婪算法？选择最佳局部解贪婪算法在每一步选择看起来最优的方案，而不考虑全局最优解。逐步构建最优解贪婪算法以“一步一步”的方式，逐步构建最终的解，而不是一次性计算出全局最优解。可能无法找到最优解贪婪算法并非总是能找到全局最优解，有时会陷入局部最优解。贪婪算法的特点11.贪心选择算法在每个步骤都选择当前看起来最优的选项，而不考虑未来。22.局部最优贪心算法总是做出局部最优的选择，希望最终得到全局最优解。33.简单易懂贪心算法的思路简洁明了，易于实现。44.效率较高贪心算法通常具有较高的运行效率，能够快速解决问题。贪婪算法解决的问题找零问题给定一组面值的硬币，计算最少硬币数量以支付特定金额。活动安排问题给定一组活动，每个活动都有开始时间和结束时间，选择最大数量的互不相容的活动。哈夫曼编码问题给定一组字符及其频率，构建最优的二进制前缀编码，以最小化编码后的总长度。最短路径问题给定一个带权重的图，找到从源节点到目标节点的最短路径。贪婪算法的基本步骤定义问题清晰地定义要解决的问题，确定目标函数和约束条件。构建贪婪选择根据当前状态选择看起来最好的选择，而不考虑未来的影响。构建解重复贪婪选择步骤，逐步构建问题的解。检查解验证构建的解是否满足问题的约束条件，并评估其质量。贪婪算法的代价:局部最优解局部最优解贪婪算法选择当前看起来最好的方案，不一定能得到全局最优解。例子例如，找零问题中，如果只考虑当前面值最大的货币，可能无法找到最少的硬币数量。适用场景贪婪算法适用于能快速找到局部最优解，并且局部最优解也能带来较好效果的问题。贪婪算法的应用场景找零问题银行自动售货机找零，以最小数量的硬币找零。使用不同面值的硬币来找零。活动安排问题一个房间可以安排多场活动，安排最多不相冲突的活动。选取最早结束的活动。哈夫曼编码问题使用二进制编码来压缩数据，用最短的平均码长。将最小的两个字符合并成一个新的节点。其他场景最短路径问题，最小生成树问题，背包问题等。贪婪算法可用于优化许多工程和科学领域的决策。例子一:找零问题贪婪算法在找零问题中有着广泛的应用。例如，在商店付款时，收银员会使用尽可能多的面额较大的货币来找零，这体现了贪婪算法的基本思想。找零问题的描述问题场景假设顾客购买商品后，需要用现金支付。收银员需要根据顾客支付的金额和商品的价格，计算出应找回的零钱。目标如何用最少的硬币数量，找回顾客支付的金额。约束条件收银员只有有限的几种硬币面值，例如1元、5角、1角。找零问题的贪婪算法1选择最大面额首先选择面额最大的货币，并判断该面额是否小于或等于需要找的零钱。2计算剩余零钱如果选择的面额小于或等于需要找的零钱，则将该面额从需要找的零钱中减去，并记录使用该面额的货币数量。3重复步骤重复步骤1和2，直到需要找的零钱为0。找零问题的贪婪算法实现1输入金额顾客需要找回的金额。2可用面值商店可以使用的货币面值。3贪婪算法选择最大面值不超过剩余金额的货币。4输出找零返回最优的找零方案。贪婪算法通过循环迭代，每次选择最大面值不超过剩余金额的货币，并将其从剩余金额中减去。直到剩余金额为零，算法结束，返回找零方案。找零问题的代价分析时间复杂度贪婪算法的时间复杂度通常很低，它取决于可用面额的数量和所需金额的大小。空间复杂度贪婪算法的空间复杂度也较低，主要取决于储存面额信息的所需空间。局限性贪婪算法无法保证找到最优解，因为它只考虑局部最优解，而不考虑全局最优解。例子二:活动安排问题活动安排问题是一个经典的贪婪算法应用场景。它要求在给定的时间段内，安排尽可能多的活动，并且这些活动之间不能互相冲突。活动安排问题的描述活动安排问题是经典的贪婪算法应用场景。假设有一些活动，每个活动都有开始时间和结束时间。我们需要选择一些活动，使得这些活动之间不会冲突，并且选出的活动数量最多。活动安排问题在现实生活中有很多应用，例如会议安排、任务调度、考试安排等。活动安排问题的贪婪算法1排序根据活动结束时间进行排序2选择选择最早结束的活动3迭代重复选择直到没有更多活动贪婪算法选择最早结束的活动，以此类推。每次选择都尽量选择最早结束的活动，以最大化活动数量。这种方法能保证在活动结束后，有更多时间安排后续活动。活动安排问题的贪婪算法实现排序根据活动结束时间排序，将活动按结束时间升序排列。选择从排序后的活动列表中选择第一个活动，并将其加入活动安排集合中。迭代遍历剩余活动，如果当前活动开始时间大于等于已安排活动结束时间，则选择当前活动，并将其加入活动安排集合中。结束重复迭代步骤，直到所有活动都被遍历完。活动安排问题的代价分析时间复杂度贪婪算法的时间复杂度通常较低，通常为O(nlogn)，其中n是活动的数目。空间复杂度空间复杂度也较低，通常为O(n)，因为只需要存储活动的开始时间和结束时间。性能贪婪算法的性能取决于活动安排问题的具体情况，但在大多数情况下，它能有效地找到最佳解决方案。例子三:哈夫曼编码问题哈夫曼编码是一种常用的数据压缩技术，它可以有效地压缩文本数据。哈夫曼编码问题的描述11.数据压缩哈夫曼编码是一种数据压缩技术，利用字符出现的频率来构建编码表。22.编码效率高频字符分配短编码，低频字符分配长编码，以提高压缩效率。33.构建哈夫曼树通过构建哈夫曼树来生成编码表，并使用前缀码来避免歧义。44.应用场景广泛应用于数据压缩、图像处理、文本压缩等领域。哈夫曼编码问题的贪婪算法1创建最小堆将所有字符及其频率构建成最小堆，堆顶元素为频率最小的字符。2合并最小节点取出堆顶两个节点，合并成一个新节点，新节点的频率为两个节点频率之和。3重复合并将新节点加入堆中，重复步骤2直到堆中只剩下一个节点。4构建编码表根据合并过程，为每个字符构建对应的编码，频率越高的字符，编码长度越短。哈夫曼编码问题的贪婪算法实现1建立频率树将每个字符与其频率一起放入树中2合并最小频率节点重复合并频率最小的两个节点3生成哈夫曼树直到只剩下一个节点4分配编码为每个字符分配编码哈夫曼编码问题的代价分析时间复杂度哈夫曼编码算法的时间复杂度主要取决于构建哈夫曼树的步骤，其复杂度为O(nlogn)，其中n为字符的个数。空间复杂度哈夫曼编码算法的空间复杂度主要取决于哈夫曼树的大小，其空间复杂度为O(n)，其中n为字符的个数。贪婪算法的优缺点总结优点简单易懂、实现方便，适合解决一些特定类型的问题。优点速度快，效率高，适合处理大量数据，尤其在时间要求严格的情况下。缺点无法保证找到最优解，可能陷入局部最优，导致最终结果不够理想。缺点适用范围有限，不适用于所有问题，需要根据问题特征进行判断。贪婪算法的设计技巧选择合适的贪婪标准贪婪标准是算法的核心，它决定了每次选择的最佳元素，应根据问题特性选择合适的标准，以最大限度地提高算法效率。检查贪婪选择性质要确保每次贪婪选择都不会导致后续选择无法得到全局最优解，可以通过反证法或归纳法证明。避免局部最优贪婪算法可能陷入局部最优解，无法找到全局最优解，可通过回溯或分支限界等技术来克服局部最优问题。贪婪算法的局限性最优解贪婪算法不一定能找到最优解，它只保证局部最优，可能会导致全局最优的损失。问题结构贪婪算法适用于具有特定结构的问题，对某些结构复杂的问题，贪婪算法可能失效。回溯贪婪算法无法回溯，一旦做出选择，就无法撤销，这可能导致错误的最终结果。贪婪算法与其他算法的比较11.效率贪婪算法通常效率很高，因为它们只考虑当前最佳选择。它们通常比动态规划或回溯算法更快执行。22.最优性贪婪算法不一定总是找到最优解。它们提供局