贪心算法与动态规划求解活动选择问题及性能比较
活动选择问题:贪心算法 vs 动态规划
问题描述: 设有n个活动的集合E={1, 2, ..., n},其中每个活动都需要占用同一资源,且资源在同一时间只能被一个活动占用。每个活动i的起始时间为si,结束时间为fi,其中si < fi。若区间[si, fi)与区间[sj, fj)不相交,则活动i与活动j相容。目标是选择最大的相容活动子集。
本文将分别使用贪心算法和动态规划求解该问题,并比较两种算法的性能。
1. 贪心算法
思路: 每次选择结束时间最早且与已选择活动相容的活动。
**Python代码:**pythondef activity_selection(start_time, finish_time): n = len(start_time) selected_activities = [] # 将活动按照结束时间排序 activities = sorted(zip(start_time, finish_time), key=lambda x: x[1]) # 选择第一个活动 selected_activities.append(activities[0]) # 遍历剩下的活动 for i in range(1, n): # 如果当前活动与已选择的最后一个活动相容,选择该活动 if activities[i][0] >= selected_activities[-1][1]: selected_activities.append(activities[i]) return selected_activities
2. 动态规划
思路: 构建二维数组dp,dp[i][j]表示在活动i到活动j之间选择的最大活动数。
递推关系: dp[i][j] = max(dp[i][j-1], dp[i-1][k] + 1),其中k是最后一个与活动j相容的活动。
**Python代码:**pythondef optimal_activity_selection(start_time, finish_time): n = len(start_time) activities = sorted(zip(start_time, finish_time), key=lambda x: x[1]) # 初始化dp数组 dp = [[0] * n for _ in range(n)] # 计算dp数组 for j in range(1, n): for i in range(j-1, -1, -1): if activities[i][1] <= activities[j][0]: dp[i][j] = max(dp[i][j-1], dp[k][i-1] + 1) else: dp[i][j] = dp[i][j-1] # 回溯找出最优解 selected_activities = [] j = n - 1 for i in range(n-1, -1, -1): if dp[i][j] > dp[i-1][j]: selected_activities.append(activities[i]) j = i - 1 return selected_activities[::-1]
3. 性能比较
实验设计: 随机生成不同规模的活动数据,分别使用贪心算法和动态规划求解,记录执行时间。
**代码实现:**pythonimport timeimport matplotlib.pyplot as plt
def generate_activities(n): start_time = [i for i in range(1, n+1)] finish_time = [i+1 for i in range(1, n+1)] return start_time, finish_time
def compare_execution_time(): n_values = [8, 16, 32, 64, 128, 256, 512, 1024] greedy_times = [] optimal_times = [] for n in n_values: start_time, finish_time = generate_activities(n) # 计算贪心法的执行时间 start = time.time() activity_selection(start_time, finish_time) end = time.time() greedy_times.append(end - start) # 计算动态规划的执行时间 start = time.time() optimal_activity_selection(start_time, finish_time) end = time.time() optimal_times.append(end - start) # 绘制执行时间随n的变化曲线 plt.plot(n_values, greedy_times, label='Greedy') plt.plot(n_values, optimal_times, label='Optimal') plt.xlabel('Number of activities') plt.ylabel('Execution time (s)') plt.legend() plt.show()
compare_execution_time()
实验结果: 实验结果表明,贪心算法的执行时间远小于动态规划,特别是在活动数量较大时,差异更加明显。
结论:
- 贪心算法时间复杂度为O(nlogn),效率较高,但不能保证得到最优解。- 动态规划时间复杂度为O(n^2),可以得到最优解,但效率相对较低。
选择建议:
- 如果对解的质量要求不高,追求效率,可以选择贪心算法。- 如果需要得到最优解,可以考虑使用动态规划,但需要注意时间复杂度。
原文地址: https://www.cveoy.top/t/topic/fwlY 著作权归作者所有。请勿转载和采集!