算法分析笔记:贪心算法

2023年09月15日 2.1k 字大概 9 分钟

贪心算法(Greedy Algorithm)

1.算法基本思想

最优子结构的情况下可用动态规划法，但有时也会有更加简单有效的方法。贪心算法就是在解决子问题时，总是做出当前问题的最好判断。可以说其解决思路是短视和局部的，它并不考虑整体的最优解，只专注于局部问题的解。

上面的描述来看，贪心算法更加直接和高效，但其局限性也很大：很多问题的最优解并不是直接解决其子问题最优解就能得出来的。虽然贪心算法显然不能解决所有问题，但我们依旧可以用它来获得局部的最优解。

1.1 贪心选择性质

上面提到，贪心算法仅在当前问题中做最优解。其选择可以依赖于其曾今的解，但是绝对不会依赖于之后所做的选择。所以该算法通常使用自顶向下的解决顺序。

1.2 贪心算法与动态规划算法的差别

两种算法皆具有最优子结构性质。在笔者的上一篇笔记《算法分析笔记:动态规划》中有提到0-1背包问题。与这个问题类似的一个问题为背包问题。

背包问题

与0-1背包问题类似的，给定种物品，物品的重量是，其价值为，背包容量为。问如何选择物品放入背包，使得背包中物品的总价值最大。但是在背包问题中，可以选择物品的一部分装入背包，而不是全部装入。因此背包问题可以直接根据物品的单位重量价值进行装载。优先装载单位价值高的物品，该物品全部装入背包后如果仍未装满，则选择单位价值次高的物品，直到装满为止。该问题很显然可以使用贪心算法解决，而0-1背包问题不行，因为0-1背包问题不能拆分物品也就意味着其问题的整体最优解不一定对应自顶向下的子问题最优解。算法基础代码如下:

void knapsack(int a, float M, float v[], float w[], float x[])
{
    Sort(n,v,w);
    int i;
    for (i = 1; i <= n; i++)
    {
        x[i] = 0;
    }
    float c = M;
    for (i = 1;i <= n; i++)
    {
        if (w[i] > c)
        {
            break;
        }
        x[i] = 1;
        c -= w[i];
    }
    
    if(i <= n)
    {
        x[i] = c/w[i];
    }
}

上述算法计算时间上界为。

2.算法应用问题

2.1 单源最短路径(Single Source Shortest Path)

2.1.1 问题描述

给定一个带权有向图，每条边的权都是非负实数，给定中的一个顶点称为源。求源到中所有顶点的最短路径。下图是该问题的一个示意图：

2.1.2 Dijkstra算法

Dijkstra算法是贪心算法设计策略的又一个典型例子。在中选择具有最短路线的顶点，并将其加入到中。然后对于每个中的顶点，如果存在一条从到的边，那么就更新从源到的最短路径。

我们这样描述Dijkstra算法：输入带权有向图，源为顶点。使用二维数组表示边的权值。使用数组表示当前从源到顶点的最短路径长度。基本代码如下:

template <class Type>
void Dijkstra(int n, int v, Type dist[], int prev[], Type **c)
{
    bool s[maxint];             // 判断是否已经求得最短路径
    for (int i = 1; i <= n; i++)
    {
        dist[i] = c[v][i];
        s[i] = false;
        if (dist[i] == maxint)
        {
            prev[i] = 0;
        }
        else
        {
            prev[i] = v;
        }
    }
    dist[v] = 0;
    s[v] = true;
    for (int i = 1; i < n; i++)
    {
        Type temp = maxint;
        int u = v;
        for (int j = 1; j <= n; j++)
        {
            if ((!s[j]) && (dist[j] < temp))
            {
                u = j;
                temp = dist[j];
            }
        }
        s[u] = true;
        for (int j = 1; j <= n; j++)
        {
            if ((!s[j]) && (c[u][j] < maxint))
            {
                Type newdist = dist[u] + c[u][j];
                if (newdist < dist[j])
                {
                    dist[j] = newdist;
                    prev[j] = u;
                }
            }
        }
    }
}

以上算法总体需要的时间完成。

对于上面2.2.1问题描述中给出的一个有向图，我们计算从源顶点1到其它顶点的最短路径，推演其迭代过程，使用表格记录:

