贪心算法的应用

2025年3月17日 | 阅读 15 分钟

贪心算法是一种解决优化问题的策略，它在每个阶段都做出局部最优决策，以期获得全局最优解。之所以称为“贪心”，是因为它假设算法在当前时刻选择看起来最理想的决策，而不考虑未来阶段可能产生的后果。贪心算法通常简单、直观且易于实现。

贪心算法的总体思想是，在每个阶段都选择最理想的选项，并期望所选的选项能导致一个理想的整体解决方案。

特性组件

贪心策略：一种在每个阶段选择最佳局部选择以获得全局最优解的策略，而无需重新评估决策。
选择标准：根据问题特征，使用特定的规则在每一步选择最佳选项。
可行性检查：验证所选选项是否满足问题的所有规定约束。
优化目标：明确定义算法旨在优化的目标。
迭代：重复应用贪心策略，直到找到解决方案或满足特定条件。
正确性证明：提供逻辑证据，证明算法始终能得出最优解。
最优解：实现期望极值（最小化或最大化目标函数）的可行解。
最优性检查：验证所选解是否在满足约束条件的同时，产生目标函数的最小或最大值。
最优子结构性质：全局最优解包含其内部的最优子解。

算法

根据物品的价值-重量比选择物品。
将背包的当前重量设为零，总价值设为零。
确保所选物品能够放入背包而不超出其容量。
最大化背包中物品的总价值。
选择能放入背包的、价值-重量比最高的物品。
将选定的物品添加到背包中。更新总价值和当前重量。
重复步骤 3-6，直到背包已满或没有更多物品。
验证获得的解是否在最大总价值方面是最优的。
当背包已满或没有更多物品时停止算法。

应用

1. 任务调度

任务调度是有效分配任务或作业给系统资源的进程，同时考虑各种限制和优化目标。在计算机和操作系统中，任务调度对于管理 CPU 上进程或线程的执行尤为重要。基本目标是利用系统资源，最小化整体执行时间，并优化特定的执行指标。

示例

1. 任务

假设我们有四个任务：A、B、C 和 D。

2. 执行时间

每个任务都有不同的执行时间，表示完成它所需的时间。

任务 A：五单位时间。
任务 B：两单位时间。
任务 C：八单位时间。
任务 D：四单位时间。

3. 调度步骤

FCFS（先来先服务）算法按任务到达或提交的顺序进行调度。让我们逐步了解调度步骤：

任务 A 最先到达，因此从时间零开始执行。
任务 A 完成后，任务 B 在时间 5 开始执行。
任务 B 完成后，任务 C 在时间 7 开始执行。
最后，任务 D 在任务 C 完成后的时间 15 开始执行。

4. 完成时间

每个任务的完成时间如下所示：

任务 A 在时间 5 完成。
任务 B 在时间 7 完成。
任务 C 在时间 15 完成。
任务 D 在时间 19 完成。

5. 最终调度

使用 FCFS 的完整工作调度如下：

任务	完成时间
A	5
B	7
C	15
D	19

6. 观察

FCFS 算法按任务到达的顺序执行它们，而不管它们的执行时间。这可能会导致不同作业的完成时间不同。

7. 考虑

虽然 FCFS 很简单，但可能存在更好的调度方案。对于某些情况，其他调度策略，例如“最短作业优先”（SJN）或“优先级调度”，可能更合适。

实施

#include <stdio.h>
struct Task {
    char name;       
    int executionTime;  
};
void scheduleTasks(struct Task tasks[], int n) {
    int completionTime = 0;  
    printf("Task Schedule:\n");
    printf("Task\tCompletion Time\n");
    for (int i = 0; i < n; i++) {
        printf("%c\t%d\n", tasks[i].name, completionTime);
        completionTime += tasks[i].executionTime;
    }
}
int main() {
    struct Task tasks[] = {
        {'A', 5},
        {'B', 2},
        {'C', 8},
        {'D', 4}
    };
    int numTasks = sizeof(tasks) / sizeof(tasks[0]);
    scheduleTasks(tasks, numTasks);
    return 0;
}

输出

说明

我们定义一个 Task 结构来表示每个任务，包括任务标识符（名称）和其执行时间（executionTime）。
scheduleTasks 函数通过按接收顺序遍历任务来执行 FCFS 调度，并打印每个任务的完成时间。
在 main 函数中，我们创建一个任务数组并调用 scheduleTasks 函数。

2. 哈夫曼编码用于数据压缩

