集智百科 - 复杂系统|人工智能|复杂科学|复杂网络|自组织 - 用户贡献 [zh-cn]

贪心算法

2022-05-23T06:06:03Z

Tanpopo：

此词条暂由彩云小译翻译，翻译字数共1208，Tanpopo正在进行审校，带来阅读不便，请见谅。

[[Image:Greedy algorithm 36 cents.svg|thumb|280px|right| 利用贪心算法确定在找零时要提供的最小硬币数量。图中大多数人会采用的步骤，通过模拟贪心算法来只用面值为1、5、10、20 美分的硬币来表示 36 美分。价值最高且金额小于所欠的剩余零钱的硬币，是局部最优的。（一般来说，找零问题需要动态规划来找到最优解；然而，大多数货币系统，包括欧元系统和美元系统，都是贪心策略可以找到最优解的特殊情况。）|link=Special:FilePath/Greedy_algorithm_36_cents.svg]]

'''贪心算法'''是一种在每个阶段中都进行局部最优选择来进行问题求解的启发式算法。在许多问题中，贪心策略通常不会产生最优解，但贪心启发式算法可以产生局部最优解，即在合理的时间内得到全局最优解的近似。

例如，[[旅行商问题]]（计算复杂度很高）的贪心策略是以下启发式算法: “旅程的每一步都去最近的没去过的城市。”这种启发式方法并不打算找到最优解，但是它在合理的步骤数后终止，而通常为这种复杂问题找到最优解所需要的步骤数通常多到不合理。在最优化中，贪心算法可最优求解具有[[拟阵]]性质的组合问题，并给出具有子模结构的优化问题的常数因子近似。
==算法细节==

一般来说，贪心算法有五个组成部分:

#候选集，用于从中创建解
#选择函数，用于选择要添加到解中的最佳候选
#可行性函数，用于确定一个候选是否有助于解决问题
#目标函数，用于为解或部分解赋值
#解函数，当找到一个完整的解时，它会指示出来
贪心算法对一些数学问题上生成的解较好，但在另一些上的解不好。大多数可以使用贪心算法问题都有如下两个性质:

=== 贪心选择性质===
贪心选择性质指，可以首先做出目前最优选择，然后再解决随后出现的子问题。贪心算法所做的选择可能取决于过去所做的所有选择，但不考虑未来的选择，也不会考虑子问题的所有解。它通过迭代来依次做出贪心选择，将每个给定的问题缩小为一个更小的问题。换句话说，贪心算法不会重新考虑已做出的选择，这是贪心算法与动态规划的主要区别。[[动态规划]]是穷举式的，并且保证能够找到解。在每个阶段之后，动态规划基于之前的所有决策做出下一步决策，并可能重新考虑之前求解的算法路径。

===最优子结构===
“如果问题的最优解包含子问题的最优解，则问题具有[[最优子结构]]。”
=== 失效情况 ===
{{multiple image
| align =
| direction = vertical
| width = 300
| header = 贪心算法可能无法获得最优解的例子。
| image1 = Greedy Glouton.svg
| alt1 =
| caption1 = 从 a 开始，一个贪心算法试图通过跟随最大斜率来寻找最大值，会在“ m”处找到局部最大值，不会注意到“ m”处的全局最大值。
| image2 = Greedy-search-path-example.gif
| alt2 =
| caption2 =

为了达到最大和的目标，在每一步，贪心算法将选择看起来是最优的即时选择，所以在第二步它将选择12而不是3，并且不会达到包含99的最优解。
}}

对于许多其他问题，贪心算法不能产生最优解，甚至可能产生唯一的最坏可能解。比如上面提到的旅行商问题，对于任意给定的城市数量，都存在一个城市之间的距离分配，使得最近邻启发式算法产生唯一的最坏可能的旅行方案。其他可能使贪心算法失效的例子，请参阅[[地平线效应]]。
== 分类==

{{More citations needed section|date=June 2018}}

贪心算法可以被描述为“目光短浅” ，也可以被描述为“不可恢复”。它们只适用于具有“最优子结构”的问题。尽管如此，对于许多简单的问题，最适合的算法依然是贪心算法。但是，值得注意的是，贪心算法可以用于在搜索或分支定界算法中对选项进行优先级排序。贪心算法有以下几种变体:
*纯贪心算法
*正交贪心算法

*松弛贪心算法
== 理论==

