基本思想
贪心算法是一种稳扎稳打的算法,它从问题的某一个角度出发,在每一个阶段都根据相应的贪心策略做出当前最优决策,逐步逼近最终目标,尽可能快地求出最优解。贪心算法可以理解为局部最优,最后达到全局最优。贪心算法的核心思想就是“今朝有酒今朝醉”,只考虑当前面临的问题,不考虑接下来会发生什么。
特点
- 1.贪心算法每个决策一旦做出,不可撤回,即贪心不允许回溯。
- 2.贪心是根据贪心策略来逐步构造问题的,所选贪心策略不同,其具体算法实现也会不同,算法质量也不同。因此,算法的好坏在于贪心策略的选择。
- 3.贪心算法就有高效性和不稳定性,因为它可以迅速地得到一个解,但不一定是最优解,但无论是不是最优解,它一定是最优解的一个近似值。
基本要素
1.最优子结构
当一个问题的最优解一定包含其子问题的最优解时,此问题具有最优解性质。即一个问题能分成若干个子问题,通过对子问题的最优解的推导(数学归纳),可以得到原问题的最优解。只有问题的子问题具有最优解时,才能保证贪心可以求得原问题的最优解。
2.贪心选择性质
贪心选择性质是指通过一系列的逐步局部最优选择,使得最终的选择是最优的,其次,每次做的选择依赖于前一次的选择,但不依赖于下一次的选择。贪心所做的是一个非线性的子问题处理(一个子问题不依赖于另一个子问题,但又有严格的处理顺序要求)。
贪心法的解题步骤
- 1.将问题分为若干个互相独立的子问题。
- 2.制定贪心策略并选择最合适的策略
- 3.对于每个阶段,依据贪心策略进行贪心选择,并求出最优解。
- 4.将各个子问题的解,合并为原问题的一个解。
Comments | NOTHING