贪心算法

贪心算法(greedy algorithm)

算法思路

  1. 第一步,当我们看到这类问题的时候,首先要联想到贪心算法:针对一组数据,我们定义了限制值期望值,希望从中选出几个数据,在满足限制值的情况下,期望值最大
  2. 第二步,我们尝试看下这个问题是否可以用贪心算法解决:每次选择当前情况下,在对限制值同等贡献量的情况下,对期望值贡献最大的数据。
  3. 第三步,我们举几个例子看下贪心算法产生的结果是否是最优的。大部分情况下,举几个例子验证一下就可以了。严格地证明贪心算法的正确性,是非常复杂的,需要涉及比较多的数学推理。而且,从实践的角度来说,大部分能用贪心算法解决的问题,贪心算法的正确性都是显而易见的,也不需要严格的数学推导证明

应用场景

  1. 霍夫曼编码(Huffman Coding),霍夫曼编码是一种十分有效的编码方法,广泛用于数据压缩中,其压缩率通常在 20%~90% 之间。
  2. Prim 和 Kruskal 最小生成树算法
  3. 还有 Dijkstra 单源最短路径算法

You may also like...

发表评论

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