贪心算法与动态规划求解活动选择问题及Python代码实现
贪心算法与动态规划求解活动选择问题及Python代码实现
问题描述
设有n个活动的集合E={1, 2, ..., n},其中每个活动都需要占用同一资源,且资源同一时间只能被一个活动占用。每个活动i都有一个起始时间si和结束时间fi,且si < fi。活动i占用资源的时间区间为[si, fi)。若区间[si, fi)与区间[sj, fj)不相交,则称活动i与活动j是相容的。
目标:求解能够选择的最大相容活动集合。
算法描述
1. 贪心算法
思路: 每次选择结束时间最早的活动,然后将与该活动相容的活动从集合中删除,直到集合为空。
步骤:
- 将活动按照结束时间从小到大进行排序。2. 初始化一个空集合S,用于存放最大相容活动集合。3. 将第一个活动加入集合S。4. 对于剩下的活动,依次判断是否与集合S中的活动相容,如果相容则将该活动加入集合S。5. 返回集合S作为近似解。
2. 动态规划算法
思路: 将问题分解成子问题,通过求解子问题的最优解来得到原问题的最优解。
步骤:
- 将活动按照结束时间从小到大进行排序。2. 初始化一个数组dp,其中dp[i]表示以第i个活动为最后一个活动的最大相容活动集合的大小。3. 对于每个活动i,计算dp[i]的值: - 如果活动i是第一个活动,则dp[i]为1。 - 否则,遍历之前的每个活动j,如果活动i与活动j相容,则dp[i]为dp[j]+1和dp[i]中的较大值。4. 返回dp数组中的最大值作为最优解的大小。
Python代码实现pythonimport timeimport randomimport matplotlib.pyplot as plt
def generate_activities(n): activities = [] for i in range(n): start_time = random.randint(0, 100) end_time = start_time + random.randint(1, 10) activities.append((i+1, start_time, end_time)) return activities
def greedy_activity_selection(activities): activities.sort(key=lambda x: x[2]) # 按照结束时间排序 selected_activities = [activities[0]] for i in range(1, len(activities)): if activities[i][1] >= selected_activities[-1][2]: selected_activities.append(activities[i]) return selected_activities
def dynamic_programming_activity_selection(activities): activities.sort(key=lambda x: x[2]) # 按照结束时间排序 dp = [1] * len(activities) for i in range(1, len(activities)): for j in range(i): if activities[i][1] >= activities[j][2]: dp[i] = max(dp[i], dp[j] + 1) return max(dp)
def compare_execution_time(): n_values = [8, 16, 32, 64, 128, 256] 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) plt.plot(n_values, greedy_times, label='Greedy') plt.plot(n_values, dp_times, label='Dynamic Programming') plt.xlabel('Number of Activities') plt.ylabel('Execution Time (seconds)') plt.legend() plt.show()
compare_execution_time()
实验结果分析
运行上述代码,可以得到贪婪算法和动态规划算法的执行时间随活动数量n变化的曲线图。
根据实验结果,可以观察到:
- 贪婪算法的执行时间随着n的增加呈线性增长。* 动态规划算法的执行时间随着n的增加呈指数增长。
这是因为:
- 贪婪算法的时间复杂度为O(nlogn),其中排序的时间复杂度为O(nlogn),选择活动的时间复杂度为O(n)。* 动态规划算法的时间复杂度为O(n^2),因为需要计算n个子问题的最优解,每个子问题需要遍历之前的活动。
因此,贪婪算法在时间效率上优于动态规划算法。
结论
- 贪婪算法能够得到活动选择问题的近似解,但不一定是最优解。* 动态规划算法能够得到活动选择问题的最优解,但时间效率低于贪婪算法。
在实际应用中,需要根据具体情况选择合适的算法。如果对解的质量要求较高,可以选择动态规划算法;如果对时间效率要求较高,可以选择贪婪算法。
原文地址: https://www.cveoy.top/t/topic/fwl1 著作权归作者所有。请勿转载和采集!