贪心算法是求解最优问题的一种解决策略，通过把问题分步，每一步上都采取一种贪心的决策，最终构建一个决策树解决问题，使用贪心算法往往不能得到问题的最优解，但是可以得到局部最优解，而且有时候局部最优解就是问题的最优解。

        贪心算法的复杂度往往比穷举等其他算法快很多，但其需要经过证明才能确定是否是最优解，但是有一些常用的问题是被证明可以用贪心算法得到最优解的。

        先举个0/1背包问题来理解下贪心算法，所谓0/1背包问题，意思是说每件物品可以拿（1），也可以不拿（0）。有一个背包，总容量为20，还有一些物品，每种物品只有一样，物品的体积分别为【5，7，3，4，8，1】，重量分别为【11，14，6，9，18，1】，怎么拿才能装到总质量最重的物品呢？

        第一个人按照他贪心的想法，每次选择最重的物品，最后肯定是最重的，则选择方案为（体积）【8，7，5】，三个物品，刚好20，总重为18+14+11=42

        第二个人想，每次选择体积最小的物品，这样可以拿尽量多的东西，则最终肯定是最重的，则选则方案是：【1，3，4，5，7】5个物品正好体积20，总重为1+6+9+11+14=41

        第三个人想：每次选择密度最大的物品，这样总质量肯定是最重的，物品的密度分别为【2.2，2，2，2.25，2.25，1】，则选择方案是【4，8，5，3】，总重量为 9+18+11+6=44

        可以发现，同样是贪心算法，不同的方案会有不同的结果，就是上面说的贪心算法往往得不到最优解，这里虽然第三种方案得到了最优解，但实际上贪心算法并不能解决所有的0/1背包问题。假设第三方案背包最后剩2，但没有体积为2的物品，则最后无法按照"密度最大"这个贪婪方案，因此总重量就不一定比其他人的重了。贪心算法可以用来解决部分背包问题，所谓部分背包问题，就是说物品不一定是只能拿全部或者不拿，也可以拿部分，比如说是沙子，米，大豆，就可以拿部分，这样，就可以使用密度最大的贪心方案拿物品，其结果也一定是最优解。

以下两种求最小生成树的算法是典型的贪心算法：

prim算法

        prim算法用于生成最小生成树，是一个典型的贪心算法，如下图，假设从1开始生成最小生成树，先把所有的点设置为未处理，从1开始，更新2和4的距离为12和7，并选择最近距离的点4为下一个点处理点

image.png

        更新4相邻的点的距离，并选择未处理的最近的点2作为下一个处理点

image.png

        然后处理点2，更新3和5的距离（能变小就更新），并得到下一个处理点3（未处理中距离最小的）

image.png

        接续处理3，然后处理5

image.png

        然后处理6，只剩7，结束

image.png

        最小生成树为：

image.png

    代码如下：

#include <iostream>
#include <cstring>
using namespace std;

char flag[8] = {0};
char line[10][10] = {0};
int dis[8] = {0};

void toline(int s, int e, int len) {
    line[s][e] = len;
    line[e][s] = len;
}

//获取未处理的，路径最短的点，最小长度累加
int GetMinPoint(int& len) {
    int tmp = 0;
    int pos = 0;
    for (int i = 1; i < 8; i++)
    {
        if (flag[i] == 1) //处理过了
            continue;
        
        if (pos == 0)
        {
            pos = i;
            tmp = dis[i];
        }else{
            if (tmp > dis[i])
            {
                tmp = dis[i];
                pos = i;
            }
        }
    }
    flag[pos] = 1;
    len += tmp;
    return pos;
}

int Prim() {
    int len = 0;
    dis[1] = 0;
    flag[1] = 1;
    int pos = 1;
    do
    {
        cout << pos << " ";
        //更新dis与pos的路径
        for (int i = 1; i < 8; i++)
        {   
            //不是自己，且没有处理过，且距离更小，则更新距离
            if (i != pos && flag[i] == 0 && dis[i] > line[pos][i])
                dis[i] = line[pos][i];
        }
        //继续选下一个点
        pos = GetMinPoint(len);
    } while (pos != 0);
    cout << endl;
    return len;
}

