贪心法求解活动安排问题及与动态规划法比较
活动安排问题:贪心法与动态规划法比较
本文探讨使用贪心算法和动态规划算法解决活动安排问题。我们首先介绍问题背景,然后分别使用 Python 实现两种算法,并通过实验比较它们的执行时间和结果。最后,我们将分析两种算法的优缺点,并讨论在实际应用中如何选择合适的算法。
问题描述
设有 n 个活动的集合 E={1, 2, ..., n},其中每个活动都需要占用同一资源,且同一时间该资源只能被一个活动占用。每个活动 i 有一个起始时间 si 和结束时间 fi,且 si < fi。当活动 i 被选择后,它将在半开时间区间 [si, fi) 内占用资源。如果区间 [si, fi) 与区间 [sj, fj) 不相交,则称活动 i 和 j 是相容的。目标是在 E 中选择最大的相容活动子集。
算法实现
1. 贪心算法
贪心算法的基本思想是:每次选择结束时间最早的活动,从而尽可能多地安排活动。pythonimport randomimport timeimport matplotlib.pyplot as plt
贪心算法求解近似解def greedy_activity_selection(start_times, finish_times): n = len(start_times) activities = list(range(n)) activities.sort(key=lambda x: finish_times[x]) # 按结束时间排序
selected_activities = [activities[0]] # 选择第一个活动 last_finish_time = finish_times[activities[0]]
for i in range(1, n): if start_times[activities[i]] >= last_finish_time: selected_activities.append(activities[i]) last_finish_time = finish_times[activities[i]]
return selected_activities
2. 动态规划算法
动态规划算法通过构建一个二维表格来记录子问题的最优解,最终得到原问题的最优解。python# 动态规划算法求解最优解def dp_activity_selection(start_times, finish_times): n = len(start_times) dp = [0] * (n+1) activities = list(range(n)) activities.sort(key=lambda x: finish_times[x]) # 按结束时间排序
for i in range(1, n+1): j = i - 1 while j >= 0 and finish_times[activities[j]] > start_times[activities[i-1]]: j -= 1 dp[i] = max(dp[i-1], dp[j+1] + 1)
selected_activities = [] i = n while i > 0: if dp[i] > dp[i-1]: selected_activities.append(activities[i-1]) i = i - dp[i] else: i -= 1
selected_activities.reverse() return selected_activities
实验结果
我们随机生成不同数量的任务 (n=8, 16, 32...), 分别使用贪心算法和动态规划算法求解,并记录它们的执行时间。结果如下图所示:python# 生成随机任务def generate_tasks(n): start_times = [] finish_times = [] for i in range(n): start_time = random.randint(0, 100) finish_time = start_time + random.randint(1, 10) start_times.append(start_time) finish_times.append(finish_time) return start_times, finish_times
测试贪心算法和动态规划算法的执行时间def test_execution_time(): n_values = [8, 16, 32, 64, 128, 256, 512] greedy_times = [] dp_times = []
for n in n_values: start_times, finish_times = generate_tasks(n)
start = time.time() greedy_activity_selection(start_times, finish_times) end = time.time() greedy_times.append(end - start)
start = time.time() dp_activity_selection(start_times, finish_times) end = time.time() dp_times.append(end - start)
plt.plot(n_values, greedy_times, label='Greedy') plt.plot(n_values, dp_times, label='Dynamic Programming') plt.xlabel('Number of Tasks') plt.ylabel('Execution Time (s)') plt.legend() plt.show()
执行测试test_execution_time()

从图中可以看出,贪心算法的执行时间随任务数量的增加呈线性增长,而动态规划算法的执行时间呈指数增长。
结论
-
效率: 贪心算法的时间复杂度为 O(nlogn), 而动态规划算法的时间复杂度为 O(n^2)。因此,在处理大规模问题时,贪心算法效率更高。
-
最优解: 贪心算法不一定能得到最优解,因为它只考虑了当前的最优选择,而没有考虑全局的最优解。而动态规划算法能够保证得到全局最优解。
算法选择
在实际应用中,如果对算法的执行效率要求较高,且能够接受近似解,则可以选择贪心算法。如果要求得到精确的最优解,则可以选择动态规划算法。
原文地址: https://www.cveoy.top/t/topic/fwlz 著作权归作者所有。请勿转载和采集!