活动选择问题：贪心算法与动态规划算法比较

本文介绍了活动选择问题，并使用 Python 代码实现了贪心算法和动态规划算法来解决该问题。

import random
import time
import numpy as np
import matplotlib.pyplot as plt


def generate_activities(n):  # 生成n个活动的起始时间和结束时间
    activities = []
    for i in range(n):
        start_time = random.randint(0, 100)
        end_time = start_time + random.randint(1, 10)
        activities.append((start_time, end_time))
    return activities


def greedy_activity_selection(activities):  # 贪心算法
    activities.sort(key=lambda x: x[1])  # 按结束时间排序确保每次选择的活动都是结束时间最早的活动。使用lambda表达式指定排序的依据。
    selected_activities = []
    current_end_time = 0
    for activity in activities:
        if activity[0] >= current_end_time:
            selected_activities.append(activity)  # 如果活动的起始时间大于等于当前活动的结束时间，则添加到selected_activities中
            current_end_time = activity[1]  # 更新当前活动的结束时间为选中的活动
    return selected_activities


def dynamic_programming_activity_selection(activities):  # 动态规划算法，选择一组互相兼容的活动，使得可以参加的活动数量最大,接受活动列表
    n = len(activities)                               #每个活动都是一个元组，包含活动的起始时间和结束时间
    activities.sort(key=lambda x: x[1])  # 按结束时间排序
    dp = [1] * n  # 初始化dp数组，用于记录每个活动的最大兼容子集大小
    for i in range(1, n):
        for j in range(i):                           #两层循环遍历活动列表
            if activities[i][0] >= activities[j][1]:  # 如果活动i的起始时间大于等于活动j的结束时间，则活动i可以加入活动j的最大兼容子集
                dp[i] = max(dp[i], dp[j] + 1)          #更新dp[i]为dp[j]+1和dp[i]中大的一个
    max_activities = max(dp)  # 最大兼容子集的大小
    selected_activities = []  # 存储选中的活动
    current_end_time = float('-inf')  # 当前活动的结束时间
    for i in range(n - 1, -1, -1):                     #倒序遍历数组
        if dp[i] == max_activities and activities[i][1] >= current_end_time:
            selected_activities.append(activities[i])  # 如果活动i的最大兼容子集大小等于最大兼容子集的大小，
                                                                 #并且活动i的结束时间大于等于当前活动的结束时间，则选中该活动
            current_end_time = activities[i][0]  # 更新当前活动的结束时间为该活动的起始时间
            max_activities -= 1  # 最大兼容子集的大小减1
    return selected_activities[::-1]  # 返回选中的活动列表，按照起始时间升序排序


def compare_execution_time():
    n_values = [8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096]  # 不同活动数量的取值
    greedy_times = []
    dp_times = []
    for n in n_values:
        activities = generate_activities(n)

        start_time = time.time()
        greedy_activity_selection(activities)
        end_time = time.time()
        greedy_times.append(end_time - start_time)

        start_time = time.time()
        dynamic_programming_activity_selection(activities)
        end_time = time.time()
        dp_times.append(end_time - start_time)
    print(greedy_times)
    print(dp_times)


    smooth_N = np.linspace(min(n_values), max(n_values), 100)  # 生成平滑的活动数量序列
    curve_brute_force = np.polyfit(n_values, greedy_times, 3)  # 对贪心算法的执行时间进行拟合
    curve_backtrack = np.polyfit(n_values, dp_times, 3)  # 对动态规划的执行时间进行拟合
    smooth_times_backtrack = np.polyval(curve_brute_force, smooth_N)# 根据拟合曲线计算平滑的执行时间
    smooth_times_branch_bound = np.polyval(curve_backtrack, smooth_N)
    plt.plot(smooth_N, smooth_times_branch_bound, label='Dynamic Programming')
    plt.plot(smooth_N, smooth_times_backtrack, label='Greedy')
    plt.xlabel('Number of activities')
    plt.ylabel('Execution time')
    plt.legend()
    plt.show()


compare_execution_time()
解释上述代码的贪心法和动态规划法的算法策略内容：上述代码中实现了贪心算法和动态规划算法来解决活动选择问题。

贪心算法的策略是每次选择结束时间最早的活动，即选择当前能参加的活动中结束时间最早的活动。通过将活动按结束时间排序，然后遍历活动列表，如果当前活动的起始时间大于等于当前活动的结束时间，则将该活动加入选中的活动列表中。最终返回选中的活动列表。

动态规划算法的策略是选择一组互相兼容的活动，使得可以参加的活动数量最大。首先将活动按结束时间排序，然后初始化一个大小为活动数量的dp数组，用于记录每个活动的最大兼容子集大小。然后通过两层循环遍历活动列表，如果活动i的起始时间大于等于活动j的结束时间，则活动i可以加入活动j的最大兼容子集。最后遍历dp数组，找出最大兼容子集的大小，并根据最大兼容子集的大小和活动的结束时间来选出活动。返回选中的活动列表。

代码中还实现了一个比较执行时间的函数compare_execution_time，用于比较贪心算法和动态规划算法在不同活动数量下的执行时间，并绘制执行时间曲线图。

贪心算法

• 策略: 每次选择结束时间最早的活动，确保后续可以参加更多的活动。
• 步骤:
  1. 按结束时间对活动列表排序。
  2. 遍历排序后的活动列表，如果当前活动的起始时间大于等于当前活动结束时间，则选择该活动，并更新当前活动结束时间。
• 时间复杂度: O(n log n)，主要来自排序操作。

动态规划算法

• 策略: 找到一个包含最多互相兼容活动的子集。
• 步骤:
  1. 按结束时间对活动列表排序。
  2. 初始化一个大小为活动数量的dp数组，用于记录每个活动的最大兼容子集大小。
  3. 遍历活动列表，对于每个活动i，遍历其前面的所有活动j，如果活动i的起始时间大于等于活动j的结束时间，则更新dp[i]为dp[j] + 1和dp[i]中较大的值。
  4. 遍历dp数组，找到最大兼容子集的大小。
  5. 根据最大兼容子集的大小和活动的结束时间选出活动。
• 时间复杂度: O(n^2)，需要两层循环遍历活动列表。

比较

• 贪心算法在时间复杂度上优于动态规划算法，但它可能无法找到最优解。
• 动态规划算法能够找到最优解，但时间复杂度较高。

总结

在活动选择问题中，贪心算法可以作为一种快速且易于实现的近似算法，而动态规划算法可以找到最优解，但需要更高的计算资源。选择哪种算法取决于具体的需求和限制。