Greedy algorithm
![](https://upload.wikimedia.org/wikipedia/commons/thumb/d/da/Greedy_algorithm_36_cents.svg/280px-Greedy_algorithm_36_cents.svg.png)
Agreedy algorithmis anyalgorithmthat follows the problem-solvingheuristicof making the locally optimal choice at each stage.[1]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.
For example, a greedy strategy for thetravelling salesman problem(which is of highcomputational 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. In mathematical optimization, greedy algorithms optimally solve combinatorial problems having the properties ofmatroidsand give constant-factor approximations to optimization problems with the submodular structure.
Specifics
[edit]Greedy algorithms produce good solutions on somemathematical problems,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 fromdynamic 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 exhibitsoptimal substructureif an optimal solution to the problem contains optimal solutions to the sub-problems. "[2]
Cases of failure
[edit]Greedy algorithms fail to produce the optimal solution for many other problems and may even produce theunique worst possiblesolution. One example is thetravelling salesman problemmentioned 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.[3] For other possible examples, seehorizon effect.
Types
[edit]This sectionneeds additional citations forverification.(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:[4]
- Pure greedy algorithms
- Orthogonal greedy algorithms
- Relaxed greedy algorithms
Theory
[edit]Greedy algorithms have a long history of study incombinatorial optimizationandtheoretical computer science.Greedy heuristics are known to produce suboptimal results on many problems,[5]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 the greedy algorithm guaranteednotto produce an optimal solution?
A large body of literature exists answering these questions for general classes of problems, such asmatroids,as well as for specific problems, such asset cover.
Matroids
[edit]Amatroidis a mathematical structure that generalizes the notion oflinear independencefromvector spacesto arbitrary sets. If an optimization problem has the structure of a matroid, then the appropriate greedy algorithm will solve it optimally.[6]
Submodular functions
[edit]A functiondefined on subsets of a setis calledsubmodularif for everywe have that.
Suppose one wants to find a setwhich maximizes.The greedy algorithm, which builds up a setby incrementally adding the element which increasesthe most at each step, produces as output a set that is at least.[7]That is, greedy performs within a constant factor ofas good as the optimal solution.
Similar guarantees are provable when additional constraints, such as cardinality constraints,[8]are imposed on the output, though often slight variations on the greedy algorithm are required. See[9]for an overview.
Other problems with guarantees
[edit]Other problems for which the greedy algorithm gives a strong guarantee, but not an optimal solution, include
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
[edit]![]() | This sectionneeds expansion.You can help byadding to it.(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 knowngreedy coloringalgorithms for thegraph coloring problemand all otherNP-completeproblems 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 likedynamic programming.Examples of such greedy algorithms areKruskal's algorithmandPrim's algorithmfor findingminimum spanning treesand the algorithm for finding optimumHuffman trees.
Greedy algorithms appear in the networkroutingas 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 ingeographic routingused byad hoc networks.Location may also be an entirely artificial construct as insmall world routinganddistributed hash table.
Examples
[edit]- Theactivity selection problemis 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 theMacintosh computergameCrystal Questthe objective is to collect crystals, in a fashion similar to thetravelling salesman problem.The game has a demo mode, where the game uses a greedy algorithm to go to every crystal. Theartificial intelligencedoes not account for obstacles, so the demo mode often ends quickly.
- Thematching pursuitis an example of a greedy algorithm applied on signal approximation.
- A greedy algorithm finds the optimal solution toMalfatti's problemof 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 duringHuffman codingwhere it finds an optimal solution.
- Indecision tree learning,greedy algorithms are commonly used, however they are not guaranteed to find the optimal solution.
- One popular such algorithm is theID3 algorithmfor decision tree construction.
- Dijkstra's algorithmand the relatedA* search algorithmare verifiably optimal greedy algorithms forgraph searchandshortest path finding.
- A* search is conditionally optimal, requiring an "admissible heuristic"that will not overestimate path costs.
- Kruskal's algorithmandPrim's algorithmare greedy algorithms for constructingminimum spanning treesof a givenconnected graph.They always find an optimal solution, which may not be unique in general.
- TheSequiturandLempel-Ziv-Welchalgorithms aregreedy algorithms for grammar induction.
See also
[edit]References
[edit]- ^Black, Paul E. (2 February 2005)."greedy algorithm".Dictionary of Algorithms and Data Structures.U.S. National Institute of Standards and Technology(NIST).Retrieved17 August2012.
- ^Cormen et al. 2001,Ch. 16
- ^Gutin, Gregory; Yeo, Anders; Zverovich, Alexey (2002)."Traveling salesman should not be greedy: Domination analysis of greedy-type heuristics for the TSP".Discrete Applied Mathematics.117(1–3): 81–86.doi:10.1016/S0166-218X(01)00195-0.
- ^DeVore, R. A.; Temlyakov, V. N. (1996-12-01)."Some remarks on greedy algorithms".Advances in Computational Mathematics.5(1): 173–187.doi:10.1007/BF02124742.ISSN1572-9044.
- ^Feige 1998
- ^Papadimitriou & Steiglitz 1998
- ^Nemhauser, Wolsey & Fisher 1978
- ^Buchbinder et al. 2014
- ^Krause & Golovin 2014
- ^"Lecture 5: Introduction to Approximation Algorithms"(PDF).Advanced Algorithms (2IL45) — Course Notes.TU Eindhoven.Archived(PDF)from the original on 2022-10-09.
Sources
[edit]- Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001)."16 Greedy Algorithms".Introduction To Algorithms.MIT Press. pp. 370–.ISBN978-0-262-03293-3.
- Gutin, Gregory; Yeo, Anders; Zverovich, Alexey (2002)."Traveling salesman should not be greedy: Domination analysis of greedy-type heuristics for the TSP".Discrete Applied Mathematics.117(1–3): 81–86.doi:10.1016/S0166-218X(01)00195-0.
- Bang-Jensen, Jørgen; Gutin, Gregory; Yeo, Anders (2004)."When the greedy algorithm fails".Discrete Optimization.1(2): 121–127.doi:10.1016/j.disopt.2004.03.007.
- Bendall, Gareth; Margot, François (2006)."Greedy-type resistance of combinatorial problems".Discrete Optimization.3(4): 288–298.doi:10.1016/j.disopt.2006.03.001.
- Feige, U. (1998)."A threshold of ln n for approximating set cover"(PDF).Journal of the ACM.45(4): 634–652.doi:10.1145/285055.285059.S2CID52827488.Archived(PDF)from the original on 2022-10-09.
- Nemhauser, G.; Wolsey, L.A.; Fisher, M.L. (1978)."An analysis of approximations for maximizing submodular set functions—I".Mathematical Programming.14(1): 265–294.doi:10.1007/BF01588971.S2CID206800425.
- Buchbinder, Niv; Feldman, Moran; Naor, Joseph (Seffi); Schwartz, Roy (2014)."Submodular maximization with cardinality constraints"(PDF).Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms.Society for Industrial and Applied Mathematics.doi:10.1137/1.9781611973402.106.ISBN978-1-61197-340-2.Archived(PDF)from the original on 2022-10-09.
- Krause, A.; Golovin, D. (2014)."Submodular Function Maximization".In Bordeaux, L.; Hamadi, Y.; Kohli, P. (eds.).Tractability: Practical Approaches to Hard Problems.Cambridge University Press. pp. 71–104.doi:10.1017/CBO9781139177801.004.ISBN9781139177801.
- Papadimitriou, Christos H.;Steiglitz, Kenneth(1998).Combinatorial Optimization: Algorithms and Complexity.Dover.
External links
[edit]![](https://upload.wikimedia.org/wikipedia/en/thumb/4/4a/Commons-logo.svg/30px-Commons-logo.svg.png)
- "Greedy algorithm",Encyclopedia of Mathematics,EMS Press,2001 [1994]
- Gift, Noah."Python greedy coin example".