贪心算法介绍(Greedy Algorithm)

1. 贪心算法概念简介

​ 贪心算法Greedy Algorithm是一种在每一步选择中都采取当前状态下最优(或最有利)决策的算法策略,以期望通过这样的局部最优决策达到全局最优解。它适用于那些具有最优子结构的问题,即问题的最优解包含其子问题的最优解。贪心算法的关键在于它做出的选择是不可逆的,一旦选择了某个选项,就不会再回溯考虑其他选项。

  • 通过示例来感受贪心算法的思想

2. 贪心算法的特点

  1. 贪心选择性质

    • 贪心算法在每一步都做出当前看起来最优的选择,而不考虑这个选择对未来步骤的影响。这种选择是基于问题的贪心选择性质,即问题具有这样的结构:局部最优选择可以导致全局最优解。
  2. 无回溯

    • 与动态规划等其他算法不同,贪心算法做出选择后不会回溯。这意味着一旦做出了一个贪心选择,算法就会继续前进,即使这个选择在后来看起来可能不是最佳选择。

  3. 子问题局部最优

    • 贪心算法通常用于具有最优子结构的问题,即一个问题的最优解包含其子问题的最优解。这种特性允许算法在构建解决方案的过程中,利用子问题的局部最优解。
  4. 简单高效

    • 贪心算法通常易于理解和实现,因为它的决策过程直观且不需要复杂的优化过程。此外,由于贪心算法不需要存储所有可能的解决方案,因此它在空间复杂度上通常很低。
  5. 不保证全局最优

    • 尽管贪心算法在某些问题上能够找到全局最优解,但它并不保证在所有情况下都能找到。这取决于问题本身是否满足贪心选择性质和最优子结构。

3. 贪心算法的应用场景

  • 物流优化:在物流配送中,使用贪心算法来规划最短或最快路径,例如快递员的包裹派送顺序,以减少行驶距离和时间 。
  • 网络路由选择:在计算机网络中,通过贪心算法选择数据传输的最优路径,例如OSPF(开放最短路径优先)协议 。
  • 任务调度:在计算机系统中,贪心算法用于CPU任务调度,选择优先级最高或最早截止时间的任务先执行 。
  • 数据压缩:霍夫曼编码是一种使用贪心算法的数据压缩技术,通过为频繁出现的字符分配较短的编码来优化存储空间 。
  • 股票交易分析:在金融领域,贪心算法可以用来模拟股票买卖,选择最优的买入和卖出时机以最大化利润 。
  • 广告投放:在广告行业,通过贪心算法优化广告投放策略,选择最有效的广告组合和展示顺序以吸引用户 。

4. 贪心算法的优缺点

  • 优点
  1. 简单高效:贪心算法通常易于理解和实现,执行速度快,不需要复杂的优化过程。
  2. 快速得到解决方案:贪心算法能够迅速给出问题的解决方案,对于需要即时决策的问题特别有用。
  3. 空间效率高:由于其决策过程不需要存储所有可能的解决方案,因此空间复杂度通常较低。
  4. 适应性广:贪心算法可以应用于多种问题领域,如资源分配、路径选择、任务调度等。
  5. 启发式方法:作为一种启发式算法,贪心算法用于快速找到一个可接受的解决方案,而不是总是寻找最优解。
  • 缺点
  1. 不保证全局最优:贪心算法在某些情况下可能无法得到全局最优解,特别是当问题不具有贪心选择性质时。
  2. 依赖于问题结构:贪心算法的成功依赖于问题是否具有最优子结构,对于不具备这种结构的问题可能不适用。
  3. 可能错过更优解:由于贪心算法的决策是不可逆的,一旦做出选择就不再回溯,可能会错过更优的解决方案。
  4. 局限性:对于一些NP难问题,贪心算法可能只能得到局部最优解,而不是绝对最优解。
  5. 需要问题证明:在使用贪心算法时,需要证明其正确性,这可能需要一些数学推理和证明工作。

5. 贪心算法的实现步骤

  1. 明确问题

    • 确定你要解决的问题是什么,比如分配资源、选择任务、规划路径等。
  2. 理解贪心选择

    • 找出问题中可以应用贪心选择的地方,即在每一步选择中都采取当前看起来最好的决策。
  3. 设定目标

    • 确定你的“贪心目标”是什么,也就是你希望通过贪心选择达到什么样的效果,比如最小化成本、最大化利润等。
  4. 准备数据

    • 收集并准备所有需要的数据,比如资源数量、任务列表、路径信息等。
  5. 排序或组织数据

    • 根据你的目标,可能需要对数据进行排序或以某种方式组织,以便贪心选择可以更容易进行。
  6. 执行贪心策略

    • 从第一步开始,每次都选择当前看起来最佳的选项。例如,如果你的目标是最小化成本,那么就选择成本最低的选项。
  7. 更新选择状态

    • 每次做出选择后,更新当前的状态,这可能意味着从可用选项中移除已选择的选项,或者更新剩余资源的数量。
  8. 重复选择过程

    • 继续执行贪心选择,直到所有的选项都被选择完,或者达到某个特定的条件。
  9. 检查结果

    • 完成所有步骤后,检查你的结果是否满足问题的要求。
  10. 评估和调整

    • 如果结果不是预期的,可能需要回到前面的步骤,调整你的贪心策略或选择标准。