哈夫曼编码是一种著名的无损数据压缩方法，旨在减小文件大小但保留所有信息。它以 David A. Huffman 的名字命名，他于 1952 年发明了该方法。哈夫曼编码的基本原理是根据信息数据中出现的频率，为不同的符号（字符或字符组）分配可变长度的代码。更频繁出现的符号被授予较短的代码，而不太频繁出现的符号被授予较长的代码。

示例

考虑以下输入数据：“ABRACADABRA”。

1. 频率分析

频率：A(5)、B(2)、R(2)、C(1)、D(1)。

2. 构建哈夫曼树

根据频率创建哈夫曼树。

          [11]
     /              \
    [5]                [6]
  /     \          /           \
 A(5) B(2) R(2)     C(1) D(1)

3. 分配代码

要分配代码，请遍历树：A(0)、B(10)、R(11)、C(100)、D(101)。

4. 创建哈夫曼表

哈夫曼表：A=0、B=10、R=11、C=100、D=101。

5. 编码

原始数据“ABRACADABRA”被编码为“0101110100111110100”。

6. 解码

编码后的数据被解码回原始数据：“ABRACADABRA”。

哈夫曼编码通过使用较短的代码来压缩更常见的符号，从而生成可变长度的前缀码。它确保最常用的符号得到更有效的表示，从而实现总体数据减少。

实施

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct Node {
    char data;
    unsigned frequency;
    struct Node *left, *right;
};
struct MinHeap {
    unsigned size;
    unsigned capacity;
    struct Node** array;
};
struct Node* newNode(char data, unsigned frequency) {
    struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
    temp->left = temp->right = NULL;
    temp->data = data;
    temp->frequency = frequency;
    return temp;
}
struct MinHeap* createMinHeap(unsigned capacity) {
    struct MinHeap* minHeap = (struct MinHeap*)malloc(sizeof(struct MinHeap));
    minHeap->size = 0;
    minHeap->capacity = capacity;
    minHeap->array = (struct Node**)malloc(capacity * sizeof(struct Node*));
    return minHeap;
}
void swapNode(struct Node** a, struct Node** b) {
    struct Node* t = *a;
    *a = *b;
    *b = t;
}
void minHeapify(struct MinHeap* minHeap, int idx) {
    int smallest = idx;
    int left = 2 * idx + 1;
    int right = 2 * idx + 2;
    if (left < minHeap->size && minHeap->array[left]->frequency < minHeap->array[smallest]->frequency)
        smallest = left;
    if (right < minHeap->size && minHeap->array[right]->frequency < minHeap->array[smallest]->frequency)
        smallest = right;
    if (smallest != idx) {
        swapNode(&minHeap->array[smallest], &minHeap->array[idx]);
        minHeapify(minHeap, smallest);
    }
}
int isSizeOne(struct MinHeap* minHeap) {
    return (minHeap->size == 1);
}
struct Node* extractMin(struct MinHeap* minHeap) {
    struct Node* temp = minHeap->array[0];
    minHeap->array[0] = minHeap->array[minHeap->size - 1];
    --minHeap->size;
    minHeapify(minHeap, 0);
    return temp;
}
void insertMinHeap(struct MinHeap* minHeap, struct Node* node) {
    ++minHeap->size;
    int i = minHeap->size - 1;
    while (i && node->frequency < minHeap->array[(i - 1) / 2]->frequency) {
        minHeap->array[i] = minHeap->array[(i - 1) / 2];
        i = (i - 1) / 2;
    }
    minHeap->array[i] = node;
}
struct Node* buildHuffmanTree(char data[], unsigned frequency[], int size) {
    struct Node *left, *right, *top;
    struct MinHeap* minHeap = createMinHeap(size);
    for (int i = 0; i < size; ++i)
        insertMinHeap(minHeap, newNode(data[i], frequency[i]));
    while (!isSizeOne(minHeap)) {
        left = extractMin(minHeap);
        right = extractMin(minHeap);
        top = newNode('$', left->frequency + right->frequency);
        top->left = left;
        top->right = right;
        insertMinHeap(minHeap, top);
    }
    return extractMin(minHeap);
}
void printCodes(struct Node* root, int arr[], int top) {
    if (root->left) {
        arr[top] = 0;
        printCodes(root->left, arr, top + 1);
    }
    if (root->right) {
        arr[top] = 1;
        printCodes(root->right, arr, top + 1);
    }
    if (!(root->left) && !(root->right)) {
        printf("%c: ", root->data);
        for (int i = 0; i < top; ++i)
            printf("%d", arr[i]);
        printf("\n");
    }
}
void HuffmanCodes(char data[], unsigned frequency[], int size) {
    struct Node* root = buildHuffmanTree(data, frequency, size);
    int arr[100], top = 0;
    printCodes(root, arr, top);
}
int main() {
    char data[] = {'a', 'b', 'c', 'd', 'e', 'f'};
    unsigned frequency[] = {5, 9, 12, 13, 16, 45};
    int size = sizeof(data) / sizeof(data[0]);
    printf("Huffman Codes:\n");
    HuffmanCodes(data, frequency, size);
    return 0;
}

