VDOM
何为贪心?
- 贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,算法得到的是在某种意义上的局部最优解。(百度百科解释)
- 贪心思想,同样是长度为 2 的序列,[1,2] 一定比 [1,4] 好,因为它更有潜力。换句话说,我们想要组成最长的递增子序列, 就要让这个子序列中上升的尽可能的慢,这样才能更长。
贪心使用条件
利用贪心法求解的问题应具备如下2个特征。
- 贪心选择性质
一个问题的整体最优解可通过一系列局部的最优解的选择达到,并且每次的选择可以依赖以前作出的选择,但不依赖于后面要作出的选择。这就是贪心选择性质。对于一个具体问题,要确定它是否具有贪心选择性质,必须证明每一步所作的贪心选择最终导致问题的整体最优解。 - 最优子结构性质
当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用贪心法求解的关键所在。在实际应用中,至于什么问题具有什么样的贪心选择性质是不确定的,需要具体问题具体分析
贪心存在问题编
贪心算法也存在如下问题:
1、不能保证解是最佳的。因为贪心算法总是从局部出发,并没从整体考虑
2、贪心算法一般用来解决求最大或最小解
3、贪心算法只能确定某些问题的可行性范围 。
- 本文作者: Littleki
- 本文链接: https:/littleki.gitee.io/2021/04/28/VDOM/
- 版权声明: 本博客所有文章除特别声明外,均采用 MIT 许可协议。转载请注明出处!