举个例子,如果要用贪心算法来安排一天的工作,步骤可能是这样的:

  • 确定你要完成的所有工作任务。
  • 决定你的贪心目标,比如完成最多的任务或完成最重要的任务。
  • 列出每个任务需要的时间和重要性。
  • 根据任务的紧急程度或重要性对任务进行排序。
  • 从列表的顶部开始,逐个选择任务,并安排到你的日程中。
  • 每次选择后,更新你的日程表,直到所有任务都被安排或时间被填满。
  • 最后,检查你的日程表,确保所有任务都已妥善安排。

6. 贪心算法与其他算法的比较

7. 贪心算法的示例演示

示例1:分糖果问题

简介:有一组孩子的胃口值 g 和一组糖果的大小 s,我们要尽量多的满足孩子。每个孩子只能拿到一个糖果,且只有当糖果的大小大于或等于孩子的胃口值时,孩子才能满足。

思维过程

  1. 目标:最大化能满足的孩子数量。
  2. 贪心选择:每次优先满足胃口最小的孩子,因为大胃口的孩子可以用大糖果来满足,但小胃口的孩子需要较小的糖果。
  3. 步骤分析:
    • 首先对孩子的胃口和糖果的大小进行排序,以便从最小的胃口和最小的糖果开始比较。
    • 然后,逐一遍历糖果,尝试将糖果分给胃口最小的孩子。
    • 如果糖果能够满足当前孩子,就给这个孩子糖果,并继续考虑下一个孩子。
    • 最后,统计并返回能够满足的孩子数量。
def findContentChildren(g, s):
    # 对孩子的胃口和糖果大小进行排序
    g.sort()
    s.sort()

    # 用于统计能够满足的孩子数量
    child_i = 0

    # 遍历每个糖果的大小
    for size in s:
        # 如果当前孩子的胃口能被满足
        if child_i < len(g) and size >= g[child_i]:
            child_i += 1  # 孩子得到了糖果

    # 返回能够满足的孩子数量
    return child_i


# 测试
g = [1, 2, 5, 4, 3, 666]  # 孩子的胃口值
s = [1, 2, 1, 1]  # 糖果的大小
print(findContentChildren(g, s))  # 输出: 2

示例2:零钱兑换问题

简介:给定一些硬币面值 coins 和一个目标金额 amount,找到能够凑成该金额的最少硬币数。

思维过程

  1. 目标:最小化使用的硬币数量。
  2. 贪心选择:每次选择面值最大的硬币,这样可以尽快减少剩余的金额,减少所需的硬币数量。
  3. 步骤分析:
    • 将硬币按面值从大到小排序,以便优先使用大面值的硬币。
    • 依次从最大的硬币开始,计算该硬币可以使用多少次,减少目标金额。
    • 剩余金额用更小面值的硬币继续凑。
    • 最后,如果能完全凑成目标金额,就返回硬币数量;否则返回 -1。
def coinChange(coins, amount):
    # 将硬币面值从大到小排序
    coins.sort(reverse=True)
    count = 0  # 统计使用的硬币数量

    # 遍历每种面值的硬币
    for coin in coins:
        if amount == 0:  # 如果金额已经为0,停止
            break
        count += amount // coin  # 使用最大面值硬币的最大数量
        amount %= coin  # 更新剩余金额

    # 如果金额能够被完全兑换,返回硬币数量,否则返回-1
    return count if amount == 0 else -1


# 测试
coins = [1, 2, 5]  # 硬币面值
amount = 11  # 目标金额
print(coinChange(coins, amount))  # 输出: 3

示例3:区间调度问题

简介:给定一组时间区间 intervals,找出最多的互不重叠的区间数。例如,多个会议时间重叠的情况下,最多能够安排多少场不冲突的会议。

思维过程

  1. 目标:最大化选择的区间数量。
  2. 贪心选择:每次选择结束时间最早且与前一个区间不重叠的区间,这样可以给后续的区间留出更多的时间。
  3. 步骤分析:
    • 首先按区间的结束时间进行排序,以便优先考虑结束时间早的区间。
    • 从第一个区间开始,选择它作为第一个非重叠区间,并记录它的结束时间。
    • 依次考虑后续的区间,如果它的开始时间不早于前一个区间的结束时间,就选择这个区间,并更新结束时间。
    • 最后,返回选择的区间数量。
def intervalSchedule(intervals):
    # 根据区间的结束时间进行排序
    intervals.sort(key=lambda x: x[1])
    count = 0  # 统计能够安排的区间数量
    end = float('-inf')  # 记录上一个选择的区间的结束时间

    # 遍历所有区间
    for interval in intervals:
        if interval[0] >= end:  # 如果当前区间的开始时间大于等于上一个区间的结束时间
            count += 1  # 选择当前区间
            end = interval[1]  # 更新结束时间

    # 返回能够安排的最大区间数量
    return count


