贪心法

维基百科,自由的百科全书
跳转至: 导航搜索
一般人換零錢的時候也會應用到貪心算法。把$36換散︰$20 > $10 > $5 > $1

贪心法Greedy algorithm),又称貪心演算法,是一种在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择,从而希望导致结果是最好或最优的算法[1]比如在旅行推销员问题中,如果旅行员每次都选择最近的城市,那这就是一种贪心算法。

贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是局部最优解能决定全局最优解。简单地说,问题能够分解成子问题来解决,子问题的最优解能递推到最终问题的最优解。

贪心算法与动态规划的不同在于它每对每个子问题的解决方案都做出选择,不能回退。动态规划则会保存以前的运算结果,并根据以前的结果对当前进行选择,有回退功能。

贪心法可以解决一些最优化问题,如:求中的最小生成树、求哈夫曼编码……对于其他问题,贪心法一般不能得到我们所要求的答案。一旦一个问题可以通过贪心法来解决,那么贪心法一般是解决这个问题的最好办法。由于贪心法的高效性以及其所求得的答案比较接近最优结果,贪心法也可以用作辅助算法或者直接解决一些要求结果不特别精确的问题。

细节[编辑]

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

实现该算法的过程:
从问题的某一初始解出发;while 能朝给定总目标前进一步 do ,求出可行解的一个解元素;
最后,由所有解元素组合成问题的一个可行解。

种类[编辑]

應用[编辑]

  • 對於大部分的問題,貪心法通常都不能找出最佳解(不過也有例外),因為他們一般沒有測試所有可能的解。貪心法容易過早做決定,因而沒法達到最佳解。例如,所有對圖著色問題已知的貪心法,和所有對NP完全問題的貪心法, 都無法確保得到最佳解。然而,貪心法的好處在於容易設計和很多時能達到好的近似解
  • 贪心法在系统故障诊断策略生成乃至高校的排课系统中都可使用。[2][1]

举例[编辑]

http://blog.csdn.net/xywlpo/article/details/6439048

参见[编辑]

参考文献[编辑]

  1. ^ 1.0 1.1 曦辉, 邓. 浅谈贪心算法在排课系统中的应用. 电脑与电信 (广东省广州市: 广东省对外科技交流中心). 2011. ISSN 1008-6609 (简体中文). 
  2. ^ 贪心算法在系统故障诊断策略生成中的应用. 计算机系统应用 (北京市: 中国科学院软件研究所). 2011. ISSN 1003-3254 (简体中文).  |coauthors= requires |author= (帮助)

外部链接[编辑]