贪心算法（英語：greedy algorithm），又称贪婪算法，是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。[1]比如在旅行推销员问题中，如果旅行员每次都选择最近的城市，那这就是一种贪心算法。
一般人换零钱的時候也會應用到貪心算法。把$36換散︰$20 > $10 > $5 > $1贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是局部最优解能决定全局最优解。简单地说，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。
贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。
贪心法可以解决一些最优化问题，如：求图中的最小生成树、求哈夫曼编码……对于其他问题，贪心法一般不能得到我们所要求的答案。一旦一个问题可以通过贪心法来解决，那么贪心法一般是解决这个问题的最好办法。由于贪心法的高效性以及其所求得的答案比较接近最优结果，贪心法也可以用作辅助算法或者直接解决一些要求结果不特别精确的问题。在不同情況，選擇最優的解，可能會導致辛普森悖論（Simpson's Paradox），不一定出現最優的解。
貪心算法在数据科学領域被广泛應用，特別是金融工程。其中一個貪心算法例子就是Ensemble method。
细节 编辑
- 建立数学模型来描述问题。
- 把求解的问题分成若干个子问题。
- 对每一子问题求解，得到子问题的局部最优解。
- 把子问题的解局部最优解合成原来解问题的一个解。
实现该算法的过程：
从问题的某一初始解出发；while 能朝给定总目标前进一步 do，求出可行解的一个解元素；
最后，由所有解元素组合成问题的一个可行解。
應用 编辑
- 對於大部分的問題，貪心法通常都不能找出最佳解（不過也有例外），因為他們一般沒有測試所有可能的解。貪心法容易過早做決定，因而沒法達到最佳解。例如，所有對圖著色問題。
- 贪心法在系统故障诊断策略生成乃至高校的排课系统中都可使用。[2][1]
举例 编辑
参见 编辑
参考文献 编辑
- ^ 1.0 1.1 曦辉, 邓. 浅谈贪心算法在排课系统中的应用. 电脑与电信 (广东省广州市: 广东省对外科技交流中心). 2011. ISSN 1008-6609. （原始内容于2021-04-11） （中文（简体））.
- ^ 孙煜; 刘松风; 马力. 贪心算法在系统故障诊断策略生成中的应用. 计算机系统应用 (北京市: 中国科学院软件研究所). 2011. ISSN 1003-3254. （原始内容于2021-04-11） （中文（简体））.
外部链接 编辑
贪心算法, 此條目需要擴充, 2013年3月12日, 请協助改善这篇條目, 更進一步的信息可能會在討論頁或扩充请求中找到, 请在擴充條目後將此模板移除, 英語, greedy, algorithm, 又称贪婪算法, 是一种在每一步选择中都采取在当前状态下最好或最优, 即最有利, 的选择, 从而希望导致结果是最好或最优的算法, 比如在旅行推销员问题中, 如果旅行员每次都选择最近的城市, 那这就是一种, 一般人换零钱的時候也會應用到貪心算法, 36換散, 1在有最优子结构的问题中尤为有效, 最优子结构的意思是局部最优解. 此條目需要擴充 2013年3月12日 请協助改善这篇條目 更進一步的信息可能會在討論頁或扩充请求中找到 请在擴充條目後將此模板移除 贪心算法 英語 greedy algorithm 又称贪婪算法 是一种在每一步选择中都采取在当前状态下最好或最优 即最有利 的选择 从而希望导致结果是最好或最优的算法 1 比如在旅行推销员问题中 如果旅行员每次都选择最近的城市 那这就是一种贪心算法 一般人换零钱的時候也會應用到貪心算法 把 36換散 20 gt 10 gt 5 gt 1贪心算法在有最优子结构的问题中尤为有效 最优子结构的意思是局部最优解能决定全局最优解 简单地说 问题能够分解成子问题来解决 子问题的最优解能递推到最终问题的最优解 贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择 不能回退 动态规划则会保存以前的运算结果 并根据以前的结果对当前进行选择 有回退功能 贪心法可以解决一些最优化问题 如 求图中的最小生成树 求哈夫曼编码 对于其他问题 贪心法一般不能得到我们所要求的答案 一旦一个问题可以通过贪心法来解决 那么贪心法一般是解决这个问题的最好办法 由于贪心法的高效性以及其所求得的答案比较接近最优结果 贪心法也可以用作辅助算法或者直接解决一些要求结果不特别精确的问题 在不同情況 選擇最優的解 可能會導致辛普森悖論 Simpson s Paradox 不一定出現最優的解 貪心算法在数据科学領域被广泛應用 特別是金融工程 其中一個貪心算法例子就是Ensemble method 目录 1 细节 2 應用 3 举例 4 参见 5 参考文献 6 外部链接细节 编辑建立数学模型来描述问题 把求解的问题分成若干个子问题 对每一子问题求解 得到子问题的局部最优解 把子问题的解局部最优解合成原来解问题的一个解 实现该算法的过程 从问题的某一初始解出发 while 能朝给定总目标前进一步 do 求出可行解的一个解元素 最后 由所有解元素组合成问题的一个可行解 應用 编辑對於大部分的問題 貪心法通常都不能找出最佳解 不過也有例外 因為他們一般沒有測試所有可能的解 貪心法容易過早做決定 因而沒法達到最佳解 例如 所有對圖著色問題 贪心法在系统故障诊断策略生成乃至高校的排课系统中都可使用 2 1 举例 编辑最小生成樹的算法如Prim算法 Kruskal算法均为贪心算法 其中Prim算法是对图上的节点贪心 而Kruskal算法是对图上的边贪心 参见 编辑动态规划 最长公共子序列 Floyd Warshall算法 Viterbi算法参考文献 编辑 1 0 1 1 曦辉 邓 浅谈贪心算法在排课系统中的应用 电脑与电信 广东省广州市 广东省对外科技交流中心 2011 ISSN 1008 6609 原始内容存档于2021 04 11 中文 简体 孙煜 刘松风 马力 贪心算法在系统故障诊断策略生成中的应用 计算机系统应用 北京市 中国科学院软件研究所 2011 ISSN 1003 3254 原始内容存档于2021 04 11 中文 简体 外部链接 编辑 取自 https zh wikipedia org w index php title 贪心算法 amp oldid 74328003, 维基百科，wiki，书籍，书籍，图书馆，
文章
，阅读，下载，免费，免费下载，mp3，视频，mp4，3gp， jpg，jpeg，gif，png，图片，音乐，歌曲，电影，书籍，游戏，游戏。