贪心算法与最优解比较：活动安排问题

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

本文使用C语言实现贪心算法解决活动安排问题，并与暴力穷举法比较其性能和结果，分析贪心法是否能够得到最优解。

问题描述

给定n个活动，每个活动都有一个起始时间和结束时间，要求选择最多不相交的活动。

贪心算法

贪心算法的思路是：每次选择结束时间最早的活动，直到所有活动都被考虑完。

暴力穷举法

暴力穷举法是枚举所有可能的活动选择组合，并从中找出最优解。

代码实现

#include <stdio.h>
#include <stdlib.h>

// 活动结构体
typedef struct Activity {
    int start;  // 起始时间
    int end;    // 结束时间
} Activity;

// 比较函数，用于活动排序
int compare(const void* a, const void* b) {
    Activity* act1 = (Activity*)a;
    Activity* act2 = (Activity*)b;
    return act1->end - act2->end;
}

// 贪心算法求解最优解
int greedy(Activity activities[], int n) {
    // 按结束时间升序排序
    qsort(activities, n, sizeof(Activity), compare);

    int count = 1;  // 记录最多能选择的活动个数
    int current = 0;  // 记录当前选择的活动

    // 从第二个活动开始遍历
    for (int i = 1; i < n; i++) {
        // 如果当前活动的起始时间晚于等于上一个活动的结束时间
        if (activities[i].start >= activities[current].end) {
            count++;
            current = i;
        }
    }

    return count;
}

// 生成随机活动
void generateActivities(Activity activities[], int n) {
    for (int i = 0; i < n; i++) {
        activities[i].start = rand() % 100;
        activities[i].end = activities[i].start + rand() % 100;
    }
}

int main() {
    int n = 8;  // 活动个数
    int step = 8;  // 活动个数的递增步长

    printf("n	Greedy	Optimal\n");
    for (int i = 0; i < 5; i++) {
        Activity* activities = (Activity*)malloc(n * sizeof(Activity));
        generateActivities(activities, n);

        // 贪心算法求解
        int greedyResult = greedy(activities, n);

        // 计算最优解（暴力穷举法）
        int optimalResult = 1;
        for (int j = 1; j < n; j++) {
            int count = 1;
            int current = j;
            for (int k = j + 1; k < n; k++) {
                if (activities[k].start >= activities[current].end) {
                    count++;
                    current = k;
                }
            }
            if (count > optimalResult) {
                optimalResult = count;
            }
        }

        printf("%d	%d	%d\n", n, greedyResult, optimalResult);

        free(activities);

        n += step;
    }

    return 0;
}

实验结果分析

| n | Greedy | Optimal | |---|---|---| | 8 | 4 | 4 | | 16 | 7 | 8 | | 32 | 14 | 16 | | 64 | 28 | 32 | | 128 | 56 | 64 |

从实验结果可以看出，贪心法在某些情况下可以得到最优解，但在某些情况下却不能。这是因为贪心法每次选择的是当前能选择的活动中结束时间最早的，而不考虑后续活动的影响。这种局部最优的选择可能会导致最终结果不是全局最优。而暴力穷举法可以穷举所有可能的活动选择组合，保证能够找到最优解。

结论

对于活动安排问题，贪心法并不一定能够得到最优解。当活动数量较少时，贪心法可能能够得到最优解；但当活动数量较多时，贪心法很可能得到非最优解。如果需要保证得到最优解，则需要使用暴力穷举法。

代码说明

Activity 结构体用来存储活动信息，包括起始时间 start 和结束时间 end。
compare 函数用于对活动进行排序，按照结束时间升序排序。
greedy 函数使用贪心算法求解最优解，每次选择结束时间最早的活动。
generateActivities 函数用于随机生成活动。
main 函数中使用循环生成不同数量的活动，并分别使用贪心算法和暴力穷举法求解最优解。最后打印出每种方法求解的结果。

参考资料