贪心算法
此词条暂由彩云小译翻译，翻译字数共119，未经人工整理和审校，带来阅读不便，请见谅。
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[1]. 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
贪婪算法是遵循在每个阶段进行局部最优选择的问题求解启发式的任何算法
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.
Specifics
In general, greedy algorithms have five components:
- 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
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.
- Optimal substructure
- "A problem exhibits optimal substructure if an optimal solution to the problem contains optimal solutions to the sub-problems."[2]
Cases of failure
Category:Optimization algorithms and methods
类别: 优化算法和方法
{{multiple image
Category:Combinatorial algorithms
类别: 组合算法
| align =
Category:Matroid theory
范畴: 拟阵理论
| direction = vertical
Category:Exchange algorithms
类别: Exchange 算法
This page was moved from wikipedia:en:Greedy algorithm. Its edit history can be viewed at 贪心算法/edithistory
- ↑ Black, Paul E. (2 February 2005). "greedy algorithm". Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology (NIST). Retrieved 17 August 2012.
- ↑ Introduction to Algorithms (Cormen, Leiserson, Rivest, and Stein) 2001, Chapter 16 "Greedy Algorithms".