贪心算法思想_贪心算法的基本要素

贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，

它所做出的仅是在某种意义上的局部最优解。用局部解构造全局解，即从问题的某一个初始解逐步逼近给定的

目标，以尽可能快的求得更好的解。当某个算法中的某一步不能再继续前进时，算法停止。

利用贪心算法解决问题时需要解决以下两个问题：

（1）该问题是否适合贪心策略求解。

（2）如何选择贪心标准，以得到问题的最优/较优解。

贪心算法存在如下问题：

（1）不能保证解释最佳的。因为贪心算法总是从局部出发，并没有从整体考虑。

（2）贪心算法一般用来解决求最大或最小解。

（3）贪心算法只能确定某些问题的可行性范围。

1.  贪心算法的基本要素

（1）贪心选择性质

所谓的贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。

对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所做的贪心选择最终导致问题的整体

最优解。首先考察问题的一个整体最优解，并证明可修改这个最优解，使其以贪心选择开始。做了贪心选择

后，原问题简化为规模更小的类似子问题。然后，用数学归纳法证明，通过每一步做贪心选择，最终可得到

问题的整体最优解。其中，证明贪心选择后的问题简化为规模更小的类似子问题的关键在于利用该问题的最

优子结构性质。

        （2）最优子结构性质

         当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。运用贪心策略在每一次

转化时都取得了最优解。

        

        2.  贪心算法的实现过程

        贪心算法的核心问题是选择能产生问题最优解的最优度量标准，即贪心策略。

所谓贪心策略是指从问题的初始状态出发，通过若干次的贪心选择而得出最优值的一种解题方法，其具体的实现

过程如下：

        （1）应用同一规则，将原问题变为一个相似的但规模更小的子问题。

        （2）从问题的某一初始解出发：

            while （能朝给定目标前进一步）

                    求出可行解的一个解元素

        （3）由所有解元素组合成问题的一个可行解