获取内容资料
综合学习

贪心算法的策略

所谓贪心算法是指,在对问题求解时,总是 做出在当前来看是最好的选择。也就是说,不从整体最优上加以考虑,通过贪心算法做出来的往往是在把 原问题拆分成几个小问题,分别求 每个小问题的最优解,再把这些“局部最优解”叠起来,就作为整个问题 当前 的最优解。

贪心算法无固定的算法框架,算法设计的关键是贪心策略的选择,必须注意的是,贪心算法不是对所有问题都能得到整体最优解,选择贪心策略必须具备 无后效性(即某个状态以后的过程不会影响以前的状态,只与当前状态有关)。

比如,求 最小生成树的Prim算法 和 Kruskal算法 都是漂亮的贪心算法。

贪心算法的策略

二、基本思路

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

三、存在的问题

不能保证求得的最后解是最佳的;不能用来 求最值 的问题;只能求 满足某些约束条件 的可行解的范围。

四、例题分析

[背包问题]有一个背包,容量是M=150,有7个物品,物品可以分割成任意大小。要求尽可能让装入背包中的物品总价值最大,但不能超过总容量。

物品:A B C D E F G

重量:35 30 60 50 40 10 25

价值:10 40 30 50 35 40 30

题目分析:为了使背包总价值最大,我们可以制定三种策略:

每次挑选价值最大的物品装入背包;每次挑选重量最小的物品装入背包;每次挑选单位重量价值最大的物品装入背包;

策略 1 结果:选择 D B F E 总重量 130 总价值 165;

策略 2 结果:选择 F G B A E 总重量 140 总价值 155;

策略 3 结果:选择 F B G D A 总重量 150 总价值 170;

结果分析:可以看到单位重量价值最大的策略 的结果比其它更好。

总结:由此可见,策略制定的不同,得到的解也会不同,我们只需要针对不同的问题制定不同的策略即可。

五、算法的使用前提

原问题复杂度过高;求全局最优解的数学模型难以建立;求全局最优解的计算量过大;没有太大必要一定要求出全局最优解,“比较优”就可以。

六、分解问题方式

按串行任务分

时间串行的任务,按子任务来分解,即每一步都是在前一步的基础上再选择当前的最优解。

按规模递减分

规模较大的复杂问题,可以借助递归思想,分解成一个规模小一点点的问题,循环解决,当最后一步的求解完成后就得到了所谓的“全局最优解”。

按并行任务分

这种问题的任务不分先后,可能是并行的,可以分别求解后,再按一定的规则(比如某种配比公式)将其组合后得到最终解。

Similar Posts

发表评论

邮箱地址不会被公开。 必填项已用*标注