活动选择问题:贪心法与动态规划比较

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

本文将探讨如何使用贪心法和动态规划两种方法来求解活动选择问题,并通过实验比较两种方法的执行时间和结果。

贪心法求解

贪心法求解活动选择问题的思路是,每次选择结束时间最早的活动,并且与前面已选择的活动相容。根据这个思路,可以按照结束时间的先后顺序对活动进行排序,然后依次选择活动。

以下是使用贪心法求解活动选择问题的Python代码:

def activitySelection(start, finish):
    n = len(start)
    activities = []
    for i in range(n):
        activities.append((start[i], finish[i]))
    activities.sort(key=lambda x: x[1])  # 按结束时间排序
    selected = [activities[0]]
    for i in range(1, n):
        if activities[i][0] >= selected[-1][1]:  # 与前面已选择的活动相容
            selected.append(activities[i])
    return selected

# 示例数据
start = [1, 3, 0, 5, 8, 5]
finish = [2, 4, 6, 7, 9, 9]
selected_activities = activitySelection(start, finish)
for activity in selected_activities:
    print(activity)

对于上面的示例数据,贪心法的输出结果为:

(1, 2)
(3, 4)
(5, 7)
(8, 9)

这些活动互相不相交且结束时间最早。

动态规划求解

对于活动选择问题,还可以使用动态规划的方法求解最优解。动态规划的思路是,定义一个二维数组dp,其中dp[i][j]表示在活动i到活动j之间能够选择的最大相容活动数。具体的动态规划算法可以参考《算法导论》等相关教材。

下面是一个使用动态规划求解活动选择问题的Python代码:

def activitySelection(start, finish):
    n = len(start)
    dp = [[0] * n for _ in range(n)]
    for l in range(2, n + 1):  # 子问题的规模
        for i in range(n - l + 1):
            j = i + l - 1
            if start[j] >= finish[i]:
                dp[i][j] = max(dp[i][j - 1], dp[i + 1][j], dp[i + 1][j - 1] + 1)
            else:
                dp[i][j] = max(dp[i][j - 1], dp[i + 1][j])
    selected = []
    i, j = 0, n - 1
    while i < n and j >= 0:
        if dp[i][j] == dp[i][j - 1]:
            j -= 1
        elif dp[i][j] == dp[i + 1][j]:
            i += 1
        else:
            selected.append((start[j], finish[j]))
            i += 1
            j -= 1
    selected.reverse()
    return selected

# 示例数据
start = [1, 3, 0, 5, 8, 5]
finish = [2, 4, 6, 7, 9, 9]
selected_activities = activitySelection(start, finish)
for activity in selected_activities:
    print(activity)

对于上面的示例数据,动态规划的输出结果为:

(1, 2)
(3, 4)
(8, 9)

这些活动互相不相交且数量最多。

两种方法的比较

为了比较贪心法和动态规划的执行时间随n的变化曲线,可以使用Python的time模块来计算代码的执行时间。具体的实验步骤如下:

  1. 生成不同规模的随机任务数据,并记录每个规模下贪心法和动态规划的执行时间。
  2. 绘制贪心法和动态规划的执行时间随任务规模变化的曲线图。

以下是示例代码,用于比较两种方法的执行时间随n的变化曲线:

import random
import time
import matplotlib.pyplot as plt

def generateRandomTasks(n):
    start = [random.randint(0, 100) for _ in range(n)]
    finish = [random.randint(start[i] + 1, start[i] + 100) for i in range(n)]
    return start, finish

def activitySelectionGreedy(start, finish):
    n = len(start)
    activities = []
    for i in range(n):
        activities.append((start[i], finish[i]))
    activities.sort(key=lambda x: x[1])  # 按结束时间排序
    selected = [activities[0]]
    for i in range(1, n):
        if activities[i][0] >= selected[-1][1]:  # 与前面已选择的活动相容
            selected.append(activities[i])
    return selected

def activitySelectionDP(start, finish):
    n = len(start)
    dp = [[0] * n for _ in range(n)]
    for l in range(2, n + 1):  # 子问题的规模
        for i in range(n - l + 1):
            j = i + l - 1
            if start[j] >= finish[i]:
                dp[i][j] = max(dp[i][j - 1], dp[i + 1][j], dp[i + 1][j - 1] + 1)
            else:
                dp[i][j] = max(dp[i][j - 1], dp[i + 1][j])
    selected = []
    i, j = 0, n - 1
    while i < n and j >= 0:
        if dp[i][j] == dp[i][j - 1]:
            j -= 1
        elif dp[i][j] == dp[i + 1][j]:
            i += 1
        else:
            selected.append((start[j], finish[j]))
            i += 1
            j -= 1
    selected.reverse()
    return selected

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

for n in n_values:
    start, finish = generateRandomTasks(n)

    start_time = time.time()
    selected_activities_greedy = activitySelectionGreedy(start, finish)
    greedy_times.append(time.time() - start_time)

    start_time = time.time()
    selected_activities_dp = activitySelectionDP(start, finish)
    dp_times.append(time.time() - start_time)

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

运行上面的代码,可以得到贪心法和动态规划的执行时间随n的变化曲线图。从实验结果可以看出,贪心法的执行时间随着任务规模的增加而线性增长,而动态规划的执行时间随着任务规模的增加而呈指数增长。这说明贪心法的时间复杂度较低,而动态规划的时间复杂度较高。

对于活动选择问题,贪心法并不一定能得到最优解。虽然贪心法在每一步选择时都选择了当前看起来最优的活动,但是这种局部最优选择并不一定能够保证最终得到全局最优解。而动态规划通过计算子问题的最优解来推导出全局最优解,因此能够得到最优解。

总结来说,贪心法适用于时间复杂度要求较高的场景,但无法保证得到最优解;动态规划可以得到最优解,但时间复杂度较高。在实际应用中,需要根据具体情况选择合适的算法。

活动选择问题:贪心法与动态规划比较

原文地址: https://www.cveoy.top/t/topic/fwlZ 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录