输出

说明

1. 节点结构

我们定义一个名为 Node 的结构来表示字符及其频率。每个节点都有一个字符（data）、一个频率以及指向左右子节点的指针。

2. 新节点函数

有一个名为 newNode 的函数，它使用给定的字符和频率创建一个新节点。

3. 主要哈夫曼编码函数

HuffmanCodes 函数是哈夫曼编码的主函数。
它初始化示例数据和频率（字符及其出现次数）。

4. 创建哈夫曼树

buildHuffmanTree 函数（此处未显示）根据提供的字符和频率构建哈夫曼树。

5. 打印哈夫曼码

然后程序使用 printCodes 函数（此处未显示）打印每个字符的哈夫曼码。

6. 主函数

在 main 函数中，我们使用示例数据和频率调用 HuffmanCodes 函数。

3. 最小生成树 (MST)

最小生成树 (MST) 是网络设计中的一个关键概念，尤其是在图论中。它指的是连接连通的无向图中的所有节点的最小树，同时最小化整体边权重。MST 被广泛用于各种目的，包括开发高效的网络架构、确保连通性和降低成本。

工作原理

边权重

图中的每条边都有一个相关的权重或成本。目标是找到一条连接所有节点且总边权重最小的树。

连接性

MST 必须保持连通性，这意味着可以从树中的任何其他节点访问所有节点。

示例

考虑一种情况，其中有多个城市通过高速公路连接，每条高速公路都有特定的成本。目标是以最低的总成本创建一个连接所有城市的网络。

让我们将城市描绘成节点，将高速公路描绘成边，并附带它们的相应成本。

城市（节点）：A、B、C 和 D

道路（边）：A-B（成本：3）。

B-C（成本：2）

C-D（成本：1）。

D-A（成本：4）

A-C（成本：5）

图的表示

       3
   A ------- B
   | \       |
   |  \      |
   |   \     |
   |    \    |
   |     \   |
   5      2  |
   |       \ |
   |        \|
   D ------- C
       1

MST 解决方案

此网络上的最小生成树是：

       3
   A ------- B
   |         |
   |         |
   |         |
   |         |
   |         |
   5         2
   |         |
   |         |
   D ------- C
       1

在此示例中，MST 以最低的可行总成本（边权重的总和）连接了所有城市（节点）。MST 作为一棵树，不会产生任何环，并提供了城市之间最高效且经济的通信。

实施

#include <stdio.h>
#include <stdlib.h>
struct Edge {
    int src, dest, weight;
};
struct Subset {
    int parent;
    int rank;
};
int find(struct Subset subsets[], int i) {
    if (subsets[i].parent != i)
        subsets[i].parent = find(subsets, subsets[i].parent);
    return subsets[i].parent;
}
void Union(struct Subset subsets[], int x, int y) {
    int xroot = find(subsets, x);
    int yroot = find(subsets, y);
    if (subsets[xroot].rank < subsets[yroot].rank)
        subsets[xroot].parent = yroot;
    else if (subsets[xroot].rank > subsets[yroot].rank)
        subsets[yroot].parent = xroot;
    else {
        subsets[yroot].parent = xroot;
        subsets[xroot].rank++;
    }
}
int compareEdges(const void* a, const void* b) {
    return ((struct Edge*)a)->weight - ((struct Edge*)b)->weight;
}
void KruskalMST(struct Edge edges[], int V, int E) {
    struct Edge result[V - 1]; 
    int e = 0; 
    int i = 0; 
    qsort(edges, E, sizeof(edges[0]), compareEdges);
    struct Subset* subsets = (struct Subset*)malloc(V * sizeof(struct Subset));
    for (int v = 0; v < V; ++v) {
        subsets[v].parent = v;
        subsets[v].rank = 0;
    }
    while (e < V - 1 && i < E) {
        struct Edge next_edge = edges[i++];
        int x = find(subsets, next_edge.src);
        int y = find(subsets, next_edge.dest);
        if (x != y) {
            result[e++] = next_edge;
            Union(subsets, x, y);
        }
        // Else discard the next_edge
    }
    printf("Edges in the Minimum Spanning Tree:\n");
    for (int j = 0; j < e; ++j)
        printf("%d - %d : %d\n", result[j].src, result[j].dest, result[j].weight);
    free(subsets);
}
int main() {
    int V = 4, E = 5;
    struct Edge edges[] = {
        {0, 1, 3},
        {1, 2, 2},
        {2, 3, 1},
        {3, 0, 4},
        {0, 2, 5}
    };
    KruskalMST(edges, V, E);
    return 0;
}

