贪心算法与动态规划算法求解活动选择问题及性能比较

问题描述

设有n个活动的集合E={1, 2, ..., n},其中每个活动都要求使用同一资源,且同一时间内只有一个活动能使用该资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si < fi。如果选择了活动i,则它在半开时间区间[si, fi)内占用资源。若区间[si, fi)与区间[sj, fj)不相交,则称活动i与活动j是相容的。

目标

随机生成n个任务(n=8,16,32...), 分别使用贪心算法和动态规划算法求解活动选择问题,并比较两种算法的执行时间和结果。

算法描述

1. 贪心算法

贪心算法的基本思路是每次选择结束时间最早的活动,从而尽可能多地选择活动。

2. 动态规划算法

动态规划算法通过构建一个dp数组来记录每个子问题的最优解,最终得到全局最优解。

代码实现 (Python)pythonimport randomimport time

贪心算法def greedy_activity_selection(s, f): n = len(s) selected = [0] * n selected[0] = 1 j = 0 for i in range(1, n): if s[i] >= f[j]: selected[i] = 1 j = i return selected

动态规划算法def dp_activity_selection(s, f): n = len(s) dp = [0] * n dp[0] = 1 for i in range(1, n): dp[i] = max(dp[j] + 1 for j in range(i) if f[j] <= s[i]) selected = [] j = dp.index(max(dp)) selected.append(j) for i in range(j-1, -1, -1): if f[i] <= s[j] and dp[i] == dp[j] - 1: selected.append(i) j = i selected.reverse() return selected

生成随机任务def generate_random_tasks(n): s = [] f = [] for i in range(n): start_time = random.randint(1, 100) end_time = start_time + random.randint(1, 10) s.append(start_time) f.append(end_time) return s, f

测试函数def test_algorithm(algorithm, n): s, f = generate_random_tasks(n) start_time = time.time() selected = algorithm(s, f) end_time = time.time() execution_time = end_time - start_time print(f'算法: {algorithm.name}, 任务数量: {n}') print(f'选择活动: {selected}') print(f'执行时间: {execution_time:.6f} 秒')

测试不同规模的任务数量for n in [8, 16, 32, 64, 128]: test_algorithm(greedy_activity_selection, n) test_algorithm(dp_activity_selection, n) print('-' * 20)

实验结果分析

  • 从实验结果可以观察到,贪心算法的执行时间随着任务数量的增加而线性增长,而动态规划算法的执行时间随着任务数量的增加呈指数增长。- 对于该问题,贪心算法不一定会得到最优解。贪心算法每次选择结束时间最早的活动,因此可能会错过一些后续活动,导致选择的活动数量不是最大的。而动态规划算法通过构建一个dp数组来记录每个子问题的最优解,可以得到最优解。

结论

  • 贪心算法简单易实现,时间复杂度低,但对于活动选择问题不一定能得到最优解。- 动态规划算法可以得到最优解,但时间复杂度较高。- 在实际应用中,需要根据具体情况选择合适的算法。
贪心算法与动态规划算法求解活动选择问题及性能比较

原文地址: https://www.cveoy.top/t/topic/fwlu 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录