(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

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 2 February 2005.

HTML page formatted Tue May 6 13:48:55 2014.

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