输出

说明

struct Edge：表示图中的一条边，包含源（src）、目标（dest）和权重。
struct Subset：为并查集数据结构表示一个子集。
find 和 Union：用于查找顶点集的函数，以及使用并查集算法执行两个子集的合并。
compareEdges：qsort 用于根据边权重对边进行排序的比较器函数。
KruskalMST：实现 Kruskal 算法查找最小生成树的主函数。
main：示例用法，包含一个具有 4 个顶点和 5 条边的图。程序查找并打印最小生成树的边。

4. 背包问题

背包问题是计算机科学和数学中的一个标准优化问题。其正式定义如下：

给定一组物品，每个物品都有重量和价值，以及一个具有最大重量容量的背包，目标是找到要放入背包的最佳物品组合，使得总价值最大化。但是，总重量不超过背包的容量。

背包问题有多种变体，但其中一个显著的区别是 0/1 背包问题和分数背包问题。

0/1 背包问题：在此版本中，一个物品只能包含在背包中或排除在外。因此，您不能取其一部分。决策是二元的：要么包含整个物品，要么不包含。

分数背包问题：在此变体中，一个物品可以被分成几部分。它允许更灵活的方法，您可以在其中取物品的一部分，如果这有助于最大化整体价值。

示例

问题陈述：您的背包的重量容量为 10 个单位。您有以下物品，每个物品都有其重量和价值：

Item	Weight	Value
A	    2        6
B	    3        5
C	    5        8
D	    7        9

目标是找到一个物品组合放入背包，使其总价值最大化，同时保持总重量低于 10 个单位。

解决方案

让我们利用动态规划策略来解决这个问题。

1. 创建一个二维数组 dp[n+1][capacity+1]，其中 n 是物品数量，capacity 是背包容量。

2. 使用以下递推关系填充数组：

这里，dp[i][w] 表示使用前 i 个物品和背包容量为 w 时可能获得的最大价值。

3. 结果保存在 dp[n][capacity] 中。

实施

#include <stdio.h>
int max(int a, int b) {
    return (a > b) ? a : b;
}
int knapsack(int capacity, int weights[], int values[], int n) {
    int i, w;
    int dp[n + 1][capacity + 1];
    for (i = 0; i <= n; i++) {
        for (w = 0; w <= capacity; w++) {
            if (i == 0 || w == 0)
                dp[i][w] = 0;
            else if (weights[i - 1] <= w)
                dp[i][w] = max(values[i - 1] + dp[i - 1][w - weights[i - 1]], dp[i - 1][w]);
            else
                dp[i][w] = dp[i - 1][w];
        }
    }
    return dp[n][capacity];
}
int main() {
    int capacity = 10;
    int weights[] = {2, 3, 5, 7};
    int values[] = {6, 5, 8, 9};
    int n = sizeof(values) / sizeof(values[0]);
    int maxValue = knapsack(capacity, weights, values, n);
    printf("Maximum value in the knapsack: %d\n", maxValue);
    return 0;
}

输出

说明

max 函数是一个实用函数，用于查找两个数字中的最大值。
knapsack 函数：0/1 背包问题的动态规划解决方案。它创建一个二维数组 dp[][] 来保存每个子问题的可能最大价值。
main 函数：这是一个示例，用于背包容量为 10 个单位和 4 件物品。它计算并打印在给定限制内可以获得的最大价值。

5. 活动选择问题

活动选择问题是一个经典的算法问题，涉及从活动列表中选择最多的不重叠活动，每个活动都有开始和结束时间。目标是确定由单个人或资源可以完成的最大活动数量，前提是同一时间只能执行一项活动。

示例

考虑以下活动集：

Activity    Start Time    Finish Time
   A          1            4
   B          3            5
   C          0            6
   D          5            7
   E          8            9
   F          5            9

解决方案：最多的不重叠活动是 [C, A, D, E]。

说明

活动 C 是最早完成的活动，于时间 6 结束。
活动 A 在 C 完成后开始，于时间 4 结束。
活动 D 在 A 完成后开始，于时间 7 结束。
活动 E 在 D 完成后开始，于时间 9 结束。

