0%

贪婪法

简介

贪婪法又称贪心算法, 是寻找最优解问题的常用方法,

区别

  • 相同点: 贪婪法和动态规划法以及分治法一样, 主要对问题进行分解, 定义最优解的子结构
  • 不同点: 贪婪法每一步选择完之后, 局部最优解就确定了, 不再进行回溯处理, 也就是每一个步骤的局部最优解确定以后, 就不再修改, 直到算法结束, 因为不进行回溯处理, 贪婪法只在很少的情况下可以得到真正的最优解, 比如最短路径问题, 图的最小生成树问题, 大多数情况下, 由于选择策略的局部最优解, 贪婪法会错过真正的最优解, 得不到问题的真正答案, 但是贪婪法简单高效, 省去了为找最优解可能需要的穷举操作, 可以得到与最优解比较接近的近似最优解, 通常作为其他算法的辅助算法使用

基本思想

贪婪法的基本设计思想有以下三个步骤:

  1. 建立对问题精确描述的数学模型, 包括定义最优解的模型
  2. 将问题分解为一系列子问题, 同时定义子问题的最优解结构
  3. 应用贪心原则确定每个子问题的局部最优解, 并根据最优解的模型, 用子问题的局部最优解堆叠出全局最优解

例子

找零钱

找零钱是一个经典的例子, 假如某国发行的货币有 25 分, 10 分, 5 分和 1 分四种硬币, 如果每次支付一定金额的时候都需要保证硬币个数最少, 那就可以使用贪婪法来处理

基于上面的步骤, 将问题分解成按照货币的大小顺序, 保证每次都计算上最多的最大面值的硬币即可

如果现在需要支付 41 分钱, 那流程如下

  1. 选择 25 分的硬币一枚
  2. 选择 10 分的硬币一枚
  3. 选择 5 分的硬币一枚
  4. 选择 1 分的硬币一枚

总共需要 4 枚硬币, 由于该实例每个子问题的最优解合并起来就是全局的最优解, 所以使用贪婪法是最合适的

很多情况下计算了所有局部最优解, 但合并成全局确不是最优解

同样以找零钱为例, 假如某国发行的货币是 25 分, 20 分, 5 分和 1 分四种硬币, 这时候找 41 分钱的最优策略是 2 枚 20 分的硬币加一枚 1 分硬币共 3 枚硬币, 但是用贪婪法得到的结果却是 1 枚 25 分硬币, 三枚 5 分硬币和一枚 1 分硬币共 5 枚硬币

0-1 背包问题

问题: 有 N 件物品和一个承重为 C 的背包 (也可定义为体积), 每件物品的重量是 $w_i$ , 价值是 $p_i$ , 求解将哪几件物品装入背包可使这些物品在重量总和不超过 C 的情况下价值总和最大, 这里限定每件物品只能选择 0 个或 1 个

现在有一个背包, 最多承载重量 $C=150$ 的物品, 有七个物品, 编号为 $1~7$, 重量为 $w_i=[35,30,60,50,40,10,25]$, 价值为 $p_i=[10,40,30,50,35,40,30]$, 需要确保装进背包的物品价值最高

由于是每个物品只有一份, 所以使用贪婪法是最适合的, 物品具有多重属性, 所以可以通过不同的策略进行计算

  • 根据物品价值选择, 每次都选价值最高的物品, 最终选择装入背包的物品编号依次是 4, 2, 6, 5, 此时包中物品总重量是 130, 总价值是 165
  • 根据物品重量选择, 每次都选择重量最轻的物品, 最终选择装入背包的物品编号依次是 6, 7, 2, 1, 5, 此时包中物品总重量是 140, 总价值是 155
  • 根据价值密度的概念, 就是计算哪个物品同重量下价值最高, 也就是通过权重来选择策略, 设置一个权重值 $s_i$, 该值计算方法如下, 最终选择装入背包的物品编号依次是 6, 2, 7, 4, 1, 此时包中物品的总重量是 150, 总价值是 170

$$s_i=\frac{p_i}{w_i}=[0.286,1.333,0.5,1.0,0.875,4.0,1.2]$$

小结

对于一些能够证明贪婪策略得到的就是最优解的问题, 应用贪婪法可以高效地求得结果, 比如求最小生成树的 Prim 算法和 Kruskal 算法, 大多数情况下, 贪婪法只能得到比较接近最优解的近似的最优解, 但是作为一种启发式辅助方法, 它常用于其他算法中, 比如 Dijkstra 的单源最短路径算法, 事实上, 在任何算法中, 只要在某个阶段使用了只考虑局部最优情况的选择策略, 都可以理解为使用了贪婪算法