算法笔记之贪心算法

贪婪策略

贪心算法（Greedy Algorithm）是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法。贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是局部最优解能决定全局最优解（对有些问题这是显然的，如最小生成树（Minimum Spanning Tree），对其它问题却是非常不明显的，如单源最短路径（Single-Source Shortest Path））。

贪心算法与动态规划的不同在于：贪心算法对每个子问题的解决方案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。更详细的如下：

贪心算法是先做出选择再解决产生的子问题，而动态规划则是先解决子问题再做出选择。
动态规划每一步可能会产生多个子问题，而贪心算法一般每一步只会产生一个子问题（且为非空）
从特点上看，动态规划是自底向上解决问题，而贪心算法是自顶向下解决问题。

贪心算法可以解决一些最优化问题，如：求图中的最小生成树、求哈夫曼编码等。然而对于工程和生活中的问题，贪心算法一般不能得到我们所要求的答案。因为贪心算法采取的是局部最优策略，这种策略并不保证能得到全局最优解，因为选择的只是局部最优，所以它不像动态规划那样能解决更加复杂的最优化问题。

贪心算法的基本步骤：

建立数学模型来描述问题。
把求解的问题分成若干个子问题。
对每一子问题求解，得到子问题的局部最优解。
把子问题的局部最优解合成原来问题的一个解。

贪心算法的要素

贪心算法适用的前提是：局部最优策略能导致产生全局最优解。实际上，贪心算法适用的情况很少。工程中的问题很少能整除成满足这个特性的问题，所以在采用贪心算法前，必须对问题进行深入分析。

判断一个问题能否用贪心算法解决，即局部最优解能否导致全局最优解，通常需要依赖问题本身的特性以及一些数学证明。这通常涉及到两个主要的概念：最优子结构和贪心选择性质。

最优子结构：一个问题的最优解包含其子问题的最优解。简单来说，问题的最优解可以通过找到其子问题的最优解并选择最优的一种方案来构造。如果一个问题有最优子结构，一旦所有子问题都已解决，我们可以简单地通过在所有子问题中选择每个子问题的最优选择来找到全局最优解。
贪心选择性质：全局最优解可以通过局部最优选择来达到。也就是说，选择当前最优的解，也就是贪心选择，将会导致全局最优解。贪心选择性质是贪心算法可行的主要特性，它意味着我们可以做出一个局部最优选择，并且这个选择不会影响后续的选择，这样我们就可以保证最终的解是全局最优的。

对于许多问题，我们可以通过反证法或者归纳法来证明贪心策略的正确性。具体来说，我们可以假设存在一个不是由贪心策略得出的最优解，然后找出矛盾，或者我们可以证明问题的每一个步骤都可以应用贪心策略。

然而，值得注意的是，尽管贪心算法在某些问题上很有效，但并不是所有问题都适合使用贪心算法。有些问题可能看起来像是可以应用贪心算法，但在深入分析后可能发现不能得到全局最优解。这就需要我们对问题有深入的理解和分析。

贪心算法的问题集

哈夫曼树编码

哈夫曼编码（Huffman Coding）是一种广泛用于数据压缩的算法，特别是在文件压缩和通信编码中。哈夫曼编码是一种前缀编码，即在该编码中，任何字符的编码都不是其他字符编码的前缀，这使得编码的解码非常清晰，不会产生歧义。哈夫曼编码的一个关键特性是它是一种最优编码，即对于给定的字符频率，哈夫曼编码可以生成最短的平均编码长度。

哈夫曼编码算法的基本步骤如下：

创建一个节点列表，其中每个节点包含一个字符及其在数据中的频率。
将节点列表按照频率从低到高排序。
从列表中取出频率最低的两个节点，然后创建一个新的父节点，其频率是这两个节点频率的和。将这两个节点设置为新节点的左右子节点。
将新的父节点添加到列表中，并从列表中移除已处理的两个节点。
重复步骤3和4，直到列表中只剩下一个节点。这个节点就是哈夫曼树的根节点。

在哈夫曼编码算法中，贪心算法的应用体现在每次都选择频率最低的两个节点来创建新的父节点。这是一个贪心的选择，因为我们总是选择当前能够立即达到的最小频率。这种选择保证了生成的哈夫曼树的平均编码长度最短，即最优。

需要注意的是，虽然哈夫曼编码能够保证最短的平均编码长度，但它并不一定能够为每个字符生成最短的编码。实际的编码长度取决于字符的频率：频率高的字符会得到更短的编码，而频率低的字符可能会得到更长的编码。这样我们就能根据每个字母出现的频率最大程度的压缩信息。

在编程中，代码也很容易实现。我们可以定义一个优先队列储存所有的哈夫曼节点，每个节点是带有编码和频率的字符节点。然后我们可以每次从优先队列中弹出两个最小节点，把它们作为一个新的父节点的左、右孩子，并把父节点的频率设置为左右两节点的频率之和，再把父节点添加入优先队列中。这样重复n次（共n个节点）后得到的优先队列就是一个哈夫曼树。

