4
个编辑
更改
跳到导航
跳到搜索
小第1行：
第1行： − 此词条暂由彩云小译翻译，翻译字数共1208，未经人工整理和审校，带来阅读不便，请见谅。+ − + − Greedy algorithms determine minimum number of coins to give while making change. These are the steps a human would take to emulate a greedy algorithm to represent 36 cents using only coins with values {1, 5, 10, 20}. The coin of the highest value, less than the remaining change owed, is the local optimum. (In general the [[change-making problem requires dynamic programming to find an optimal solution; however, most currency systems, including the Euro and US Dollar, are special cases where the greedy strategy does find an optimal solution.)]]+ − 贪婪算法确定最低数量的硬币，以给予同时作出改变。这些是人类模仿贪婪算法的步骤，只使用值为{1,5,10,20}的硬币来表示36美分。价值最高的硬币，小于其余的变化欠款，是局部最优。(一般来说，[变革问题需要动态规划来找到最优解; 然而，大多数货币系统，包括欧元和美元，是贪婪策略找到最优解的特殊情况。]]+ + + + + + + + − + + + + + − A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage. In many problems, a greedy strategy does not usually produce an optimal solution, but nonetheless a greedy heuristic may yield locally optimal solutions that approximate a globally optimal solution in a reasonable amount of time. − 贪婪算法是遵循在每个阶段进行局部最优选择的问题求解启发式的任何算法。在许多问题中，贪婪策略通常不会产生最优解，但尽管如此，贪婪启发式算法可能产生局部最优解，在合理的时间内逼近全局最优解。+ + + − + − For example, a greedy strategy for the [[travelling salesman problem]] (which is of a high computational complexity) is the following heuristic: "At each step of the journey, visit the nearest unvisited city." This heuristic does not intend to find a best solution, but it terminates in a reasonable number of steps; finding an optimal solution to such a complex problem typically requires unreasonably many steps. In mathematical optimization, greedy algorithms optimally solve combinatorial problems having the properties of [[matroid]]s, and give constant-factor approximations to optimization problems with submodular structure.+ − + − For example, a greedy strategy for the travelling salesman problem (which is of a high computational complexity) is the following heuristic: "At each step of the journey, visit the nearest unvisited city." This heuristic does not intend to find a best solution, but it terminates in a reasonable number of steps; finding an optimal solution to such a complex problem typically requires unreasonably many steps. In mathematical optimization, greedy algorithms optimally solve combinatorial problems having the properties of matroids, and give constant-factor approximations to optimization problems with submodular structure. − − 例如，旅行推销员问题的贪婪策略(具有很高的计算复杂性)是以下启发式: “在旅程的每一步，访问最近的未访问的城市。”这种启发式方法并不打算找到最佳解决方案，但是它在合理的步骤数中终止; 为这样一个复杂问题找到最佳解决方案通常需要不合理的许多步骤。在最优化中，贪婪算法最优化地解决具有拟阵性质的组合问题，并给出具有子模结构的优化问题的常数因子近似。 − − − − − − In general, greedy algorithms have five components: − − In general, greedy algorithms have five components: − − 一般来说，贪婪算法有五个组成部分: − − # A candidate set, from which a solution is created − − A candidate set, from which a solution is created − − 用于创建解决方案的候选集 − − # A selection function, which chooses the best candidate to be added to the solution − − 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 − − 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 − − 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 − − A solution function, which will indicate when we have discovered a complete solution − − 一个解函数，当我们找到一个完整的解时，它会指示出来 − − − − Greedy algorithms produce good solutions on some [[mathematical problem]]s, but not on others. Most problems for which they work will have two properties: − − Greedy algorithms produce good solutions on some mathematical problems, but not on others. Most problems for which they work will have two properties: − − 贪婪算法在某些数学问题上产生好的解决方案，但在其他问题上却没有。他们研究的大多数问题都有两个属性: − − − − ; Greedy choice property: We can make whatever choice seems best at the moment and then solve the subproblems that arise later. The choice made by a greedy algorithm may depend on choices made so far, but not on future choices or all the solutions to the subproblem. It iteratively makes one greedy choice after another, reducing each given problem into a smaller one. In other words, a greedy algorithm never reconsiders its choices. This is the main difference from [[dynamic programming]], which is exhaustive and is guaranteed to find the solution. After every stage, dynamic programming makes decisions based on all the decisions made in the previous stage, and may reconsider the previous stage's algorithmic path to solution. − − Greedy choice property: We can make whatever choice seems best at the moment and then solve the subproblems that arise later. The choice made by a greedy algorithm may depend on choices made so far, but not on future choices or all the solutions to the subproblem. It iteratively makes one greedy choice after another, reducing each given problem into a smaller one. In other words, a greedy algorithm never reconsiders its choices. This is the main difference from dynamic programming, which is exhaustive and is guaranteed to find the solution. After every stage, dynamic programming makes decisions based on all the decisions made in the previous stage, and may reconsider the previous stage's algorithmic path to solution. − − 贪婪选择属性: 我们可以做出任何当前看起来最好的选择，然后解决随后出现的子问题。贪婪算法所做的选择可能取决于到目前为止所做的选择，但不取决于未来的选择或子问题的所有解决方案。它迭代地做出一个又一个贪婪的选择，将每个给定的问题缩小为一个更小的问题。换句话说，贪婪算法永远不会重新考虑它的选择。这是与动态规划的主要区别，动态规划是穷举式的，并且保证能够找到解决方案。在每个阶段之后，动态规划基于前一阶段的所有决策做出决策，并可能重新考虑前一阶段的算法路径到解决方案。 − − − − ;Optimal substructure: "A problem exhibits [[optimal substructure]] if an optimal solution to the problem contains optimal solutions to the sub-problems."<ref>Introduction to Algorithms (Cormen, Leiserson, Rivest, and Stein) 2001, Chapter 16 "Greedy Algorithms".</ref> − − Optimal substructure: "A problem exhibits optimal substructure if an optimal solution to the problem contains optimal solutions to the sub-problems." − − 最优子结构: “如果问题的最优解包含子问题的最优解，则问题表现为最优子结构。” − − − − − − {{multiple image − − − {多重图像 − − − | align = − − = align = − − − | direction = vertical − − | direction = vertical − − | width = 300 − − + − 300 − − − − | header = Examples on how a greedy algorithm may fail to achieve the optimal solution. − − | header = 贪婪算法可能无法获得最优解的例子。 − − | image1 = Greedy Glouton.svg − − − 1 = Greedy Glouton.svg − − + − | alt1 = − − 1 = − − | caption1 = Starting from A, a greedy algorithm that tries to find the maximum by following the greatest slope will find the local maximum at "m", oblivious to the global maximum at "M". − − − − | caption1 = 从 a 开始，一个贪婪算法试图通过跟随最大斜率来寻找最大值，会在“ m”处找到局部最大值，不会注意到“ m”处的全局最大值。 − − | image2 = Greedy-search-path-example.gif − − − 2 = Greedy-search-path-example. gif − − − | alt2 = − − 2 = − − | caption2 = − − 2 = + − − − − With a goal of reaching the largest sum, at each step, the greedy algorithm will choose what appears to be the optimal immediate choice, so it will choose 12 instead of 3 at the second step, and will not reach the best solution, which contains 99. − − With a goal of reaching the largest sum, at each step, the greedy algorithm will choose what appears to be the optimal immediate choice, so it will choose 12 instead of 3 at the second step, and will not reach the best solution, which contains 99. − − 为了达到最大和的目标，在每一步，贪婪算法将选择看起来是最优的即时选择，所以在第二步它将选择12而不是3，并且不会达到包含99的最优解。 − − }} − − }} − + − For many other problems, greedy algorithms fail to produce the optimal solution, and may even produce the ''unique worst possible'' solution. One example is the [[traveling salesman problem]] mentioned above: for each number of cities, there is an assignment of distances between the cities for which the nearest-neighbor heuristic produces the unique worst possible tour.<ref>{{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}}</ref>+ − − For many other problems, greedy algorithms fail to produce the optimal solution, and may even produce the unique worst possible solution. One example is the traveling salesman problem mentioned above: for each number of cities, there is an assignment of distances between the cities for which the nearest-neighbor heuristic produces the unique worst possible tour. − − 对于许多其他问题，贪婪算法不能产生最优解，甚至可能产生唯一的最坏可能的解。一个例子是上面提到的旅行推销员问题: 对于每个城市数量，都有一个城市之间的距离分配，其中最近的邻居启发式产生唯一的最坏可能的旅游。 − − − − ==Types== − Greedy algorithms can be characterized as being 'short sighted', and also as 'non-recoverable'. They are ideal only for problems which have 'optimal substructure'. Despite this, for many simple problems, the best suited algorithms are greedy algorithms. It is important, however, to note that the greedy algorithm can be used as a selection algorithm to prioritize options within a search, or branch-and-bound algorithm. There are a few variations to the greedy algorithm:+ − + − Greedy algorithms can be characterized as being 'short sighted', and also as 'non-recoverable'. They are ideal only for problems which have 'optimal substructure'. Despite this, for many simple problems, the best suited algorithms are greedy algorithms. It is important, however, to note that the greedy algorithm can be used as a selection algorithm to prioritize options within a search, or branch-and-bound algorithm. There are a few variations to the greedy algorithm:+ − − 贪婪算法可以被描述为“目光短浅” ，也可以被描述为“不可恢复”。它们只适用于具有“最优子结构”的问题。尽管如此，对于许多简单的问题，最适合的算法是贪婪算法。但是，值得注意的是，贪婪算法可以用作在搜索或分支定界算法中对选项进行优先级排序的选择算法。贪婪算法有几种变体: − − − + + − + + + + − * Relaxed greedy algorithms+ − + − − − ==Theory== − − Greedy algorithms have a long history of study in [[combinatorial optimization]] and [[theoretical computer science]]. Greedy heuristics are known to produce suboptimal results on many problems,<ref>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.</ref> and so natural questions are: − − Greedy algorithms have a long history of study in combinatorial optimization and theoretical computer science. Greedy heuristics are known to produce suboptimal results on many problems, and so natural questions are: − − 贪婪算法在组合优化和理论计算机科学领域有着悠久的研究历史。众所周知，贪婪启发法会在许多问题上产生次优的结果，因此自然的问题是: − − − − * For which problems do greedy algorithms perform optimally? − − * For which problems do greedy algorithms guarantee an approximately optimal solution? − − * For which problems is the greedy algorithm guaranteed ''not'' to produce an optimal solution? − − − − A large body of literature exists answering these questions for general classes of problems, such as [[matroid]]s, as well as for specific problems, such as [[set cover]]. − − A large body of literature exists answering these questions for general classes of problems, such as matroids, as well as for specific problems, such as set cover. − − 大量的文献都在回答这些问题，例如矩阵的一般类问题，以及集合覆盖等具体问题。 − − − − − A [[matroid]] is a mathematical structure that generalizes the notion of [[linear independence]] from [[vector spaces]] to arbitrary sets. If an optimization problem has the structure of a matroid, then the appropriate greedy algorithm will solve it optimally.<ref>Papadimitriou, Christos H., and Kenneth Steiglitz. Combinatorial optimization: algorithms and complexity. Courier Corporation, 1998.</ref>+ − + − A matroid is a mathematical structure that generalizes the notion of linear independence from vector spaces to arbitrary sets. If an optimization problem has the structure of a matroid, then the appropriate greedy algorithm will solve it optimally. − − 拟阵是一种数学结构，它将线性无关的概念从向量空间推广到任意集合。如果一个最佳化问题具有拟阵的结构，那么适当的贪婪算法将最优化地解决它。 − − − − − A function <math>f</math> defined on subsets of a set <math>\Omega</math> is called [[submodular]] if for every <math>S, T \subseteq \Omega</math> we have that <math>f(S)+f(T)\geq f(S\cup T)+f(S\cap T)</math>.+ − − A function <math>f</math> defined on subsets of a set <math>\Omega</math> is called submodular if for every <math>S, T \subseteq \Omega</math> we have that <math>f(S)+f(T)\geq f(S\cup T)+f(S\cap T)</math>. − − 定义在一个集合的子集上的一个函数，如果对于每个 < math > s，t 子集 ω </math > 我们有 < math > f (s) + f (t) geq f (s cup t) + f (s cap t) </math > 。 − − − − Suppose one wants to find a set <math>S</math> which maximizes <math>f</math>. The greedy algorithm, which builds up a set <math>S</math> by incrementally adding the element which increases <math>f</math> the most at each step, produces as output a set that is at least <math>(1 - 1/e) \max_{X \subseteq \Omega} f(X)</math>.<ref>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.</ref> That is, greedy performs within a constant factor of <math>(1 - 1/e) \approx 0.63</math> as good as the optimal solution. − − Suppose one wants to find a set <math>S</math> which maximizes <math>f</math>. The greedy algorithm, which builds up a set <math>S</math> by incrementally adding the element which increases <math>f</math> the most at each step, produces as output a set that is at least <math>(1 - 1/e) \max_{X \subseteq \Omega} f(X)</math>. That is, greedy performs within a constant factor of <math>(1 - 1/e) \approx 0.63</math> as good as the optimal solution. − − 假设一个人想要找到一个使数学最大化的集合。贪婪算法通过在每一步中逐步添加元素，使得每一步的 < math > f </math > 最大，从而建立一个集合 s </math > ，产生一个至少 < math > (1-1/e) max _ x subseteq } f (x) </math > 的集合作为输出。也就是说，贪婪的表现在一个常数 < math > (1-1/e)大约0.63 </math > 和最优解一样好。 − − − − Similar guarantees are provable when additional constraints, such as cardinality constraints,<ref>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.</ref> are imposed on the output, though often slight variations on the greedy algorithm are required. See <ref>Krause, Andreas, and Daniel Golovin. "[https://www.cs.cmu.edu/afs/.cs.cmu.edu/Web/People/dgolovin/papers/submodular_survey12.pdf Submodular function maximization]." (2014): 71-104.</ref> for an overview. − − Similar guarantees are provable when additional constraints, such as cardinality constraints, are imposed on the output, though often slight variations on the greedy algorithm are required. See for an overview. − − 当对输出施加额外的约束(如基数约束)时，类似的保证也是可以证明的，尽管贪婪算法通常需要一些细微的变化。请参阅概览。 − + − + + 第273行：
第86行： − 其他问题，贪婪算法提供了强有力的保证，但不是一个最优解决方案，包括+ − + + − + − + + − * [[Load balancing (computing)|Load balancing]]<ref>http://www.win.tue.nl/~mdberg/Onderwijs/AdvAlg_Material/Course%20Notes/lecture5.pdf</ref> − * [[Independent set (graph theory)#Approximation algorithms|Independent set]]+ − − − − Many of these problems have matching lower bounds; i.e., the greedy algorithm does not perform better, in the worst case, than the guarantee. − − Many of these problems have matching lower bounds; i.e., the greedy algorithm does not perform better, in the worst case, than the guarantee. − − 这些问题中的许多都有匹配的下界; 也就是说，贪婪算法在最坏的情况下并不比保证算法执行得更好。 − − − − 第303行：
第105行： − 贪婪算法通常(但并不总是)无法找到全局最优解，因为它们通常不会对所有数据进行详尽的操作。他们可能过早地对某些选择做出承诺，这会妨碍他们以后找到最佳的整体解决方案。例如，所有已知的图着色问题问题和所有其他 np 完全问题的贪婪着色算法都不能始终找到最优解。尽管如此，它们还是很有用的，因为它们很快就能想出来，而且常常能给出最佳的近似值。+ 第311行：
第113行： − 如果一个贪婪算法被证明可以为给定的问题类产生全局最优解，它通常成为选择的方法，因为它比动态规划等其他优化方法更快。这种贪婪算法的例子有 Kruskal 算法和 Prim 算法用于寻找最小生成树，以及寻找最优 Huffman 树的算法。+ 第319行：
第121行： − 贪婪算法也出现在网络路由中。使用贪婪路由，消息被转发到邻近的节点，这是“最接近”的目标。一个节点的位置(因此是“贴近度”)的概念可以由它的物理位置来决定，就像临时网络使用的地理路由一样。位置也可能是一个完全人为的构造，就像小世界路由和分散式杂凑表路由。+ − − + − + − + − + − + − + − + − 第360行：
第160行： − − + − − + − − * {{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}} − + − + − + − + − + − + + 第393行：
第190行： − + − +
无编辑摘要
此词条暂由彩云小译翻译，翻译字数共1208，Tanpopo正在进行审校，带来阅读不便，请见谅。
[[Image:Greedy algorithm 36 cents.svg|thumb|280px|right| Greedy algorithms determine minimum number of coins to give while making change. These are the steps a human would take to emulate a greedy algorithm to represent 36 cents using only coins with values {1, 5, 10, 20}. The coin of the highest value, less than the remaining change owed, is the local optimum. (In general the [[change-making problem]] requires [[dynamic programming]] to find an optimal solution; however, most currency systems, including the Euro and US Dollar, are special cases where the greedy strategy does find an optimal solution.)]]
[[Image:Greedy algorithm 36 cents.svg|thumb|280px|right| 利用贪心算法确定在找零时要提供的最小硬币数量。图中大多数人会采用的步骤，通过模拟贪心算法来只用面值为1、5、10、20 美分的硬币来表示 36 美分。价值最高且金额小于所欠的剩余零钱的硬币，是局部最优的。（一般来说，找零问题需要动态规划来找到最优解；然而，大多数货币系统，包括欧元系统和美元系统，都是贪心策略可以找到最优解的特殊情况。）|link=Special:FilePath/Greedy_algorithm_36_cents.svg]]
'''贪心算法'''是一种在每个阶段中都进行局部最优选择来进行问题求解的启发式算法。在许多问题中，贪心策略通常不会产生最优解，但贪心启发式算法可以产生局部最优解，即在合理的时间内得到全局最优解的近似。
例如，[[旅行商问题]]（计算复杂度很高）的贪心策略是以下启发式算法: “旅程的每一步都去最近的没去过的城市。”这种启发式方法并不打算找到最优解，但是它在合理的步骤数后终止，而通常为这种复杂问题找到最优解所需要的步骤数通常多到不合理。在最优化中，贪心算法可最优求解具有[[拟阵]]性质的组合问题，并给出具有子模结构的优化问题的常数因子近似。
==算法细节==
一般来说，贪心算法有五个组成部分:
#候选集，用于从中创建解
#选择函数，用于选择要添加到解中的最佳候选
#可行性函数，用于确定一个候选是否有助于解决问题
#目标函数，用于为解或部分解赋值
#解函数，当找到一个完整的解时，它会指示出来
A '''greedy algorithm''' is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage<ref name="NISTg">{{cite web|last=Black|first=Paul E.|title=greedy algorithm|url=http://xlinux.nist.gov/dads//HTML/greedyalgo.html|work=Dictionary of Algorithms and Data Structures|publisher=[[National Institute of Standards and Technology|U.S. National Institute of Standards and Technology]] (NIST) |accessdate=17 August 2012|date=2 February 2005}}</ref>. In many problems, a greedy strategy does not usually produce an optimal solution, but nonetheless a greedy heuristic may yield locally optimal solutions that approximate a globally optimal solution in a reasonable amount of time.
#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
贪心算法对一些数学问题上生成的解较好，但在另一些上的解不好。大多数可以使用贪心算法问题都有如下两个性质:
=== 贪心选择性质===
贪心选择性质指，可以首先做出目前最优选择，然后再解决随后出现的子问题。贪心算法所做的选择可能取决于过去所做的所有选择，但不考虑未来的选择，也不会考虑子问题的所有解。它通过迭代来依次做出贪心选择，将每个给定的问题缩小为一个更小的问题。换句话说，贪心算法不会重新考虑已做出的选择，这是贪心算法与动态规划的主要区别。[[动态规划]]是穷举式的，并且保证能够找到解。在每个阶段之后，动态规划基于之前的所有决策做出下一步决策，并可能重新考虑之前求解的算法路径。
===最优子结构===
“如果问题的最优解包含子问题的最优解，则问题具有[[最优子结构]]。”
=== 失效情况 ===
==Specifics==
===Cases of failure===
{{multiple image
{{multiple image
| align =
| align =
| direction = vertical
| direction = vertical
| width = 300
| width = 300
| header = 贪心算法可能无法获得最优解的例子。
| header = Examples on how a greedy algorithm may fail to achieve the optimal solution.
| image1 = Greedy Glouton.svg
| image1 = Greedy Glouton.svg
| alt1 =
| alt1 =
| caption1 = 从 a 开始，一个贪心算法试图通过跟随最大斜率来寻找最大值，会在“ m”处找到局部最大值，不会注意到“ m”处的全局最大值。
| caption1 = Starting from A, a greedy algorithm that tries to find the maximum by following the greatest slope will find the local maximum at "m", oblivious to the global maximum at "M".
| image2 = Greedy-search-path-example.gif
| image2 = Greedy-search-path-example.gif
| alt2 =
| alt2 =
| caption2 =
| caption2 =
为了达到最大和的目标，在每一步，贪心算法将选择看起来是最优的即时选择，所以在第二步它将选择12而不是3，并且不会达到包含99的最优解。
}}
}}
对于许多其他问题，贪心算法不能产生最优解，甚至可能产生唯一的最坏可能解。比如上面提到的旅行商问题，对于任意给定的城市数量，都存在一个城市之间的距离分配，使得最近邻启发式算法产生唯一的最坏可能的旅行方案。其他可能使贪心算法失效的例子，请参阅[[地平线效应]]。
== 分类==
{{More citations needed section|date=June 2018}}
{{More citations needed section|date=June 2018}}
贪心算法可以被描述为“目光短浅” ，也可以被描述为“不可恢复”。它们只适用于具有“最优子结构”的问题。尽管如此，对于许多简单的问题，最适合的算法依然是贪心算法。但是，值得注意的是，贪心算法可以用于在搜索或分支定界算法中对选项进行优先级排序。贪心算法有以下几种变体:
*纯贪心算法
*正交贪心算法
* Pure greedy algorithms
*松弛贪心算法
== 理论==
* Orthogonal greedy algorithms
贪心算法在[[组合优化]]和[[理论计算机科学]]领域有着悠久的研究历史。众所周知，贪心启发法会在许多问题上产生次优的结果，因此自然会提出以下问题:
*怎样的问题可以保证贪心算法能产生最优解？
*怎样的问题可以保证贪心算法能产生近似最优解？
*怎样的问题可以保证贪心算法无法产生最优解？
大量的文献都在回答上述问题，例如拟阵等回答一般类问题，以及集合覆盖等回答具体问题。
===拟阵===
===Matroids===
{{Main|Matroid}}
{{Main|Matroid}}
拟阵是一种将线性无关的概念从向量空间推广到任意集合的数学结构。如果一个最优化问题具有拟阵的结构，那么这个问题可由贪心算法得到最优解。
===子模函数===
===Submodular functions===
{{Main|Submodular set function#Optimization problems}}
{{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>下，贪心算法的表现和最优解一样好。
===Other problems with guarantees===
可以证明，当对输出施加额外的约束（如基数约束）时，类似的保证依然成立，尽管贪心算法通常需要一些细微的变化。详见[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
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
对其他问题，贪心算法提供了强保证，但不是最优解。这些问题包括：
*[[集合覆盖]]
*[[斯坦纳树]]问题
* [[Set cover problem#Greedy algorithm|Set cover]]
*[[负载均衡]]
* The [[Steiner tree problem]]
*[[独立集]]
其中许多问题都有匹配的下限；即，贪心算法在最坏情况下的性能并不优于保证。
==应用 ==
==Applications==
{{Expand section|date=June 2018}}
{{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 trees, and the algorithm for finding optimum Huffman trees.
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 networks. 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==
==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.
*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.
*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.
*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 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.
*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.
*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.
**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]].
*[[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.
**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.
*[[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.
*[[Best-first search]]
*[[Best-first search]]
==Notes==
==Notes==
<references/>
<references />
==References==
==References==
* ''[[Introduction to Algorithms]]'' (Cormen, Leiserson, Rivest, and Stein) 2001, Chapter 16 "Greedy Algorithms".
*''[[Introduction to Algorithms]]'' (Cormen, Leiserson, Rivest, and Stein) 2001, Chapter 16 "Greedy Algorithms".
* {{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/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.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}}
*{{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}}
* 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.
*{{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}}
* 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.
*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.
* 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.
*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.
* 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.
*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}}
{{commons category|Greedy algorithms}}
* {{springer|title=Greedy algorithm|id=p/g110210}}
*{{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.
*[http://www.oreillynet.com/onlamp/blog/2008/04/python_greedy_coin_changer_alg.html Python greedy coin] example by Noah Gift.