Python实现贪心算法与动态规划解决活动选择问题及性能比较
import random
import time
import numpy as np
import matplotlib.pyplot as plt
def generate_activities(n): # 生成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]) # 按结束时间排序确保每次选择的活动都是结束时间最早的活动。使用lambda表达式指定排序的依据。
selected_activities = []
current_end_time = 0
for activity in activities:
if activity[0] >= current_end_time:
selected_activities.append(activity) # 如果活动的起始时间大于等于当前活动的结束时间，则添加到selected_activities中
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 # 初始化dp数组，用于记录每个活动的最大兼容子集大小
for i in range(1, n):
for j in range(i): #两层循环遍历活动列表
if activities[i][0] >= activities[j][1]: # 如果活动i的起始时间大于等于活动j的结束时间，则活动i可以加入活动j的最大兼容子集
dp[i] = max(dp[i], dp[j] + 1) #更新dp[i]为dp[j]+1和dp[i]中大的一个
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]) # 如果活动i的最大兼容子集大小等于最大兼容子集的大小，
#并且活动i的结束时间大于等于当前活动的结束时间，则选中该活动
current_end_time = activities[i][0] # 更新当前活动的结束时间为该活动的起始时间
max_activities -= 1 # 最大兼容子集的大小减1
return selected_activities[::-1] # 返回选中的活动列表，按照起始时间升序排序
def compare_execution_time():
n_values = [8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096] # 不同活动数量的取值
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)
print(greedy_times)
print(dp_times)
smooth_N = np.linspace(min(n_values), max(n_values), 100) # 生成平滑的活动数量序列
curve_brute_force = np.polyfit(n_values, greedy_times, 3) # 对贪心算法的执行时间进行拟合
curve_backtrack = np.polyfit(n_values, dp_times, 3) # 对动态规划的执行时间进行拟合
smooth_times_backtrack = np.polyval(curve_brute_force, smooth_N)# 根据拟合曲线计算平滑的执行时间
smooth_times_branch_bound = np.polyval(curve_backtrack, smooth_N)
plt.plot(smooth_N, smooth_times_branch_bound, label='Dynamic Programming')
plt.plot(smooth_N, smooth_times_backtrack, label='Greedy')
plt.xlabel('Number of activities')
plt.ylabel('Execution time')
plt.legend()
plt.show()
compare_execution_time()
# **代码解释**
这段代码使用 Python 实现了贪心算法和动态规划算法来解决活动选择问题，并比较了它们的执行时间。
**1. 活动选择问题**
活动选择问题是指在一个给定的活动集合中，选择最大的互相兼容的活动子集。每个活动都有一个起始时间和结束时间，两个活动是兼容的，当且仅当它们的举行时间段不重叠。
**2. 贪心算法**
贪心算法的思路是：
- 将所有活动按照结束时间从小到大排序。
- 选择结束时间最早的活动，并将该活动加入到结果集中。
- 从剩余的活动中选择与已选活动兼容的活动，直到没有活动可以再选为止。
贪心算法的时间复杂度为 O(nlogn)，其中 n 是活动的个数。
**3. 动态规划算法**
动态规划算法的思路是：
- 创建一个 dp 数组，其中 dp[i] 表示以第 i 个活动为结尾的最大兼容子集的大小。
- 对于每个活动 i，遍历所有在它之前的活动 j，如果活动 i 和活动 j 兼容，则更新 dp[i] = max(dp[i], dp[j] + 1)。
- 最后，dp 数组中的最大值即为最大兼容子集的大小。
动态规划算法的时间复杂度为 O(n^2)，其中 n 是活动的个数。
**4. 性能比较**
从理论上讲，贪心算法的时间复杂度低于动态规划算法。但在实际应用中，贪心算法不一定总是能得到最优解，而动态规划算法可以保证得到最优解。
**5. 代码分析**
- `generate_activities(n)` 函数用于生成 n 个活动的起始时间和结束时间。
- `greedy_activity_selection(activities)` 函数实现了贪心算法。
- `dynamic_programming_activity_selection(activities)` 函数实现了动态规划算法。
- `compare_execution_time()` 函数用于比较两种算法在不同活动数量下的执行时间，并绘制执行时间曲线。
**6. 结果分析**
从执行时间曲线可以看出，随着活动数量的增加，贪心算法的执行时间增长速度明显慢于动态规划算法。
原文地址: https://www.cveoy.top/t/topic/fz8q 著作权归作者所有。请勿转载和采集!