伪代码实现如下。

HuffmanCodingAlgorithm(int A[],int n){
    //A是储存输入字符串的数组，n是A中的不重复元素个数
    初始化一个优先队列PQ，使其包括A的n个元素
    struct BinaryTreeNode*temp;
    for (i=1;i<n;i++){
        auto temp = new (BinaryTreeNode);
        temp->left = Delete-Min(PQ);
        temp->right = Delete-Min(PQ);
        temp->data = temp->letf->data + temp->right->data;
        Insert temp to PQ;
    }
    return PQ;
}

完整的c++代码实现如下。

#include <memory>
#include <queue>
#include <vector>

using namespace std;

struct HuffmanNode {
    char ch; // 字符
    int freq; // 频率
    shared_ptr<HuffmanNode> left;
    shared_ptr<HuffmanNode> right;
};

struct Compare {
    bool operator()(const shared_ptr<HuffmanNode>& a, const shared_ptr<HuffmanNode>& b) const {
        return a->freq > b->freq;
    }
};

priority_queue<shared_ptr<HuffmanNode>, vector<shared_ptr<HuffmanNode>>, Compare> 
HuffmanCodingAlgorithm(vector<pair<char, int>> A) {
    priority_queue<shared_ptr<HuffmanNode>, vector<shared_ptr<HuffmanNode>>, Compare> PQ;

    for (const auto& pair : A) {
        PQ.push(make_shared<HuffmanNode>(pair.first, pair.second, nullptr, nullptr));
    }

    while (PQ.size() > 1) {
        auto left = PQ.top(); PQ.pop();
        auto right = PQ.top(); PQ.pop();
        PQ.push(make_shared<HuffmanNode>('\0', left->freq + right->freq, left, right));
    }

    return PQ;
}

得到哈夫曼树后就可以根据哈夫曼树对信息压缩编码或解码了，要得到一个字符的编码，只需要遍历哈夫曼树查找该字符所在的节点，每经过一次左分支就标注0，经过一次右分支就标注1，最后得到的就是该字符的编码。解码操作也很简单，因为每个编码对应的节点唯一，所以只要根据01编码去定向寻找对应的节点，就可以找到对应的字符恢复数据。

最小生成树问题

这一部分在之前的数据结构——图论部分有过粗略的解释，但是当时并未附上源代码，现在我来详细的介绍一下求解最小生成树的两种算法：Prim算法和Kruskal算法。

Prim算法

这部分可以参考数据结构什锦（六）—— 走近图论| Adam8en の 8log。

具体的C++实现代码如下。

//分别储存所有的node、selected、minDist、parent
//初始化所有的node的selected为false，minDist为无穷大，parent为-1
//然后初始化第一个node的selected为true，minDist为0，parent为-1
//接着依次进行update->scan->add
#include <iostream>
#include <vector>
using namespace std;

// 定义图中的顶点
struct Vertex {
    int id;
    int distance; // 从起始位置到该顶点的最短距离
    [[maybe_unused]] bool selected; // 该顶点是否已经访问过
    vector<pair<int, int>> neighbors; // 该顶点的邻居（相邻顶点编号和边权重）
    //其中neighbor.first表示单项图中该顶点邻接的顶点的编号，neighbor.second表示边的权重
    int parent; // 该顶点在最短路径树中的父节点

    explicit Vertex(int _id) : id(_id), distance(INT_MAX), selected(false) , parent(-1) {};
};

// 定义图
class Graph {
public:
    vector<Vertex *> vertices; // 图中的所有顶点，对应邻接表中储存所有顶点的链表

    explicit Graph(int numVertices) {
        // 创建图中的所有顶点
        for (int i = 0; i < numVertices; ++i) {
            vertices.push_back(new Vertex(i));
        }
    }

    ~Graph() {// 析构函数，释放所有顶点的内存
        for (Vertex* v : vertices) {
            delete v;
        }
    }

    // 添加有向边
    void addDirectedEdge(int from, int to, int weight) {
        vertices[from]->neighbors.emplace_back(to, weight);
    }

    //添加无向边
    void addEdge(int from, int to, int weight) {
        vertices[from]->neighbors.emplace_back(to, weight);
        vertices[to]->neighbors.emplace_back(from, weight);
    }

    // Prim算法
    void prim(int start) {
        // 初始化所有的node的selected为false，minDist为无穷大，parent为-1
        for (Vertex *v: vertices) {
            v->selected = false;
            v->distance = INT_MAX;
            v->parent = -1;
        }
        // 初始化第一个node的selected为true，minDist为0，parent为-1
        vertices[start]->selected = true;
        vertices[start]->distance = 0;
        // 依次进行update->scan->add
        for (int i = 0; i < vertices.size(); ++i) {
            updateDistances(start);
            int next = scan();
            start = next;
            if (next == -1)
                break;
            add(next);
        }
        // 检查是否所有顶点都已被选中
        for (Vertex *v: vertices) {
            if (!v->selected) {
                cout
                        << "The graph is not connected. Cannot generate Minimum Spanning Tree."
                        << endl;
                return;
            }
        }
    }