int main() {
    memset(line, 100, 100); //先把路径设为很大
    //连线
    toline(1, 2, 12);
    toline(1, 4, 7);
    toline(2, 3, 8);
    toline(2, 4, 3);
    toline(2, 5, 11);
    toline(3, 5, 7);
    toline(4, 6, 9);
    toline(5, 6, 2);
    toline(5, 7, 7);
    toline(6, 7, 5);
    //先把dis设为很大
    for (int i = 0; i < 8; i++)
        dis[i] = 100;
    
    cout << Prim() << endl;
    return 0;
}
//最终输出
1 4 2 3 5 6 7 
32

kruskal算法

        kruskal算法也是基于贪心的算法，它是对边进行从短到长进行选择，直到所有节点都在一颗树内。具体步骤如下：还是上图，

        首先选择最短边2，连接5，6，并标记5，6节点已处理

image.png

        接着，选择最短边3，连接2，4并标记2，4为已处理

image.png

        然后，重复上面的步骤，选择最短边5，连接6，7，由于7并没有标记过，因此可行，并把7标记为已处理

image.png

        继续重复上面的步骤，选择长度为7的边，因为5，7节点已经被标记，因此不能选择连接5，7的边，其他的都符合，因此把1，4和5，3相连并标记

image.png

        此时所有节点都被选择，但并不在一棵树内，因此继续选择8，把2，3相连，构成一颗完整的树，就是最小生成树。结果和prim的方法一致

image.png

        代码分析：首先，对边进行排序，然后遍历边，取边的两个点，判断2个点是否都已经选择过，如果非都选择过，则选择，否则判断是2个点是否属于同一棵树，如果不同一棵树，则可以相连，直到边的数量为点的数量-1，结束

#include <iostream>
#include <cstring>
#include <map>
using namespace std;

multimap<int, pair<int, int>> mapLine;
int root[8] = {0};

//检查2个点是否可以选, 同时处理根节点
bool CheckOK(int n, int m) {
    //如果都没选过，则可以，根设为n
    if (root[n] == 0 && root[m] == 0)
    {
        cout << " " << n << " " << m;
        root[n] = n;
        root[m] = n;
        return true;
    }
        
    //如果两个根不相等，可选
    if (root[n] != root[m]) 
    {
        //n没有选过的，n的根设为m的根，
        if (root[n] == 0) {
            cout << " " << n;
            root[n] = root[m];
            return true;
        }
        //反之亦然
        if (root[m] == 0) {
            cout << " " << m;
            root[m] = root[n];
            return true;
        }
        //否则，说明2个点在不同子树, 让所有根和m一样的变为和n的根一样
        int r = root[m];
        for (int i = 1; i < 8; i++)
        {
            if (root[i] == r)
                root[i] = root[n];
        }
        return true;
    }
    return false;
}

int Kruskal() {
    int total = 0;
    int lines = 0;
    //最多6条边
    while (lines < 6) {
        //取最短的边
        auto it = mapLine.begin();
        if (it == mapLine.end())
            return total;
        //检查边的两点是否可以相连
        if (CheckOK(it->second.first, it->second.second)){
            lines++; //边数量+1
            total += it->first; //更新总路径
        }
        mapLine.erase(it);
    }
    cout << endl;
    return total;
}


int main() {
    mapLine.insert(make_pair(12, make_pair(1, 2)));
    mapLine.insert(make_pair(7, make_pair(1, 4)));
    mapLine.insert(make_pair(8, make_pair(2, 3)));
    mapLine.insert(make_pair(3, make_pair(2, 4)));
    mapLine.insert(make_pair(11, make_pair(2, 5)));
    mapLine.insert(make_pair(7, make_pair(3, 5)));
    mapLine.insert(make_pair(9, make_pair(4, 6)));
    mapLine.insert(make_pair(2, make_pair(5, 6)));
    mapLine.insert(make_pair(7, make_pair(5, 7)));
    mapLine.insert(make_pair(5, make_pair(6, 7)));

    cout << Kruskal() << endl;
    return 0;
}
//输出
 5 6 2 4 7 1 3
32


显示更多
Copyright © 2018-2023 lazypos.cn