因此，C、A、D、E 可以选择而不重叠，从而产生最多的活动。

实施

#include <stdio.h>
struct Activity {
    int start;
    int finish;
};
int compareActivities(const void* a, const void* b) {
    return ((struct Activity*)a)->finish - ((struct Activity*)b)->finish;
}
void printMaxActivities(struct Activity activities[], int n) {
    qsort(activities, n, sizeof(activities[0]), compareActivities);
    printf("Selected Activities:\n");
    int i = 0;
    printf("Activity %d: Start Time = %d, Finish Time = %d\n", i + 1, activities[i].start, activities[i].finish);
    for (int j = 1; j < n; j++) {
        if (activities[j].start >= activities[i].finish) {
            printf("Activity %d: Start Time = %d, Finish Time = %d\n", j + 1, activities[j].start, activities[j].finish);
            i = j;
        }
    }
}
int main() {
    struct Activity activities[] = {
        {1, 4},
        {3, 5},
        {0, 6},
        {5, 7},
        {8, 9},
        {5, 9}
    };
    int n = sizeof(activities) / sizeof(activities[0]);
    printMaxActivities(activities, n);
    return 0;
}

输出

说明

struct Activity：表示一个具有开始和结束时间的活动。
compareActivities：qsort 用于根据活动结束时间对活动进行排序的比较器函数。
printMaxActivities：使用贪心方法查找并打印最多不重叠活动数量的函数。
main：具有一组活动的示例用法。程序打印所选活动及其开始和结束时间。

局限性

不回溯：贪心算法在每一步都做出局部最优决策，而不考虑全局上下文。一旦做出决策，就不能撤销或撤回。这种不回溯的特性可能导致次优解。
不能保证贪心算法在所有问题实例中都能找到全局最优解。在每个阶段做出的局部最优决策可能无法导致最佳的整体解决方案。
不考虑未来影响：贪心算法优先考虑即时收益，而忽略其决策的长期后果。这种狭隘的视角可能导致在更大范围内次优的解决方案。
问题依赖性：贪心算法的有效性取决于所解决问题的独特特征。如果一个问题缺乏贪心选择性质或最优子结构，贪心方法可能无法产生最优结果。
贪心算法不适合解决 NP 难题，在这些难题中，找到最优解在计算上是不可行的。贪心算法可能产生近似答案，但并不总是最优答案。
当问题同时具有贪心选择性质和最优子结构时，贪心算法最有效。缺乏这些特征的问题可能不适合贪心方法。

优点

简单性：贪心算法通常易于理解和实现。简单的逻辑和缺乏复杂的数据结构使其即使对于没有扎实算法知识的人来说也易于使用。
效率：贪心算法通常在时间上非常高效。简单性通常会产生具有线性或近线性时间复杂度的算法，使其适用于大型数据集。
贪心算法广泛用于设计近似算法。虽然它们不能总是保证完美答案，但它们可以在合理的时间内提供接近最优的解决方案。
贪心算法在各种实际场景中都有应用，例如网络设计、任务调度和资源分配。它们的简单性和有效性使其成为解决实际问题的理想选择。
在某些情况下的最优性：在满足贪心选择性质和最优子结构的情况下，贪心算法可以产生最优解。每个阶段的局部最优选择会得到全局最优解。
内存效率：贪心算法通常需要更少的内存，因为它们在每个阶段处理少量信息。这使其成为内存资源受限的应用的理想选择。
快速执行：由于贪心算法高效，因此可以快速执行，尤其是在处理大型数据集时。这使其适用于实时或资源受限的应用。

下一主题数组的应用、优点和缺点

贪心算法的应用

2. 哈夫曼编码用于数据压缩

3. 最小生成树 (MST)

4. 背包问题

5. 活动选择问题

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

数据结构教程

DS 数组

DS 链表

DS 栈

DS 队列

DS 树

DS 图

DS 搜索

DS 排序

哈希与堆

差异

二叉树

二叉搜索树

AVL 树

单向链表

双向链表

循环链表

循环双向链表

DS 选择题

其他

贪心算法的应用

2. 哈夫曼编码用于数据压缩

3. 最小生成树 (MST)

4. 背包问题

5. 活动选择问题

相关帖子

链表应用、优点和缺点

插值查找

找到最大的三的倍数

Tarjan 算法用于查找强连通分量

二叉树的底视图

Recaman 序列

程序以揭示扫雷中的位置

复杂数据结构

AVL 树操作

数据结构中的结构体

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器