    void updateDistances(int start) {
        for (auto &neighbor: vertices[start]->neighbors) {
            if (!vertices[neighbor.first]->selected &&
                neighbor.second < vertices[neighbor.first]->distance) {
                vertices[neighbor.first]->distance = neighbor.second;
                vertices[neighbor.first]->parent = start;
            }
        }
    }

    int scan() {
        int minDist = INT_MAX;
        int minVertex = -1;
        for (Vertex *v: vertices) {
            if (!v->selected && v->distance < minDist) {
                minDist = v->distance;
                minVertex = v->id;
            }
        }
        return minVertex;
    }

    void add(int next) {
        vertices[next]->selected = true;
    }
};
int main(){
    Graph g(6);
    g.addEdge(0, 1, 6);
    g.addEdge(0, 2, 1);
    g.addEdge(0, 3, 5);
    g.addEdge(1, 4, 3);
    g.addEdge(2, 1, 2);
    g.addEdge(2, 4, 6);
    g.addEdge(3, 2, 2);
    g.addEdge(3, 4, 7);
    g.addEdge(4, 5, 1);
    g.prim(0);
    for (Vertex *v: g.vertices) {
        cout << "Vertex " << v->id << " parent is " << v->parent << endl;
    }
    return 0;
}

Kruskal算法

这一部分之前也有所提及，原理可以参考数据结构什锦（六）—— 走近图论 | Adam8en の 8log这篇文章中对克鲁斯卡尔算法的介绍。

其实原理很简单，就是把每个无向边取出，按权重排序后依次添加进图中，当边数达到n-1时（假设一共有n个顶点），就生成了最小生成树。每放进去一条边都要进行一次判断是否成环，如果成环就丢掉这条边。

这里唯一比较难搞的点就是判断新加入的边是否成环，这里可以用一种叫并查集的数据结构方便的实现这一目的。关于并查集，可以参考这篇文章并查集的一些个人观点以及克鲁斯卡尔算法的详解_kruskal算法为什么用并查集-CSDN博客。

其实并查集也很简单，一言以概之，就是用一个数组去储存元素，下标代表元素的位置，数组的值代表元素的父节点。整体实现后代码也很简单，大概长这样：

int find(int a)
{
    if (father[a] == a)
    {
        return a;
    }
    return father[a] = find(father[a]);//这里顺便压缩了路径
    //把每个路径上的节点的父节点都改成最 祖宗 的那一个（
}
void merge(int x, int y)
{
    int tx = find(x), ty = find(y);
    if (tx != ty)
    {
        father[tx] = ty;
        //判断，如果两个顶点的祖先不一样则进行合并操作
    }
    return;
}

那么，根据并查集的思想，我们可以把每个顶点作为元素储存进一个数组中。初始化把每个顶点都赋值为它本身，代表每个顶点在开始时都是独立的根节点，然后每加入一条边就把两个顶点进行合并。如果遇到加入边导致顶点在一个集合内的情况，就说明会成环，就舍弃这条边跳过到下一条即可。

那么最终实现的代码版本如下。

#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;

struct Edge {
    int from, to, weight;
    Edge(int _from, int _to, int _weight) : from(_from), to(_to), weight(_weight) {}
};

bool compareEdges(const Edge &a, const Edge &b) {
    return a.weight < b.weight;
}

class UnionFind {
private:
    vector<int> parent;
public:
    explicit UnionFind(int n) : parent(n) {
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
        }
    }
    int find(int x) {
        while (parent[x] != x) {
            x = parent[x];
        }
        return x;
    }
    void unionSet(int x, int y) {
        parent[find(x)] = find(y);
    }
};

class Graph {
public:
    vector<Edge> edges;
    int numVertices;
    explicit Graph(int _numVertices) : numVertices(_numVertices) {}

    void addEdge(int from, int to, int weight) {
        edges.emplace_back(from, to, weight);
    }

    void kruskal() {
        sort(edges.begin(), edges.end(), compareEdges);
        UnionFind uf(numVertices);
        for (const Edge &edge : edges) {
            if (uf.find(edge.from) != uf.find(edge.to)) {
                cout << "Adding edge: " << edge.from << " - " << edge.to << " weight: " << edge.weight << endl;
                uf.unionSet(edge.from, edge.to);
            }
        }
    }
};

int main() {
    Graph g(6);
    g.addEdge(0, 1, 6);
    g.addEdge(0, 2, 1);
    g.addEdge(0, 3, 5);
    g.addEdge(1, 4, 3);
    g.addEdge(2, 1, 2);
    g.addEdge(2, 4, 6);
    g.addEdge(3, 2, 2);
    g.addEdge(3, 4, 7);
    g.addEdge(4, 5, 1);
    g.kruskal();
    return 0;
}