迭代	S	u	dist[2]	dist[3]	dist[4]	dist[5]
初始	{1}	--	10	maxint	30	100
1	{1,2}	2	10	60	30	100
2	{1,2,4}	4	10	50	30	90
3	{1,2,4,3}	3	10	50	30	60
4	{1,2,4,3,5}	5	10	50	30	60

上述算法具体的过程解析可以参考这篇推文:《图文详解 Dijkstra 最短路径算法》

2.2 最小生成树(Minimum Spanning Tree)

2.2.1 问题描述

设是无向连通带权图。中每条边的权为。如果的一个子图是包含的所有顶点的树，则称为$G的生成树。而其中，其耗费最小的(或者说边最少)生成树即为最小生成树。

解决该问题之前，我们需要了解其的性质。设是连通带权图，是的真子集。如果，且，，且的权值最小，这条边一定存在于的最小生成树中。

2.2.2 Prim算法

对于上面所说的，首先置，只要是的真子集，就做如下选择：选取满足条件的，，且最小的边，并将顶点加入到。直到为止。简单来说，就是将“最短”的连接边加入到生成树中，直到获得完整顶点以得到最小生成树。以下面的连通带权图为例：

下图为Prim算法的图片过程：

简单来说，该算法将原图打散，从出发点开始，统计所有连接着已经过点和未经过点的边，并找到最短的一条，将其连接的原未经过点加入到已经过点中并循环改过程。下面是基本代码：

template <class Type>
void Prim(int n, Type** c)
{
    Type lowcost[maxint];
    int closest[maxint];
    bool s[maxint];
    s[1] = true;
    for (int i = 2; i <= n; i++)
    {
        lowcost[i] = c[1][i];
        closest[i] = 1;
        s[i] = false;
    }

    for(int i = 1; i < n; i++)
    {
        Type min = inf;
        int j = 1;
        for(int k = 2; k <= n; k++)
        {
            if((lowcost[k] < min) && (!s[k]))
            {
                min = lowcost[k];
                j = k;
            }
        }
    }

    cout << "(" << closest[j] << "," << j << ")" << endl;
    s[j] = ture;
}

其时间复杂度为

。

2.2.3 Kruskal算法

Kruskal算法是解决最小生成树问题的另一种常用算法。如果说Prim算法是以相邻顶点为出发点，通过连接最短边的方式找到下一个点，那么Kruskal算法则是先找最短边，使用以边为出发点找到对应点来构建最小生成树。

算法的基本思想是：先将图中每个顶点看成独立的分支，将所有边按从大到小排列，依次观察该边是否连接了两个独立的分支。如果是，则将该边以及对应顶点加入到树中，否则直接查看下一条。完成所有边的验证后，得到的就是最小生成树。

以下为算法的基本代码：

template <class Type>

class EdgeNode
{
    freind ostream& operator<< (ostream&,EdgeNode<Type>);
    friend bool Kruskal(int, int, EdgeNode<Type>*, EdgeNode<Type>* );
    friend void main(void);
public:
    operator Type() const
    {
        return weight;
    }
private:
    Type weight;
    int u, v;
}

//Kruskal算法
template <class Type>
bool Kruskal(int n, int e, EdgeNode<Type> E[], EdgeNode<Type> t[])
{
    MinHeap<EdgeNode<Type>> H(1); //使用最小堆，用于存放顺序排列的边
    H.Initialize(E, e, e);
    UnionFind UF(n); //这是一个抽象的数据集，可以进行连接或查找操作
    int k = 0;
    while (e && k < n-1)
    {
        EdgeNode<int> x;
        H.DeleteMin(x);
        e--;
        int a = U.Find(x.u);//Find操作，返回集合中对应顶点所在分支的名字
        int b = U.Find(x.v);
        if (a != b)//判断顶点是否在同一分支
        {
            t[k++] = x;
            U.Union(a, b);//Union操作，将两个分支合并
        }
        H.Deactivate(x);
        return (k == n-1);
    }
}

对于一个有条边的图，组成优先队列需要的时间。DeleteMin需要时间。实现UnionFind所需时间为或者。因此Kruskal算法的时间复杂度为。

由此可以看出，当时，Kruskal算法要比Prim算法差，但是当时，Kruskal算法要比Prim算法好。