更改

跳到导航 跳到搜索

贪心算法 (查看源代码)

2020年10月27日 (二) 22:22的版本

添加24,704字节 、 2020年10月27日 (二) 22:22
小
Moved page from wikipedia:en:Greedy algorithm (history)
第1行： 第1行： −
此词条暂由彩云小译翻译，翻译字数共119，未经人工整理和审校，带来阅读不便，请见谅。
+
此词条暂由彩云小译翻译，翻译字数共1208，未经人工整理和审校，带来阅读不便，请见谅。
    
[[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| 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.)]]
第11行： 第11行：  
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 '''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 greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage
+
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 [[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.
 +
 +
例如，旅行推销员问题的贪婪策略(具有很高的计算复杂性)是以下启发式: “在旅程的每一步，访问最近的未访问的城市。”这种启发式方法并不打算找到最佳解决方案，但是它在合理的步骤数中终止; 为这样一个复杂问题找到最佳解决方案通常需要不合理的许多步骤。在最优化中，贪婪算法最优化地解决具有拟阵性质的组合问题，并给出具有子模结构的优化问题的常数因子近似。
      第24行： 第28行：     
In general, greedy algorithms have five components:
 
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 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 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
 +
 +
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
 +
 +
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
 +
 +
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 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.
 +
 +
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."<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."
 +
 +
最优子结构: “如果问题的最优解包含子问题的最优解，则问题表现为最优子结构。”
          
===Cases of failure===
 
===Cases of failure===
 +
 +
{{multiple image
 +
 +
{{multiple image
 +
 +
{多重图像
 +
 +
  | align =
 +
 +
  | align =
 +
 +
= align =
 +
 +
| direction = vertical
 +
 +
| direction = vertical
 +
 +
| direction = vertical
 +
 +
  | width    = 300
 +
 +
  | width    = 300
 +
 +
300
 +
 +
  | header    = Examples on how a greedy algorithm may fail to achieve the optimal solution.
 +
 +
  | header    = Examples on how a greedy algorithm may fail to achieve the optimal solution.
 +
 +
| header = 贪婪算法可能无法获得最优解的例子。
 +
 +
  | image1    = Greedy Glouton.svg
 +
 +
  | image1    = Greedy Glouton.svg
 +
 +
1 = Greedy Glouton.svg
 +
 +
  | alt1      =
 +
 +
  | 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  = 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
 +
 +
  | image2    = Greedy-search-path-example.gif
 +
 +
2 = Greedy-search-path-example. gif
 +
 +
  | alt2      =
 +
 +
  | alt2      =
 +
 +
2 =
 +
 +
  | caption2  =
 +
 +
  | 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==
 +
 +
{{More citations needed section|date=June 2018}}
 +
 +
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:
 +
 +
贪婪算法可以被描述为“目光短浅” ，也可以被描述为“不可恢复”。它们只适用于具有“最优子结构”的问题。尽管如此，对于许多简单的问题，最适合的算法是贪婪算法。但是，值得注意的是，贪婪算法可以用作在搜索或分支定界算法中对选项进行优先级排序的选择算法。贪婪算法有几种变体:
 +
 +
 +
 +
* Pure greedy algorithms
 +
 +
* Orthogonal greedy algorithms
 +
 +
* 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.
 +
 +
大量的文献都在回答这些问题，例如矩阵的一般类问题，以及集合覆盖等具体问题。
 +
 +
 +
 +
===Matroids===
 +
 +
{{Main|Matroid}}
 +
 +
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.
 +
 +
拟阵是一种数学结构，它将线性无关的概念从向量空间推广到任意集合。如果一个最佳化问题具有拟阵的结构，那么适当的贪婪算法将最优化地解决它。
 +
 +
 +
 +
===Submodular functions===
 +
 +
{{Main|Submodular set function#Optimization problems}}
 +
 +
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.
 +
 +
当对输出施加额外的约束(如基数约束)时，类似的保证也是可以证明的，尽管贪婪算法通常需要一些细微的变化。请参阅概览。
 +
 +
 +
 +
===Other problems with guarantees===
 +
 +
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]]
 +
 +
* [[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.
 +
 +
这些问题中的许多都有匹配的下界; 也就是说，贪婪算法在最坏的情况下并不比保证算法执行得更好。
 +
 +
 +
 +
==Applications==
 +
 +
{{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 完全问题的贪婪着色算法都不能始终找到最优解。尽管如此，它们还是很有用的，因为它们很快就能想出来，而且常常能给出最佳的近似值。
 +
 +
 +
 +
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:Optimization algorithms and methods
第55行： 第407行：  
类别: 优化算法和方法
 
类别: 优化算法和方法
   −
{{multiple image
+
[[Category:Combinatorial algorithms]]
    
Category:Combinatorial algorithms
 
Category:Combinatorial algorithms
第61行： 第413行：  
类别: 组合算法
 
类别: 组合算法
   −
  | align =
+
[[Category:Matroid theory]]
    
Category:Matroid theory
 
Category:Matroid theory
第67行： 第419行：  
范畴: 拟阵理论
 
范畴: 拟阵理论
   −
| direction = vertical
+
[[Category:Exchange algorithms]]
    
Category:Exchange algorithms
 
Category:Exchange algorithms
Moonscar
管理员
1,592

个编辑

取自“https://wiki.swarma.org/index.php/特殊:移动版差异/17210”

导航菜单