贪心算法在[[组合优化]]和[[理论计算机科学]]领域有着悠久的研究历史。众所周知，贪心启发法会在许多问题上产生次优的结果，因此自然会提出以下问题:
*怎样的问题可以保证贪心算法能产生最优解？
*怎样的问题可以保证贪心算法能产生近似最优解？
*怎样的问题可以保证贪心算法无法产生最优解？

大量的文献都在回答上述问题，例如拟阵等回答一般类问题，以及集合覆盖等回答具体问题。
===拟阵===

{{Main|拟阵}}

拟阵是一种将线性无关的概念从向量空间推广到任意集合的数学结构。如果一个最优化问题具有拟阵的结构，那么这个问题可由贪心算法得到最优解。
===子模函数===

{{Main|Submodular set function#Optimization problems}}

定义在一个集合<math>\Omega</math>的子集上的一个函数<math>f</math>，如果对于每个 <math>S, T \subseteq \Omega</math>，有<math>f(S)+f(T)\geq f(S\cup T)+f(S\cap T)</math>，则称这个函数为子模函数。

假设我们想要找到一个使<math>f</math>最大化的集合<math>S</math>。贪心算法通过在每一步中逐步添加元素，使得每一步的<math>f</math>的增量最大，从而建立一个集合<math>S</math>，产生一个至少<math>(1 - 1/e) \max_{X \subseteq \Omega} f(X)</math>的集合作为输出。也就是说，在常数因子<math>(1 - 1/e) \approx 0.63</math>下，贪心算法的表现和最优解一样好。

可以证明，当对输出施加额外的约束（如基数约束）时，类似的保证依然成立，尽管贪心算法通常需要一些细微的变化。详见[3]。
===其他有保证的问题===

对其他问题，贪心算法提供了强保证，但不是最优解。这些问题包括：
*[[集合覆盖]]

*[[斯坦纳树]]问题

*[[负载均衡]]

*[[独立集]]
其中许多问题都有匹配的下限；即，贪心算法在最坏情况下的性能并不优于保证。
==应用 ==

{{Expand section|date=June 2018}}

贪心算法通常（但并不总是）无法找到全局最优解，这是因为这些算法通常不会遍历所有数据。贪心算法可能过早地做出某些选择，妨碍了之后找到全局最优解。例如，针对所有已知的[[图着色]]问题和所有其他[[NP完全|NP 完全]]问题，[[贪心着色]]算法都不能保证找到最优解。尽管如此，贪心算法还是很有用的，因为它们很快就能想出来，而且常常能给出最佳的近似值。

如果一个贪心算法被证明可以为给定的问题类产生全局最优解，它通常成为选择的方法，因为它比动态规划等其他优化方法更快。这种贪心算法的例子有 [[Kruskal 算法]]和 [[Prim 算法]]用于寻找[[最小生成树]]，以及寻找最优 [[Huffman 树]]的算法。

贪心算法也出现在网络[[路由]]中。使用贪心路由，消息被转发到邻近的节点，这是“最接近”的目标。一个节点的位置(因此是“贴近度”)的概念可以由它的物理位置来决定，就像临时网络使用的[[地理路由]]一样。位置也可能是一个完全人为的构造，就像[[小世界路由]]和[[分散式哈希表]]路由。
==举例==

* [[活动选择问题]]是这类问题的特征，其目标是选择彼此不冲突的最大活动数。
* 在[[麦金塔电脑]]游戏''[[Crystal Quest]]''中，目标是收集水晶，其方式类似于[[旅行商问题]]。游戏有一个演示模式，游戏使用贪心算法去每一个水晶。游戏AI（[[人工智能]]）不考虑障碍物，因此演示模式通常会很快结束。
* [[匹配追求]]是应用于信号近似的贪心算法的一个例子。
* 贪心算法为[[马尔法蒂问题]]找到了最优解，即在给定的三角形内找到三个不相交的圆，使圆的总面积最大化;据推测，同样的贪心算法对于任何数量的圆圈都是最优的。
* 贪心算法用于在[[霍夫曼编码]]期间构造霍夫曼树，以找到最优解。
* 在[[决策树学习]]中，通常使用贪心算法，但是不能保证它们能找到最优解。
** 一种流行的此类算法是用于决策树构造的[[ID3算法]]。
* [[Dijkstra算法]]和相关的[[A*搜索算法]]是用于[[图搜索]]和[[最短路径查找]]的可验证的最优贪心算法。
** A* 搜索是有条件最优的，需要一种不会高估路径成本的“[[可接受启发式算法]]”。
* [[Kruskal算法]]和[[Prim算法]]是用于构造给定连通图的[[最小生成树]]的贪心算法。他们总能找到一个最佳解决方案，这在一般情况下可能不是唯一的。

==参见==

{{Portal|Mathematics}}

*[[Epsilon-贪婪策略|Epsilon-贪心策略]]

*[[埃及分数的贪婪算法|埃及分数的贪心算法]]

*[[贪婪源|贪心源]]

*[[拟阵]]

*[[最佳优先搜索]]
==参考==

*''[[Introduction to Algorithms]]'' (Cormen, Leiserson, Rivest, and Stein) 2001, Chapter 16 "Greedy Algorithms".

*{{cite journal|doi=10.1016/S0166-218X(01)00195-0|title=Traveling salesman should not be greedy: Domination analysis of greedy-type heuristics for the TSP|journal=Discrete Applied Mathematics|volume=117|issue=1–3|pages=81–86|year=2002|last1=Gutin|first1=Gregory|last2=Yeo|first2=Anders|last3=Zverovich|first3=Alexey}}

*{{cite journal|doi=10.1016/j.disopt.2004.03.007|title=When the greedy algorithm fails|journal=Discrete Optimization|volume=1|issue=2|pages=121–127|year=2004|last1=Bang-Jensen|first1=Jørgen|last2=Gutin|first2=Gregory|last3=Yeo|first3=Anders}}

*{{cite journal|doi=10.1016/j.disopt.2006.03.001|title=Greedy-type resistance of combinatorial problems|journal=Discrete Optimization|volume=3|issue=4|pages=288–298|year=2006|last1=Bendall|first1=Gareth|last2=Margot|first2=François}}

*U. Feige. [https://www.cs.duke.edu/courses/cps296.2/spring07/papers/p634-feige.pdf A threshold of ln n for approximating set cover]. Journal of the ACM, 45(4):634–652, 1998.

*G. Nemhauser, L.A. Wolsey, and M.L. Fisher. "[https://www.researchgate.net/profile/George_Nemhauser/publication/242914003_An_Analysis_of_Approximations_for_Maximizing_Submodular_Set_Functions-I/links/53d696490cf228d363ea6bdf.pdf An analysis of approximations for maximizing submodular set functions—I]." Mathematical Programming 14.1 (1978): 265-294.

*N. Buchbinder, et al. "[http://theory.epfl.ch/moranfe/Publications/SODA2014.pdf Submodular maximization with cardinality constraints]." Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 2014.

*A. Krause and D. Golovin. "[https://www.cs.cmu.edu/afs/.cs.cmu.edu/Web/People/dgolovin/papers/submodular_survey12.pdf Submodular function maximization]." (2014): 71-104.

==外部链接==

{{commons category|Greedy algorithms}}

*{{springer|title=Greedy algorithm|id=p/g110210}}

*[http://www.oreillynet.com/onlamp/blog/2008/04/python_greedy_coin_changer_alg.html Python greedy coin] example by Noah Gift.

{{optimization algorithms|combinatorial|state=expanded}}{{Template:Data structures and algorithms}}

[[Category:Optimization algorithms and methods]]

Category:Optimization algorithms and methods

类别: 优化算法和方法

[[Category:Combinatorial algorithms]]

Category:Combinatorial algorithms

类别: 组合算法

[[Category:Matroid theory]]

Category:Matroid theory

范畴: 拟阵理论

[[Category:Exchange algorithms]]

Category:Exchange algorithms

类别: Exchange 算法

<noinclude>

<small>This page was moved from [[wikipedia:en:Greedy algorithm]]. Its edit history can be viewed at [[贪心算法/edithistory]]</small></noinclude>

[[Category:待整理页面]]

用户:Tanpopo

2022-05-02T16:58:50Z

Tanpopo：

== 基本信息 ==

* 昵称：Tanpopo（蒲公英、婆婆丁、大佐）
* 性别：男
* 职位：2021级直博生
* MBTI：INTP（正努力让自己多点Fe，多点Te）
* 感兴趣的研究方向：
** 工业物联网路由与调度
** 网络科学
** 自组织、涌现
* 元爱好：学各种各样的知识，并建立一定的体系
* 次生爱好：
** 玩乐器、听音乐（了解了一些和声学、曲式学、配器法等）
** 做饭、吃好吃的（尤其是旅游到各地去吃，探索各种各样的新奇美食）
** 语言文字（初步了解了语言学、语音学、语法树、语言谱系、中古汉语拟音等）
** 学各种语言（母语东北话，方言可以说洋泾浜的苏州话、天津话、西安话、南京话等，非官话方言大致听懂台湾闽南语、广州粤语，日语N3水平，韩语、芬兰语、德语仅入门）
** 心理学（乱七八糟看的，并不系统，但是弗洛伊德-荣格看的比较多）
** 哲学（主要看康德和海德格尔，挺难啃的）

== 最近的目标 ==

* 戒手机。手机真的太成瘾，一刷停不下来，而且戒手机竟然有一定的戒断反应。
* 找到自己的研究课题。

用户:Tanpopo

2022-05-02T16:56:48Z

Tanpopo：建立内容为“== 基本信息 == * 昵称：Tanpopo（蒲公英、婆婆丁、大佐） * 性别：男 * 故乡：黑龙江 * 职位：东南大学2021级直博生 * MBTI：IN…”的新页面

== 基本信息 ==

* 昵称：Tanpopo（蒲公英、婆婆丁、大佐）
* 性别：男
* 故乡：黑龙江
* 职位：东南大学2021级直博生
* MBTI：INTP（正努力让自己多点Fe，多点Te）
* 感兴趣的研究方向：
** 工业物联网路由与调度
** 网络科学
** 自组织、涌现
* 元爱好：学各种各样的知识，并建立一定的体系
* 次生爱好：
** 玩乐器、听音乐（了解了一些和声学、曲式学、配器法等）
** 做饭、吃好吃的（尤其是旅游到各地去吃，探索各种各样的新奇美食）
** 语言文字（初步了解了语言学、语音学、语法树、语言谱系、中古汉语拟音等）
** 学各种语言（母语东北话，方言可以说洋泾浜的苏州话、天津话、西安话、南京话等，非官话方言大致听懂台湾闽南语、广州粤语，日语N3水平，韩语、芬兰语、德语仅入门）
** 心理学（乱七八糟看的，并不系统，但是弗洛伊德-荣格看的比较多）
** 哲学（主要看康德和海德格尔，挺难啃的）

== 最近的目标 ==

* 戒手机。手机真的太成瘾，一刷停不下来，而且戒手机竟然有一定的戒断反应。
* 找到自己的研究课题。

贪心算法

2022-05-02T05:32:46Z

Tanpopo：

此词条暂由彩云小译翻译，翻译字数共1208，Tanpopo正在进行审校，带来阅读不便，请见谅。

[[Image:Greedy algorithm 36 cents.svg|thumb|280px|right| 利用贪心算法确定在找零时要提供的最小硬币数量。图中大多数人会采用的步骤，通过模拟贪心算法来只用面值为1、5、10、20 美分的硬币来表示 36 美分。价值最高且金额小于所欠的剩余零钱的硬币，是局部最优的。（一般来说，找零问题需要动态规划来找到最优解；然而，大多数货币系统，包括欧元系统和美元系统，都是贪心策略可以找到最优解的特殊情况。）|link=Special:FilePath/Greedy_algorithm_36_cents.svg]]

'''贪心算法'''是一种在每个阶段中都进行局部最优选择来进行问题求解的启发式算法。在许多问题中，贪心策略通常不会产生最优解，但贪心启发式算法可以产生局部最优解，即在合理的时间内得到全局最优解的近似。

例如，[[旅行商问题]]（计算复杂度很高）的贪心策略是以下启发式算法: “旅程的每一步都去最近的没去过的城市。”这种启发式方法并不打算找到最优解，但是它在合理的步骤数后终止，而通常为这种复杂问题找到最优解所需要的步骤数通常多到不合理。在最优化中，贪心算法可最优求解具有[[拟阵]]性质的组合问题，并给出具有子模结构的优化问题的常数因子近似。
==算法细节==

一般来说，贪心算法有五个组成部分:

#候选集，用于从中创建解
#选择函数，用于选择要添加到解中的最佳候选
#可行性函数，用于确定一个候选是否有助于解决问题
#目标函数，用于为解或部分解赋值
#解函数，当找到一个完整的解时，它会指示出来

#A candidate set, from which a solution is created
#A selection function, which chooses the best candidate to be added to the solution
#A feasibility function, that is used to determine if a candidate can be used to contribute to a solution
#An objective function, which assigns a value to a solution, or a partial solution, and
#A solution function, which will indicate when we have discovered a complete solution

贪心算法对一些数学问题上生成的解较好，但在另一些上的解不好。大多数可以使用贪心算法问题都有如下两个性质:

=== 贪心选择性质===
贪心选择性质指，可以首先做出目前最优选择，然后再解决随后出现的子问题。贪心算法所做的选择可能取决于过去所做的所有选择，但不考虑未来的选择，也不会考虑子问题的所有解。它通过迭代来依次做出贪心选择，将每个给定的问题缩小为一个更小的问题。换句话说，贪心算法不会重新考虑已做出的选择，这是贪心算法与动态规划的主要区别。[[动态规划]]是穷举式的，并且保证能够找到解。在每个阶段之后，动态规划基于之前的所有决策做出下一步决策，并可能重新考虑之前求解的算法路径。

===最优子结构===
“如果问题的最优解包含子问题的最优解，则问题具有[[最优子结构]]。”
=== 失效情况 ===
{{multiple image
| align =
| direction = vertical
| width = 300
| header = 贪心算法可能无法获得最优解的例子。
| image1 = Greedy Glouton.svg
| alt1 =
| caption1 = 从 a 开始，一个贪心算法试图通过跟随最大斜率来寻找最大值，会在“ m”处找到局部最大值，不会注意到“ m”处的全局最大值。
| image2 = Greedy-search-path-example.gif
| alt2 =
| caption2 =

为了达到最大和的目标，在每一步，贪心算法将选择看起来是最优的即时选择，所以在第二步它将选择12而不是3，并且不会达到包含99的最优解。
}}

对于许多其他问题，贪心算法不能产生最优解，甚至可能产生唯一的最坏可能解。比如上面提到的旅行商问题，对于任意给定的城市数量，都存在一个城市之间的距离分配，使得最近邻启发式算法产生唯一的最坏可能的旅行方案。其他可能使贪心算法失效的例子，请参阅[[地平线效应]]。

== 分类==

{{More citations needed section|date=June 2018}}

贪心算法可以被描述为“目光短浅” ，也可以被描述为“不可恢复”。它们只适用于具有“最优子结构”的问题。尽管如此，对于许多简单的问题，最适合的算法依然是贪心算法。但是，值得注意的是，贪心算法可以用于在搜索或分支定界算法中对选项进行优先级排序。贪心算法有以下几种变体:
*纯贪心算法
*正交贪心算法

*松弛贪心算法
== 理论==

贪心算法在[[组合优化]]和[[理论计算机科学]]领域有着悠久的研究历史。众所周知，贪心启发法会在许多问题上产生次优的结果，因此自然会提出以下问题:
*怎样的问题可以保证贪心算法能产生最优解？
*怎样的问题可以保证贪心算法能产生近似最优解？
*怎样的问题可以保证贪心算法无法产生最优解？

大量的文献都在回答上述问题，例如拟阵等回答一般类问题，以及集合覆盖等回答具体问题。
===拟阵===

{{Main|Matroid}}

拟阵是一种将线性无关的概念从向量空间推广到任意集合的数学结构。如果一个最优化问题具有拟阵的结构，那么这个问题可由贪心算法得到最优解。
===子模函数===

{{Main|Submodular set function#Optimization problems}}

定义在一个集合<math>\Omega</math>的子集上的一个函数<math>f</math>，如果对于每个 <math>S, T \subseteq \Omega</math>，有<math>f(S)+f(T)\geq f(S\cup T)+f(S\cap T)</math>，则称这个函数为子模函数。

假设我们想要找到一个使<math>f</math>最大化的集合<math>S</math>。贪心算法通过在每一步中逐步添加元素，使得每一步的<math>f</math>的增量最大，从而建立一个集合<math>S</math>，产生一个至少<math>(1 - 1/e) \max_{X \subseteq \Omega} f(X)</math>的集合作为输出。也就是说，在常数因子<math>(1 - 1/e) \approx 0.63</math>下，贪心算法的表现和最优解一样好。

可以证明，当对输出施加额外的约束（如基数约束）时，类似的保证依然成立，尽管贪心算法通常需要一些细微的变化。详见[3]。
===其他有保证的问题===

Other problems for which the greedy algorithm gives a strong guarantee, but not an optimal solution, include

Other problems for which the greedy algorithm gives a strong guarantee, but not an optimal solution, include

对其他问题，贪心算法提供了强保证，但不是最优解。这些问题包括：
*[[集合覆盖]]

*[[斯坦纳树]]问题

*[[负载均衡]]

*[[独立集]]
其中许多问题都有匹配的下限；即，贪心算法在最坏情况下的性能并不优于保证。

==应用 ==

{{Expand section|date=June 2018}}

Greedy algorithms mostly (but not always) fail to find the globally optimal solution because they usually do not operate exhaustively on all the data. They can make commitments to certain choices too early which prevent them from finding the best overall solution later. For example, all known [[greedy coloring]] algorithms for the [[graph coloring problem]] and all other [[NP-complete]] problems do not consistently find optimum solutions. Nevertheless, they are useful because they are quick to think up and often give good approximations to the optimum.

Greedy algorithms mostly (but not always) fail to find the globally optimal solution because they usually do not operate exhaustively on all the data. They can make commitments to certain choices too early which prevent them from finding the best overall solution later. For example, all known greedy coloring algorithms for the graph coloring problem and all other NP-complete problems do not consistently find optimum solutions. Nevertheless, they are useful because they are quick to think up and often give good approximations to the optimum.

贪心算法通常（但并不总是）无法找到全局最优解，这是因为这些算法通常不会对所有数据进行详尽的操作。贪心算法可能过早地做出某些选择，这会妨碍这些算法之后找到最佳的整体解决方案。例如，所有已知的[[图着色]]问题问题和所有其他 [[NP完全|NP 完全]]问题的[[贪心着色]]算法都不能始终找到最优解。尽管如此，它们还是很有用的，因为它们很快就能想出来，而且常常能给出最佳的近似值。

If a greedy algorithm can be proven to yield the global optimum for a given problem class, it typically becomes the method of choice because it is faster than other optimization methods like [[dynamic programming]]. Examples of such greedy algorithms are [[Kruskal's algorithm]] and [[Prim's algorithm]] for finding [[minimum spanning tree]]s, and the algorithm for finding optimum [[Huffman tree]]s.

If a greedy algorithm can be proven to yield the global optimum for a given problem class, it typically becomes the method of choice because it is faster than other optimization methods like dynamic programming. Examples of such greedy algorithms are Kruskal's algorithm and Prim's algorithm for finding minimum spanning trees, and the algorithm for finding optimum Huffman trees.

如果一个贪心算法被证明可以为给定的问题类产生全局最优解，它通常成为选择的方法，因为它比动态规划等其他优化方法更快。这种贪心算法的例子有 [[Kruskal 算法]]和 [[Prim 算法]]用于寻找[[最小生成树]]，以及寻找最优 [[Huffman 树]]的算法。

Greedy algorithms appear in network [[routing]] as well. Using greedy routing, a message is forwarded to the neighboring node which is "closest" to the destination. The notion of a node's location (and hence "closeness") may be determined by its physical location, as in [[geographic routing]] used by [[ad hoc network]]s. Location may also be an entirely artificial construct as in [[small world routing]] and [[distributed hash table]].

Greedy algorithms appear in network routing as well. Using greedy routing, a message is forwarded to the neighboring node which is "closest" to the destination. The notion of a node's location (and hence "closeness") may be determined by its physical location, as in geographic routing used by ad hoc networks. Location may also be an entirely artificial construct as in small world routing and distributed hash table.

贪心算法也出现在网络路由中。使用贪心路由，消息被转发到邻近的节点，这是“最接近”的目标。一个节点的位置(因此是“贴近度”)的概念可以由它的物理位置来决定，就像临时网络使用的地理路由一样。位置也可能是一个完全人为的构造，就像小世界路由和分散式杂凑表路由。

==Examples==

*The [[activity selection problem]] is characteristic to this class of problems, where the goal is to pick the maximum number of activities that do not clash with each other.

*In the [[Macintosh computer]] game ''[[Crystal Quest]]'' the objective is to collect crystals, in a fashion similar to the [[travelling salesman problem]]. The game has a demo mode, where the game uses a greedy algorithm to go to every crystal. The [[artificial intelligence]] does not account for obstacles, so the demo mode often ends quickly.

*The [[matching pursuit]] is an example of greedy algorithm applied on signal approximation.

*A greedy algorithm finds the optimal solution to [[Malfatti circles|Malfatti's problem]] of finding three disjoint circles within a given triangle that maximize the total area of the circles; it is conjectured that the same greedy algorithm is optimal for any number of circles.

*A greedy algorithm is used to construct a Huffman tree during [[Huffman coding]] where it finds an optimal solution.

*In [[decision tree learning]], greedy algorithms are commonly used, however they are not guaranteed to find the optimal solution.

**One popular such algorithm is the [[ID3 algorithm]] for decision tree construction.

*[[Dijkstra's algorithm]] and the related [[A* search algorithm]] are verifiably optimal greedy algorithms for [[graph search]] and [[Shortest path problem|shortest path finding]].

**A* search is conditionally optimal, requiring an "[[admissible heuristic]]" that will not overestimate path costs.

*[[Kruskal's algorithm]] and [[Prim's algorithm]] are greedy algorithms for constructing [[minimum spanning tree]]s of a given [[connected graph]]. They always find an optimal solution, which may not be unique in general.

==See also==

{{Portal|Mathematics}}

*[[Multi-armed bandit#Semi-uniform strategies|Epsilon-greedy strategy]]

*[[Greedy algorithm for Egyptian fractions]]

*[[Greedy source]]

*[[Matroid]]

*[[Best-first search]]

==Notes==

<references />

==References==

*''[[Introduction to Algorithms]]'' (Cormen, Leiserson, Rivest, and Stein) 2001, Chapter 16 "Greedy Algorithms".

*{{cite journal|doi=10.1016/S0166-218X(01)00195-0|title=Traveling salesman should not be greedy: Domination analysis of greedy-type heuristics for the TSP|journal=Discrete Applied Mathematics|volume=117|issue=1–3|pages=81–86|year=2002|last1=Gutin|first1=Gregory|last2=Yeo|first2=Anders|last3=Zverovich|first3=Alexey}}

*{{cite journal|doi=10.1016/j.disopt.2004.03.007|title=When the greedy algorithm fails|journal=Discrete Optimization|volume=1|issue=2|pages=121–127|year=2004|last1=Bang-Jensen|first1=Jørgen|last2=Gutin|first2=Gregory|last3=Yeo|first3=Anders}}

*{{cite journal|doi=10.1016/j.disopt.2006.03.001|title=Greedy-type resistance of combinatorial problems|journal=Discrete Optimization|volume=3|issue=4|pages=288–298|year=2006|last1=Bendall|first1=Gareth|last2=Margot|first2=François}}

*U. Feige. [https://www.cs.duke.edu/courses/cps296.2/spring07/papers/p634-feige.pdf A threshold of ln n for approximating set cover]. Journal of the ACM, 45(4):634–652, 1998.

*G. Nemhauser, L.A. Wolsey, and M.L. Fisher. "[https://www.researchgate.net/profile/George_Nemhauser/publication/242914003_An_Analysis_of_Approximations_for_Maximizing_Submodular_Set_Functions-I/links/53d696490cf228d363ea6bdf.pdf An analysis of approximations for maximizing submodular set functions—I]." Mathematical Programming 14.1 (1978): 265-294.

*N. Buchbinder, et al. "[http://theory.epfl.ch/moranfe/Publications/SODA2014.pdf Submodular maximization with cardinality constraints]." Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 2014.

*A. Krause and D. Golovin. "[https://www.cs.cmu.edu/afs/.cs.cmu.edu/Web/People/dgolovin/papers/submodular_survey12.pdf Submodular function maximization]." (2014): 71-104.

==External links==

{{commons category|Greedy algorithms}}

*{{springer|title=Greedy algorithm|id=p/g110210}}

*[http://www.oreillynet.com/onlamp/blog/2008/04/python_greedy_coin_changer_alg.html Python greedy coin] example by Noah Gift.

{{optimization algorithms|combinatorial|state=expanded}}{{Template:Data structures and algorithms}}

[[Category:Optimization algorithms and methods]]

Category:Optimization algorithms and methods

类别: 优化算法和方法

[[Category:Combinatorial algorithms]]

Category:Combinatorial algorithms

类别: 组合算法

[[Category:Matroid theory]]

Category:Matroid theory

范畴: 拟阵理论

[[Category:Exchange algorithms]]

Category:Exchange algorithms

类别: Exchange 算法

<noinclude>

<small>This page was moved from [[wikipedia:en:Greedy algorithm]]. Its edit history can be viewed at [[贪心算法/edithistory]]</small></noinclude>

[[Category:待整理页面]]