贪心法求解活动选择问题的近似解及与动态规划法比较

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

问题描述

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

贪心法求解近似解

贪心法的思路是：

将所有活动按照结束时间从早到晚排序。2. 选择第一个活动作为当前活动。3. 对于剩下的活动，如果活动的起始时间晚于或等于当前活动的结束时间，则选择该活动作为当前活动，并继续执行步骤3。4. 如果活动的起始时间早于当前活动的结束时间，则将该活动舍弃。5. 重复步骤3和步骤4，直到所有活动都被遍历完毕。

贪心策略的正确性可以通过反证法证明，其能够找到一个近似解，但不一定是最优解。

动态规划求解最优解

动态规划算法可以通过构建一个二维表格来记录子问题的最优解，最终得到全局最优解。

实验比较

为了比较贪心法和动态规划法的性能，我们随机生成不同规模的活动集合 (n=8, 16, 32, 64, 128)，分别使用两种算法求解，并记录执行时间。pythonimport randomimport time

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, start_time, end_time)) return activities

def dynamic_programming(activities): activities.sort(key=lambda x: x[2]) dp = [0] * len(activities) dp[0] = 1 for i in range(1, len(activities)): max_val = 0 for j in range(i): if activities[i][1] >= activities[j][2]: max_val = max(max_val, dp[j]) dp[i] = max_val + 1 return max(dp)

def greedy_algorithm(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 len(selected_activities)

n_values = [8, 16, 32, 64, 128]dp_times = []greedy_times = []

for n in n_values: activities = generate_activities(n) start_time = time.time() dynamic_programming(activities) dp_times.append(time.time() - start_time) start_time = time.time() greedy_algorithm(activities) greedy_times.append(time.time() - start_time)

import matplotlib.pyplot as plt

plt.plot(n_values, dp_times, label='Dynamic Programming')plt.plot(n_values, greedy_times, label='Greedy Algorithm')plt.xlabel('Number of activities')plt.ylabel('Execution Time (seconds)')plt.legend()plt.show()

结果分析

实验结果表明，贪心法的执行时间随问题规模的增加呈线性增长，而动态规划算法的执行时间呈指数增长。这说明贪心法的时间复杂度较低，但不能保证得到最优解。

结论

对于活动选择问题，贪心法可以快速得到一个近似解，但并不一定是最优解。如果需要得到精确解，可以使用动态规划算法，但其时间复杂度较高。在实际应用中，需要根据具体情况选择合适的算法。