算法设计方法之 贪婪算法

贪婪算法是一种非常直观的求解方法,虽然未必能产生最优解,但是能够近似最优解,用贪婪算法可以求解货箱装载问题,背包问题,拓扑排序问题,最短路径问题等

最优化问题:

明确: 

1. 约束条件

2. 可行解

3. 目标函数

4. 最优解

举个例子:

一个口渴的人想要解渴,他可以得到n种不同的饮料,但是他对每种饮料的满意度值不同,但是单一的一种饮料不足以满足他需要的量,他需要饮用不同种类的饮料。假设他对第i种饮料的满意度值是算法设计方法之   贪婪算法,他要应用的量是算法设计方法之   贪婪算法,每种饮料的总量是算法设计方法之   贪婪算法,总的需求量是t,则问题的模型可以转化为:

通过寻找一组解算法设计方法之   贪婪算法

算法设计方法之   贪婪算法

使得p达到最大值:

且要满足:

算法设计方法之   贪婪算法

算法设计方法之   贪婪算法

这两个条件。

类似的问题还有货箱装载问题,最小成本通信网络问题,也即最小成本生成树。

贪婪算法思想:

在贪婪算法中,需要逐步构造一个最优解,每一步都在一定的标准下做出最优决策,且在以后的步骤中不能修改,做出决策所依据的标准称为贪婪准则。

如:找零钱问题

1. 机器调度问题:

假设有n个任务,机器个数不限,每个人物的开始时间a,完成时间b,时间段[a,b]为任务的处理时段。

例如:两个任务[1,4],[2,4]是有重叠的,[1,4][4,7]是没有重叠的,一个可行的分配方案是指没有把重叠的任务分配个给同一个机器。最优方案是指栈用的机器数量最少。

假设有7个任务,如果每台机器分配一个,这虽然是一个可行方案,但是明显不是一个最优方案。

贪婪法获得最优方案:每一步分配一个任务,且按照任务开始时间的非递减顺序进行。一台机器如果有至少一个任务,则成为旧机器,没有任务的机器称为新机器。采用的贪婪准则是:根据任务开始的时间,优先将任务分配给可用的旧机器。如果没有,再分配给新机器。

2. 最短路径问题:

算法设计方法之   贪婪算法

如图所示的网络,寻找一条从1到5的最短路径。

箱子排序问题:

采用贪婪算法解决箱子装载问题:

在重量固定的情况下,装载最多的箱子:

箱子重量为:【100, 200, 50, 90, 150, 50, 20, 80】

实现代码:

#include <iostream>

using namespace std;

struct box    // 箱子结构体,有箱子的id和重量 
{   
    int idd;
    int weight;

};


void containerLoading(box* p, int capacity, int box_num, int* x)
{
    for(int i=1; i<=box_num-1; i++)    //先对box进行排序 
    {
        int min_weight = p[i].weight;
        int min_index = i;
        for(int j=i+1; j<=box_num; j++)
        {
            if(p[j].weight<min_weight)
            {
                min_weight = p[j].weight;
                min_index = j;
            }
        }
        // 交换p[i]和tmp_box 
        box tmp_box = p[i];
        p[i] = p[min_index];
        p[min_index] = tmp_box;
    }

    cout << "排序后的箱子:" << endl;
    cout << "Id" << "  " << "Weight" << endl; 
    for(int i=1; i<=box_num; i++)
    {
        x[i] = 0;
        cout << p[i].idd << "  " << p[i].weight << endl;
    }

    for(int i=1; i<box_num && p[i].weight<capacity; i++)
    {
        x[p[i].idd] = 1;   // 第i个被装载的箱子
        capacity -= p[i].weight;    // 剩余容量 
    }

    cout << "结果:" << endl;
    for(int i=1; i<=box_num; i++)
    {
        cout << x[i] << " ";
    }
    cout << endl;
}


int main(int argc, char *argv[])
{
    int box_number = 8;
    int number_weight[] = {100, 200, 50, 90, 150, 50, 20, 80}; 
    int xx[box_number+1];
    int c = 400;
    box* boxp = new box[box_number+1];
    for(int i=1; i<=box_number; i++)
    {
        boxp[i].idd = i;
        boxp[i].weight = number_weight[i-1];
    }   // 初始化箱子 

    containerLoading(boxp, c, box_number, xx);
    return 0;
}

运行结果:

算法设计方法之   贪婪算法

0/1背包问题:

n个物品和一个容量为c的背包,从n个物品中选取装包的物品,第i个物品重量为w_i, 价值为p_i,在满足约束条件的情况下,使得价值最高:

所以问题描述是:

算法设计方法之   贪婪算法

约束条件是:

算法设计方法之   贪婪算法

算法设计方法之   贪婪算法

这个问题也是类似于上面货物装载的问题:

对于0/1背包问题,可能的贪婪准则:

1. 价值贪婪准则: 每次存剩余的物品中选择加价值最高的

2. 重量贪婪准则:每次从剩余的物品中选择重量最轻的

3. 价值密度贪婪准则:每次选择 价值/重量 最大的物品

但是,正对不同的问题,以上三种情况得到的不一定是最优解:

贪婪启发式方法:

上述问题是一个NP-复杂问题,在上面的贪婪准则中,价值密度虽然不一定得到最优解,但也是一种不错的启发式算法。

对贪婪启发式方法的改进:

首先将最多k件物品放入背包,如果k件物品的重量大于c,则放弃这k件物品,否则,根据背包剩余的容量,将剩余的物品按照价值密度递减的顺序放入。这种方法称为k阶优化。

 

原文链接: https://www.cnblogs.com/ncepubye/p/12724044.html

欢迎关注

微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬

    算法设计方法之   贪婪算法

原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/396633

非原创文章文中已经注明原地址,如有侵权,联系删除

关注公众号【高性能架构探索】,第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处!

(0)
上一篇 2023年4月6日 上午11:26
下一篇 2023年4月6日 上午11:26

相关推荐