贪心算法

一旦一个问题可以通过贪心法来解决, 那么贪心法一般是解决这个问题的最好办法

概念

贪心算法(英语: greedy algorithm), 又称贪婪算法,
是一种在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择,
从而希望导致结果是最好或最优的算法。

适用情况

  • 贪心算法在有最优子结构的问题中尤为有效。
    最优子结构的意思是局部最优解能决定全局最优解

简单地说, 问题能够分解成子问题来解决, 子问题的最优解能递推到最终问题的最优解

  • 由于贪心法的高效性以及其所求得的答案比较接近最优结果,贪心法也可以用作辅助算法或者直接解决一些要求结果不特别精确的问题。
  • 贪心法在系统故障诊断策略生成乃至高校的排课系统中都可使用。

缺陷

  • 对于大部分的问题,贪心法通常都不能找出最佳解(不过也有例外),因为他们一般没有测试所有可能的解。贪心法容易过早做决定,因而没法达到最佳解。例如,所有对图着色问题。

举例

  1. 旅行推销员问题
    如果旅行推销员每次都选择最近的城市, 那这就是一种贪心算法
  2. 兑换零钱
    一般人换零钱的时候也会应用到贪心算法。把$36换散︰$20 > $10 > $5 > $1

应用步骤

  1. 创建数学模型来描述问题
  2. 把求解的问题分成若干个子问题
  3. 对每一子问题求解, 得到子问题的局部最优解
  4. 把子问题的局部最优解合并成原来问题的一个解

实现该算法的过程

  1. 从问题的某一初始解出发;while 能朝给定总目标前进一步 do,求出可行解的一个解元素;
  2. 最后,由所有解元素组合成问题的一个可行解。

leetcode 122 (简单)
给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。
注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

go语言程序示例如下

func maxProfit(prices []int) int {
    res := 0
    for i := 1; i < len(prices); i++ {
        /***核心代码区域***/
        if prices[i] > prices[i-1] {
            res += prices[i] - prices[i-1]
        }
        /***先求解每一子问题的局部最优解, 然后累加起来得到原来问题的最优解***/
    }

    return res
}

证明 “贪心算法” 的有效性

我们借助“差分”这个概念,可以证明“贪心算法”的有效性。贪心算法就是选择那些所有差分(严格)大于 0 的数,把它们相加即可。
使用反证法:假设“贪心算法”得到的解并不是最优解,即我们还能够找到一个可行解比“贪心算法”得到的利润还多。差分数组中除了差分为正数的项以外,还有就是差分为 0 的项与差分为负数的项。“贪心算法”是所有差分为正数的项的和。

  1. 如果可行解在“贪心算法”的基础上,选择了差分为 0 的项,得到的结果与“贪心算法”得到的结果一样,因此加上差分为 0 的项不会比“贪心算法”得到的结果更好;
  2. 如果可行解在“贪心算法”的基础上,选择了差分为负数的项,加上一个负数得到的结果一定比“贪心算法”得到的结果要少,加上差分为负数的项,一定比“贪心算法”得到的结果更少;
  3. 如果可行解在“贪心算法”的基础上,去掉了任何一个差分为正数的项,同上,得到的结果一定比“贪心算法”得到的结果要小,因此,“贪心算法”的所有组成项不能删去任何一个。
  4. 综上,除了“贪心算法”以外,找不到一个更优的解法,因此“贪心算法”就是最优解。(证完)

该证法作者:liweiwei1419
链接:https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/solution/tan-xin-suan-fa-by-liweiwei1419-2/
来源:力扣(LeetCode)。

Last modification:January 5th, 2020 at 06:23 pm
给肥宅一点零花钱买可乐叭 (゜-゜)つロ