贪心算法与动态规划在活动选择问题上的性能比较

import random import time import numpy as np import 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((start_time, end_time)) return activities

def greedy_activity_selection(activities): activities.sort(key=lambda x: x[1]) # 按结束时间排序 selected_activities = [] current_end_time = 0 for activity in activities: if activity[0] >= current_end_time: selected_activities.append(activity) current_end_time = activity[1] return selected_activities

def dynamic_programming_activity_selection(activities): n = len(activities) activities.sort(key=lambda x: x[1]) # 按结束时间排序 dp = [1] * n for i in range(1, n): for j in range(i): if activities[i][0] >= activities[j][1]: dp[i] = max(dp[i], dp[j] + 1) max_activities = max(dp) selected_activities = [] current_end_time = float('-inf') for i in range(n - 1, -1, -1): if dp[i] == max_activities and activities[i][1] >= current_end_time: selected_activities.append(activities[i]) current_end_time = activities[i][0] max_activities -= 1 return selected_activities[::-1]

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')
plt.legend()
plt.show()

compare_execution_time()

图像呈现折线而不是曲线是因为我们仅仅进行了单次实验，每个活动数量n值对应一个执行时间数据点。因此，图像由这些离散的数据点连接而成。若要得到平滑曲线，需要进行多次实验并取平均值，以获得每个n值对应的平均执行时间。