Greedy algorithm: Difference between revisions

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search
← Previous edit
VisualWikitext
imported>Pirolegómano
Remove duplicated sentence with proof by contradiction reference "This proof pattern typically follows these steps (by contradiction):"
Fix Mistake in Big Oh of Activity Selection, see https://en.wikipedia.org/wiki/Activity_selection_problem
 
(One intermediate revision by one other user not shown)
Line 1: Line 1:
{{Short description|Sequence of locally optimal choices}}
{{Short description|Sequence of locally optimal choices}}
[[Image: Greedy algorithm 36 cents.svg|thumb|280px|right| Greedy algorithms determine the minimum number of coins to give while making change. These are the steps most people 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 are special cases where the greedy strategy does find an optimal solution.)]]


A '''greedy algorithm''' is any [[algorithm]] that follows the problem-solving [[Heuristic (computer science)|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) |access-date=17 August 2012|date=2 February 2005}}</ref> In many problems, a greedy strategy does not produce an optimal solution, but a greedy heuristic can yield locally optimal solutions that approximate a globally optimal solution in a reasonable amount of time.<ref>{{Cite web |last=van Melkebeek |first=Dieter |title=Greedy Approximations |url=https://pages.cs.wisc.edu/~dieter/Courses/2004F-CS787/Scribes/greedy-approx.pdf |access-date=2025-07-25 |website=University of Wisconsin–Madison}}</ref>
A '''greedy algorithm''' is an [[algorithm]] which, at each step, makes the choice that is locally optimal, and subsequently does not reconsider past choices. Greedy algorithms are often used to solve [[combinatorial optimization]] problems. If an optimization problem only depends on the partial solution of solving it for one subproblem, we can solve this problem by "greedily" considering only the locally optimal subproblem. In this sense, a greedy algorithm is a special case of a [[dynamic programming]] algorithm. [[Uriel Feige]]<ref name=":0">{{cite web |last=Feige |first=Uriel |title=Greedy algorithms and Matroids |url=https://www.wisdom.weizmann.ac.il/~feige/Algs2022/GreedyMatroidLecture.pdf |access-date=30 April 2026 |publisher=Department of Computer Science and Applied Mathematics, Weizmann Institute of Science }}</ref> notes that: <blockquote>[Greedy algorithms] may be viewed as the ultimate form of dynamic programming, in which only one partial solution is maintained. The problem needs to have much more structure for this approach to work. </blockquote>In many cases, a greedy algorithm does not produce an exact solution, but can yield solutions that [[Approximation algorithm|approximate]] an exact solution in a reasonable amount of time.<ref>{{Cite web |last=van Melkebeek |first=Dieter |title=Greedy Approximations |url=https://pages.cs.wisc.edu/~dieter/Courses/2004F-CS787/Scribes/greedy-approx.pdf |access-date=2025-07-25 |website=University of Wisconsin–Madison}}</ref>


For example, a greedy strategy for the [[travelling salesman problem]] (which is of 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 the 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.<ref>{{Cite arXiv |last1=Frieze |first1=Alan |last2=Pegden |first2=Wesley |date=2023-10-05 |title=The bright side of simple heuristics for the TSP |class=cs.DM |eprint=2310.03222 }}</ref>  
An example of a problem which admits an exact greedy solution, the [[activity selection problem]]. Given a collection of tasks which can be done between allotted time intervals, the problem is to determine the maximum number of tasks that can be done. A greedy algorithm in <math>O(n\log(n))</math> which solves this problem sorts the tasks by the end time and then repeatedly chooses the first task that begins after the last task ended.


In [[mathematical optimization]], greedy algorithms optimally solve [[Combinatorics|combinatorial]] problems having the properties of [[matroid]]s and give constant-factor approximations to optimization problems with the submodular structure.
Many classic algorithms in computer science such as the [[Huffman coding|Huffman coding algorithm]], [[Prim's algorithm]], [[Kruskal's algorithm]], and [[Dijkstra's algorithm]] all use greedy properties in their design. Mathematicians frequently use ''greedy strategies'' in proofs as well. A classic example is what [[Raphael Yuster]] refers to as the greedy proof<ref>{{Cite journal |last=Yuster |first=Raphael |date=January 2021 |title=Paths with many shortcuts in tournaments |journal=Discrete Mathematics |volume=344 |issue=1 |article-number=112168 |doi=10.1016/j.disc.2020.112168 |arxiv=2009.13985 }}</ref> that every [[Tournament (graph theory)|tournament]] in graph contains a [[Hamiltonian path]].


==Specifics==
==Characterizations==
Greedy algorithms produce good solutions on some [[mathematical problem]]s, but not on others. Most problems for which they work will  have two properties:
Since there is no formal definition of what a greedy algorithm is,<ref>{{cite web |title=Lecture 1 – Basics and Greedy Algorithms |url=https://www.kth.se/social/files/58203563f2765475d38069ea/algorithms-for-networks-notes-v2-lecture1.pdf |access-date=30 April 2026 |website=KTH Social |publisher=KTH Royal Institute of Technology }}</ref> a complete characterization of when a problem admits a greedy algorithm as a solution is not known. However, special cases have been identified. [[Jack Edmonds]] showed that a greedy algorithm can be used to solve a class of linear combinatorial optimization problems with a [[Matroid|matroid structure.]]<ref>{{Cite journal |last=Edmonds |first=Jack |date=December 1971 |title=Matroids and the greedy algorithm |url=http://link.springer.com/10.1007/BF01584082 |journal=Mathematical Programming |language=en |volume=1 |issue=1 |pages=127–136 |doi=10.1007/BF01584082 |issn=0025-5610|url-access=subscription }}</ref>


; 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 best (that is, the 'optimal') 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.
Later [[Bernhard Korte]] and [[László Lovász]] characterized a broader class of optimization problems by introducing the notion of a [[greedoid]]. This allowed, for example, a proof of the optimality of [[Prim's algorithm]].  
;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===  
Algorithms which undo past steps are not greedy. For example, the [[Gale–Shapley algorithm|Gale-Shapley]] algorithm is not a greedy algorithm since although it constructs a solution by choosing the current best pairing, in the process, existing solutions may be modified.
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:
 
== Correctness ==
One technique used to prove the optimiality of greedy algorithms is an 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 is at most as good as the greedy solution. This proof pattern typically follows these steps:


# Assume there exists an optimal solution different from the greedy solution  
# Assume there exists an optimal solution different from the greedy solution  
# Identify the first point where the optimal and greedy solutions differ  
# Consider 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  
# Prove that exchanging the optimal choice for the greedy choice at this point cannot worsen the greedy solution
# Conclude by induction that there must exist an optimal solution identical to the greedy solution  
# Conclude by induction that the greedy solution is optimal.  
 
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
{{multiple image
  | align =  
| align             =  
| direction = vertical
| direction         = vertical
  | width     = 300
| width             = 300
  | header   = Examples on how a greedy algorithm may fail to achieve the optimal solution.
| header           = Examples of how a greedy algorithm may fail to achieve the optimal solution
  | image1   = Greedy Glouton.svg
| image1           = Greedy Glouton.svg
  | alt1     =  
| 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".
| 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         = 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.
 
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>
==Further examples==
For other possible examples, see [[horizon effect]].
* In the [[Continuous knapsack problem|fractional knapsack problem]], one is given a list of items with weights and values. The goal is to choose fractional amounts of each item such that the total value is maximised, and the weight is below a fixed constraint. Unlike the [[knapsack problem]], which is known to be [[NP-hardness|NP-hard]], the fractional knapsack problem admits a polynomial time greedy algorithm.
 
* Instances of the [[Coin problem|Frobenius coin problem]] admit greedy solutions. However, in some cases the greedy algorithm does not yield an optimal solution.<ref>{{Citation |last1=Gupta |first1=Shreya |title=The Greedy Coin Change Problem |date=2024-11-27 |arxiv=2411.18137 |last2=Huang |first2=Boyang |last3=Impagliazzo |first3=Russell}}</ref>
==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 that have an 'optimal substructure'. Despite this, for many simple problems, the best-suited algorithms are greedy. 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:<ref>{{Cite journal |last1=DeVore |first1=R. A. |last2=Temlyakov |first2=V. N. |date=1996-12-01 |title=Some remarks on greedy algorithms |url=https://doi.org/10.1007/BF02124742 |journal=Advances in Computational Mathematics |language=en |volume=5 |issue=1 |pages=173–187 |doi=10.1007/BF02124742 |issn=1572-9044|url-access=subscription }}</ref>
 
* 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>{{harvnb|Feige|1998}}</ref> 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 are greedy algorithms 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]].
 
===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>{{harvnb|Papadimitriou|Steiglitz|1998}}</ref>
 
===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>.
 
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>{{harvnb|Nemhauser|Wolsey|Fisher|1978}}</ref> That is, greedy performs within a constant factor of <math>(1 - 1/e) \approx 0.63</math> as good as the optimal solution.
 
Similar guarantees are provable when additional constraints, such as cardinality constraints,<ref>{{harvnb|Buchbinder|Feldman|Naor|Schwartz|2014}}</ref> are imposed on the output, though often slight variations on the greedy algorithm are required. See <ref>{{harvnb|Krause|Golovin|2014}}</ref> for an overview.
 
===Other problems with guarantees===
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>{{cite web |title=Lecture 5: Introduction to Approximation Algorithms |work=Advanced Algorithms (2IL45) — Course Notes |publisher=TU Eindhoven |url=http://www.win.tue.nl/~mdberg/Onderwijs/AdvAlg_Material/Course%20Notes/lecture5.pdf |archive-url=https://ghostarchive.org/archive/20221009/http://www.win.tue.nl/~mdberg/Onderwijs/AdvAlg_Material/Course%20Notes/lecture5.pdf |archive-date=2022-10-09 |url-status=live}}</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 than the guarantee in the worst case.
 
==Applications==
{{Expand section|date=June 2018}}
Greedy algorithms typically (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, preventing 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.
 
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.
 
Greedy algorithms appear in network [[routing]] as well.  Using greedy routing, a message is forwarded to the neighbouring 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]].
 
==Examples==
* The [[activity selection problem]] is characteristic of 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 a greedy algorithm applied on signal approximation.
* The [[matching pursuit]] is an example of a 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.
* 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.
*A greedy algorithm constructs the [[Zeckendorf's theorem|Zeckendorf representation]] (or Fibonacci coding) of a natural number. Subtracting the largest Fibonacci number less than or equal to the natural number repeatedly gives its Zecekndorf representation. The greedy algorithm is extracted from the existence proof of the Zeckendorf representation. The uniqueness of the Zeckendorf representation guarantees that no other non-consecutive Fibonacci sum can give a different output.
*[[Fibonacci]] described [[Greedy algorithm for Egyptian fractions|an greedy algorithm for computing Egyptian fractions]].
*Greedy algorithms appear in network [[routing]]. Using greedy routing, a message is forwarded to the neighbouring 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 on graphs==
Graph theory is a rich source of greedy algorithms. Computing scientists frequently use greedy algorithms frequently to compute graph invariants.
*[[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.
*A greedy algorithm constructs a Huffman tree in [[Huffman coding]].
*The [[Sequitur algorithm|Sequitur]] and [[Lempel-Ziv-Welch algorithm|Lempel-Ziv-Welch]] algorithms are [[Grammar_induction#Grammatical_inference_by_greedy_algorithms|greedy algorithms for grammar induction]].
*The [[Sequitur algorithm|Sequitur]] and [[Lempel-Ziv-Welch algorithm|Lempel-Ziv-Welch]] algorithms are [[Grammar_induction#Grammatical_inference_by_greedy_algorithms|greedy algorithms for grammar induction]].
*A greedy algorithm finds the maximum independent set in a tree.
Greedy algorithms are also used to find upper bounds for the [[Graph coloring|chromatic numbers]]<ref>{{cite tech report |url=https://inria.hal.science/inria-00470158 |title=New bounds on the Grundy number of products of graphs |last1=Campos |first1=Victor |last2=Gyárfás |first2=András |last3=Havet |first3=Frédéric |last4=Linhares Sales |first4=Claudia |last5=Maffray |first5=Frédéric |date=April 2010 |institution=INRIA |number=RR-7243}}</ref>. A simple example is the bound <math>\chi(G) \leq \Delta(G) + 1</math> obtained by a greedy algorithm.<ref>{{Cite book |last=Diestel |first=Reinhard |title=Graph Theory |date=2025 |publisher=Springer |isbn=978-3-662-70106-5 |edition=Sixth Edition 2025 |series=Graduate Texts in Mathematics |location=Erscheinungsort nicht ermittelbar}}</ref> We begin by taking a vertex that has not been colored. Since it has at most <math>\Delta(G)</math> neighbours, at most <math>\Delta(G)</math> colors are used in adjacent vertices, leaving a color free for the vertex under consideration.
== Greedy approximation algorithms ==
A solution to the [[NP-completeness|NP-complete]] [[travelling salesman problem]] can be approximated by starting from an empty edge set and then adding the next cheapest edge which is a subgraph of a complete tour. This greedy algorithm has been proven to yield at most <math>\Theta (\log n)</math> times longer than the optimal tour.<ref>{{Cite journal |last1=Brecklinghaus |first1=Judith |last2=Hougardy |first2=Stefan |date=2015-05-01 |title=The approximation ratio of the greedy algorithm for the metric traveling salesman problem |url=https://www.sciencedirect.com/science/article/pii/S0167637715000280 |journal=Operations Research Letters |volume=43 |issue=3 |pages=259–261 |doi=10.1016/j.orl.2015.02.009 |issn=0167-6377|url-access=subscription }}</ref>
Another example is that a solution for the [[Knapsack problem|0-1 knapsack problem]] can be approximated by using the greedy algorithm for the  [[Continuous knapsack problem|fractional knapsack problem]]. This greedy algorithm has been proven to yield a solution at least half the value of the optimal solution.<ref>{{cite web |last=Nelson |first=Jelani |date=March 7, 2017 |others=Scribe: Hongyao Ma |title=Lecture 13: PTAS/FPTAS/FPRAS examples; Approximation algorithms via SDP |url=https://people.seas.harvard.edu/~cs224/spring17/lec/lec13.pdf |access-date=May 1, 2026 |website=CS 224: Advanced Algorithms, Spring 2017 |publisher=Harvard University}}</ref>
Solutions for [[submodular maximization]] are approximated using a greedy algorithm which yields a solution at least half the value of the optimal solution.<ref>{{Cite conference |conference=IEEE Conference on Decision and Control |last1=Grimsman |first1=David |last2=Hespanha |first2=Joao P. |last3=Marden |first3=Jason R. |date=December 17–19, 2018 |title=Strategic Information Sharing in Greedy Submodular Maximization |publisher=IEEE |location=Miami, Fla. |pages=2722–2727 |doi=10.1109/CDC.2018.8619166 |isbn=978-1-5386-1395-5}}</ref>
Problems for which greedy algorithms are used to provide approximation algorithms include the [[Set cover problem#Greedy algorithm|set cover]][[Load balancing (computing)|, load balancing]], [[Steiner tree problem|Steiner tree]] and [[Independent set (graph theory)#Approximation algorithms|independent set]]<ref>{{cite web |title=Lecture 5: Introduction to Approximation Algorithms |work=Advanced Algorithms (2IL45) — Course Notes |publisher=TU Eindhoven |url=http://www.win.tue.nl/~mdberg/Onderwijs/AdvAlg_Material/Course%20Notes/lecture5.pdf |archive-url=https://ghostarchive.org/archive/20221009/http://www.win.tue.nl/~mdberg/Onderwijs/AdvAlg_Material/Course%20Notes/lecture5.pdf |archive-date=2022-10-09 |url-status=live}}</ref> problem.


==See also==
==See also==

Latest revision as of 08:43, 2 June 2026

Template:Short description

A greedy algorithm is an algorithm which, at each step, makes the choice that is locally optimal, and subsequently does not reconsider past choices. Greedy algorithms are often used to solve combinatorial optimization problems. If an optimization problem only depends on the partial solution of solving it for one subproblem, we can solve this problem by "greedily" considering only the locally optimal subproblem. In this sense, a greedy algorithm is a special case of a dynamic programming algorithm. Uriel Feige[1] notes that:

[Greedy algorithms] may be viewed as the ultimate form of dynamic programming, in which only one partial solution is maintained. The problem needs to have much more structure for this approach to work.

In many cases, a greedy algorithm does not produce an exact solution, but can yield solutions that approximate an exact solution in a reasonable amount of time.[2]

An example of a problem which admits an exact greedy solution, the activity selection problem. Given a collection of tasks which can be done between allotted time intervals, the problem is to determine the maximum number of tasks that can be done. A greedy algorithm in O(nlog⁡(n)) which solves this problem sorts the tasks by the end time and then repeatedly chooses the first task that begins after the last task ended.

Many classic algorithms in computer science such as the Huffman coding algorithm, Prim's algorithm, Kruskal's algorithm, and Dijkstra's algorithm all use greedy properties in their design. Mathematicians frequently use greedy strategies in proofs as well. A classic example is what Raphael Yuster refers to as the greedy proof[3] that every tournament in graph contains a Hamiltonian path.

Characterizations

Since there is no formal definition of what a greedy algorithm is,[4] a complete characterization of when a problem admits a greedy algorithm as a solution is not known. However, special cases have been identified. Jack Edmonds showed that a greedy algorithm can be used to solve a class of linear combinatorial optimization problems with a matroid structure.[5]

Later Bernhard Korte and László Lovász characterized a broader class of optimization problems by introducing the notion of a greedoid. This allowed, for example, a proof of the optimality of Prim's algorithm.

Algorithms which undo past steps are not greedy. For example, the Gale-Shapley algorithm is not a greedy algorithm since although it constructs a solution by choosing the current best pairing, in the process, existing solutions may be modified.

Correctness

One technique used to prove the optimiality of greedy algorithms is an exchange argument.[6] The exchange argument demonstrates that any solution different from the greedy solution is at most as good as the greedy solution. This proof pattern typically follows these steps:

  1. Assume there exists an optimal solution different from the greedy solution
  2. Consider the first point where the optimal and greedy solutions differ
  3. Prove that exchanging the optimal choice for the greedy choice at this point cannot worsen the greedy solution
  4. Conclude by induction that the greedy solution is optimal.

Script error: No such module "Multiple image".

Further examples

  • In the fractional knapsack problem, one is given a list of items with weights and values. The goal is to choose fractional amounts of each item such that the total value is maximised, and the weight is below a fixed constraint. Unlike the knapsack problem, which is known to be NP-hard, the fractional knapsack problem admits a polynomial time greedy algorithm.
  • Instances of the Frobenius coin problem admit greedy solutions. However, in some cases the greedy algorithm does not yield an optimal solution.[7]
  • The matching pursuit is an example of a greedy algorithm applied on signal approximation.
  • A greedy algorithm finds the optimal solution to 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.
  • 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.
  • A greedy algorithm constructs the Zeckendorf representation (or Fibonacci coding) of a natural number. Subtracting the largest Fibonacci number less than or equal to the natural number repeatedly gives its Zecekndorf representation. The greedy algorithm is extracted from the existence proof of the Zeckendorf representation. The uniqueness of the Zeckendorf representation guarantees that no other non-consecutive Fibonacci sum can give a different output.
  • Fibonacci described an greedy algorithm for computing Egyptian fractions.
  • Greedy algorithms appear in network routing. Using greedy routing, a message is forwarded to the neighbouring 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 on graphs

Graph theory is a rich source of greedy algorithms. Computing scientists frequently use greedy algorithms frequently to compute graph invariants.

Greedy algorithms are also used to find upper bounds for the chromatic numbers[8]. A simple example is the bound χ(G)≤Δ(G)+1 obtained by a greedy algorithm.[9] We begin by taking a vertex that has not been colored. Since it has at most Δ(G) neighbours, at most Δ(G) colors are used in adjacent vertices, leaving a color free for the vertex under consideration.

Greedy approximation algorithms

A solution to the NP-complete travelling salesman problem can be approximated by starting from an empty edge set and then adding the next cheapest edge which is a subgraph of a complete tour. This greedy algorithm has been proven to yield at most Θ(log⁡n) times longer than the optimal tour.[10]

Another example is that a solution for the 0-1 knapsack problem can be approximated by using the greedy algorithm for the fractional knapsack problem. This greedy algorithm has been proven to yield a solution at least half the value of the optimal solution.[11]

Solutions for submodular maximization are approximated using a greedy algorithm which yields a solution at least half the value of the optimal solution.[12]

Problems for which greedy algorithms are used to provide approximation algorithms include the set cover, load balancing, Steiner tree and independent set[13] problem.

See also

Script error: No such module "Portal".

<templatestyles src="Div col/styles.css"/>

Script error: No such module "Check for unknown parameters".

References

<templatestyles src="Reflist/styles.css" />

  1. ↑ Script error: No such module "citation/CS1".
  2. ↑ Script error: No such module "citation/CS1".
  3. ↑ Script error: No such module "Citation/CS1".
  4. ↑ Script error: No such module "citation/CS1".
  5. ↑ Script error: No such module "Citation/CS1".
  6. ↑ Script error: No such module "citation/CS1".
  7. ↑ Script error: No such module "citation/CS1".
  8. ↑ Script error: No such module "citation/CS1".
  9. ↑ Script error: No such module "citation/CS1".
  10. ↑ Script error: No such module "Citation/CS1".
  11. ↑ Script error: No such module "citation/CS1".
  12. ↑ Script error: No such module "citation/CS1".
  13. ↑ Script error: No such module "citation/CS1".

Script error: No such module "Check for unknown parameters".

Sources

<templatestyles src="Refbegin/styles.css" />

  • Script error: No such module "citation/CS1".
  • Script error: No such module "Citation/CS1".
  • Script error: No such module "Citation/CS1".
  • Script error: No such module "Citation/CS1".
  • Script error: No such module "Citation/CS1".
  • Script error: No such module "Citation/CS1".
  • Script error: No such module "citation/CS1".
  • Script error: No such module "citation/CS1".
  • Script error: No such module "citation/CS1".

External links

Script error: No such module "Side box".

Template:Optimization algorithmsTemplate:Algorithmic paradigms Script error: No such module "Authority control".

Retrieved from "http://debianws.lexgopc.com/wiki143/index.php?title=Greedy_algorithm&oldid=9694179"