Editing Greedy algorithm (section)

==Specifics==
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 choice property: Whichever choice seems best at a given moment can be made and then (recursively) solve the remaining sub-problems. 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 the solution.
;Optimal substructure: "A problem exhibits [[optimal substructure]] if an optimal solution to the problem contains optimal solutions to the sub-problems."<ref>{{harvnb|Cormen|Leiserson|Rivest|Stein|2001|loc=Ch. 16}}</ref>

===Correctness Proofs=== 
A common technique for proving the correctness of greedy algorithms uses an [[inductive reasoning|inductive]] exchange argument.<ref>{{cite book |last=Erickson |first=Jeff |title=Algorithms |url=https://jeffe.cs.illinois.edu/teaching/algorithms/ |year=2019 |publisher=University of Illinois at Urbana-Champaign |chapter=Greedy Algorithms}}</ref> The exchange argument demonstrates that any solution different from the greedy solution can be transformed into the greedy solution without degrading its quality. This proof pattern typically follows these steps:

This proof pattern typically follows these steps (by contradiction): 
# Assume there exists an optimal solution different from the greedy solution 
# Identify the first point where the optimal and greedy solutions differ 
# Prove that exchanging the optimal choice for the greedy choice at this point cannot worsen the solution 
# Conclude by induction that there must exist an optimal solution identical to the greedy solution 

In some cases, an additional step may be needed to prove that no optimal solution can strictly improve upon the greedy solution.

===Cases of failure===
{{multiple image
   | align = 
| direction = vertical
   | width     = 300
   | header    = Examples on how a greedy algorithm may fail to achieve the optimal solution.
   | image1    = Greedy Glouton.svg
   | alt1      = 
   | 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
   | alt2      = 
   | caption2  =

To reach 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.
}}

Greedy algorithms fail to produce the optimal solution for many other problems and may even produce the ''unique worst possible'' solution. One example is the [[travelling salesman problem]] mentioned above: for each number of cities, there is an assignment of distances between the cities for which the nearest-neighbour 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|doi-access=free}}</ref>
For other possible examples, see [[horizon effect]].