(algorithmic technique)
Definition: An algorithm that always takes the best immediate, or local, solution while finding an answer. Greedy algorithms find the overall, or globally, optimal solution for some optimization problems, but may find less-than-optimal solutions for some instances of other problems.
Specialization (... is a kind of me.)
Dijkstra's algorithm, Huffman coding, Kruskal's algorithm, optimal merge, Prim-Jarnik algorithm.
See also greedy heuristic.
Note: Prim-Jarnik algorithm and Kruskal's algorithm are greedy algorithms that find the globally optimal solution, a minimum spanning tree. In contrast, any known greedy algorithm to find a Hamiltonian cycle might not find the shortest path, that is, a solution to the traveling salesman problem.
If there is no greedy algorithm that always finds the optimal solution for a problem, one may have to search (exponentially) many possible solutions to find the optimum. Greedy algorithms are usually quicker, since they don't consider the details of possible alternatives.
Author: PEB
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 2 February 2005.
HTML page formatted Mon Feb 2 13:10:39 2015.
Cite this as:
Paul E. Black, "greedy algorithm", in
Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 2 February 2005. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/greedyalgo.html