王亭_666

王亭_666

关注
发信
关注(28)粉丝(399)

贪心算法介绍（Greedy Algorithm）

贪心算法介绍（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
Powered by LMLPHP ©2024 王亭_666 0.006657