贪心算法与动态规划求解活动选择问题：性能比较与分析

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

随机生成n个任务（n=8,16,32…）,用贪心法求近似解，任选一种其它方法求最优解。做出图像，比较贪心法和你所选的另外一种方法的执行时间随n的变化曲线。比较计算结果，说明对该问题，贪心法是否一定会得到最优解，请根据实验结果说明理由。

贪心算法

贪心法的思路是每次选择结束时间最早的活动，然后将与该活动相容的活动从集合中移除，直到所有活动都被选择完毕。

下面给出贪心法的实现代码：

def greedy_activity_selection(s, f):
    n = len(s)
    activities = list(range(n))
    selected_activities = []
    while activities:
        earliest_finish = min(f[i] for i in activities)
        selected = [i for i in activities if f[i] == earliest_finish][0]
        selected_activities.append(selected)
        activities = [i for i in activities if s[i] >= f[selected]]
    return selected_activities

动态规划

对于最优解的求解，可以使用动态规划的方法。定义一个二维数组dp，其中dp[i][j]表示从第i个活动到第j个活动的最优解。则有以下递推关系：

dp[i][j] = max(dp[i][k] + dp[k][j])，其中i < k < j
dp[i][j] = 0，如果活动i和活动j不相容

下面给出最优解的实现代码：

def optimal_activity_selection(s, f):
    n = len(s)
    dp = [[0] * (n+1) for _ in range(n+1)]
    for length in range(2, n+1):
        for i in range(n-length+1):
            j = i + length
            for k in range(i+1, j):
                if s[k] >= f[i] and f[k] <= s[j-1]:
                    dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + 1)
    return dp[0][n]

性能比较

下面是比较贪心法和最优解方法的执行时间随n的变化曲线的代码：

import time
import matplotlib.pyplot as plt

def compare_execution_time():
    n_values = [8, 16, 32, 64, 128]
    greedy_times = []
    optimal_times = []
    for n in n_values:
        s = [i for i in range(n)]
        f = [i+1 for i in range(n)]
        start_time = time.time()
        greedy_activity_selection(s, f)
        greedy_times.append(time.time() - start_time)
        
        start_time = time.time()
        optimal_activity_selection(s, f)
        optimal_times.append(time.time() - start_time)
    
    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()

根据实验结果，可以观察到贪心法的执行时间随着活动数量的增加而线性增长，而最优解方法的执行时间随着活动数量的增加而呈指数增长。这说明贪心法的时间复杂度较低，但不能保证得到最优解。

结论

对于该问题，贪心法不一定会得到最优解的原因是贪心选择策略只考虑了当前最优解，而没有考虑全局最优解。在某些情况下，贪心选择策略可能会导致后续无法找到更优的解。而动态规划方法通过穷举所有可能的解并进行比较，可以保证得到最优解，但时间复杂度较高。