第6章 贪心算法.ppt

贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法策略。它并不保证一定能得到全局最优解，但通常在很多情况下能得到近似最优解。贪心算法的特点在于其局部最优策略，即每一步都做出看起来最好的选择，而不考虑这个选择对未来的影响，只要这个选择满足无后效性，即后续过程不会影响之前的状态。 贪心算法的实现通常包含以下几个步骤： 1. 定义问题的数学模型，明确问题的求解目标。 2. 将问题分解为一系列子问题，每个子问题都是原问题的一部分。 3. 对每个子问题找到局部最优解。 4. 将这些局部最优解合并，形成原问题的一个解。 在实际应用中，贪心策略的选择至关重要。例如在“排队打水问题”中，通过将打水时间按从小到大排序，使得每个人尽可能早地打水，从而减少总体等待时间，这就是一个贪心策略。该策略满足无后效性，因为一旦确定了打水顺序，后面的人不受前面人打水顺序的影响。 另一个例子是“均分纸牌问题”，在这个问题中，通过不断将纸牌从多的一堆移动到少的一堆，逐步让每堆的纸牌数趋向于平均值，也是一个贪心策略。每次移动都是为了减少纸牌数量的差异，最终达到最小化移动次数的目标。 在编写贪心算法的程序时，通常会有一个循环结构，每次循环中选择一个局部最优的决策，直到达到问题的终止条件。例如在上述两个示例中，都是通过迭代的方式，根据贪心策略进行操作，直至问题解决。 然而，贪心算法并不适用于所有问题。例如，当局部最优解不能保证全局最优解时，如旅行商问题，贪心算法就不能得到正确的答案。因此，在使用贪心算法时，必须仔细分析问题，确保所选策略能满足无后效性，并且可能达到全局最优解。 总结起来，贪心算法是一种以局部最优解为导向，逐步构建全局解的策略。它在某些特定问题中表现出高效性和简洁性，但并非对所有问题都适用。在实际应用中，需要谨慎选择和验证贪心策略的有效性。