# 测试
intervals = [[1, 3], [2, 4], [3, 5]]  # 时间区间
print(intervalSchedule(intervals))  # 输出: 2

示例4:分配会议室问题

简介:给定一组会议的开始和结束时间intervals,找出需要的最少会议室数量,以确保所有会议都能安排上。

思维过程

  1. 目标:最小化同时进行的会议数(即需要的会议室数)。
  2. 贪心选择:每次安排一个会议时,检查最早结束的会议是否已经结束,如果结束了就可以复用该会议室,否则需要新开一个会议室。
  3. 步骤分析:
    • 先将所有会议按开始时间排序。
    • 使用一个最小堆来跟踪当前所有正在进行的会议的结束时间。
    • 对于每个会议,如果它的开始时间不早于最早结束的会议的结束时间,则表示可以复用一个会议室,更新堆中的结束时间。
    • 否则,需要新开一个会议室,将会议的结束时间加入堆中。
    • 最后,堆的大小就是需要的最少会议室数量。
import heapq


def minMeetingRooms(intervals):
    if not intervals:
        return 0

    # 根据会议的开始时间进行排序
    intervals.sort(key=lambda x: x[0])

    # 初始化一个最小堆,用于存储当前进行的会议的结束时间
    heap = []
    heapq.heappush(heap, intervals[0][1])  # 将第一个会议的结束时间加入堆中

    # 遍历剩余的会议
    for i in intervals[1:]:
        # 如果当前会议的开始时间大于等于堆顶的结束时间
        if i[0] >= heap[0]:
            heapq.heappop(heap)  # 移除堆顶的会议,因为它已经结束了
        heapq.heappush(heap, i[1])  # 将当前会议的结束时间加入堆中

    # 最后堆的大小就是需要的会议室数量
    return len(heap)


# 测试
intervals = [[0, 30], [5, 10], [15, 20], [5, 20], [35, 40]]  # 会议时间区间
print(minMeetingRooms(intervals))  # 输出: 3

示例5:最大子数组和问题

简介:在一个整数数组 nums 中,找到和最大的连续子数组,并返回其最大和。

思维过程

  1. 目标:找到和最大的连续子数组。
  2. 贪心选择:每次都判断是将当前元素加入到之前的子数组中,还是重新开始一个新的子数组,从而保证当前的子数组和尽可能大。
  3. 步骤分析:
    • 初始化当前子数组和 current_sum 和最大子数组和 max_sum 为第一个元素。
    • 从第二个元素开始,逐个判断:
      • 当前元素是否比 current_sum + 当前元素 更大。如果是,则抛弃之前的子数组,重新开始;否则将当前元素加入到当前子数组中。
    • 每次更新最大子数组和 max_sum
    • 最终返回最大子数组和。
def maxSubArray(nums):
    max_sum = nums[0]  # 初始化最大和为数组的第一个元素
    current_sum = nums[0]  # 当前子数组的和

    # 遍历数组的其余元素
    for num in nums[1:]:
        # 如果当前子数组的和加上当前元素还不如当前元素本身大,就丢弃当前子数组,重新开始
        current_sum = max(num, current_sum + num)
        # 更新最大和
        max_sum = max(max_sum, current_sum)

    # 返回最大子数组和
    return max_sum


# 测试
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]  # 输入数组
print(maxSubArray(nums))  # 输出: 6

8. 贪心算法的回顾总结

贪心算法是一种在每一步选择中都采取当前最优解的策略,以期望构建出全局最优解的算法。它的核心思想是“贪心选择性质”,即在每个决策点上,基于当前信息选择最有利的选项,从而希望通过这些局部最优决策累积成全局最优解。贪心算法的实现通常简单直接,易于编码,且执行效率高,这使得它在需要快速响应的大规模问题中非常有用。

贪心算法的关键在于其贪心策略的选择,这通常涉及到对问题结构的深入理解。在某些问题中,贪心算法能够保证找到最优解,特别是当问题具有最优子结构和贪心选择性质时。然而,并非所有问题都适合使用贪心算法,有些情况下贪心算法可能只能得到局部最优解而非全局最优解。

贪心算法的一个显著特点是其决策过程是单向的,不会回溯。这意味着一旦做出选择,算法不会重新考虑之前的决策,即使这些决策最终可能不是最佳选择。这种特性使得贪心算法在时间效率上具有优势,但同时也限制了它在某些需要全局考虑的问题上的适用性。

贪心算法广泛应用于资源分配、路径规划、任务调度、数据压缩等领域。例如,在霍夫曼编码中用于数据压缩,在Dijkstra算法中用于寻找单源最短路径。尽管贪心算法在某些情况下可能需要结合其他算法来优化其策略,但其作为一种高效且直观的算法,仍然在算法设计和优化问题解决中占有重要地位。

08-15 15:47