A greedy algorithm is any algorithm that follows the problem solving metaheuristic of making the locally optimum choice at each stage with the hope of finding the global optimum. Image File history File links Greedy_algorithm_change_diagram. ... In mathematics, computing, linguistics, and related disciplines, an algorithm is a finite list of well-defined instructions for accomplishing some task that, given an initial state, will terminate in a defined end-state. ... Problem solving forms part of thinking. ... A metaheuristic is a heuristic method for solving a very general class of computational problems by combining user given black-box procedures — usually heuristics themselves — in a hopefully efficient way. ...

For example, applying the greedy strategy to the traveling salesman problem yields the following algorithm: "At each stage visit the unvisited city nearest to the current city". The traveling salesman problem (TSP), is a problem in discrete or combinatorial optimization. ...

1. A candidate set, from which a solution is created
2. A selection function, which chooses the best candidate to be added to the solution
3. A feasibility function, that is used to determine if a candidate can be used to contribute to a solution
4. An objective function, which assigns a value to a solution, or a partial solution, and
5. A solution function, which will indicate when we have discovered a complete solution

Greedy algorithms produce good solutions on some mathematical problems, but not on others. Most problems for which they work well have two properties: A mathematical problem is a problem that can be solved with the help of mathematics. ...

Greedy Choice Property 

We can make whatever choice seems best at the moment and then solve the subproblems that arise later. 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 solution.

Optimal Substructure 

A problem exhibits optimal substructure if an optimal solution to the problem contains optimal solutions to the sub-problems.

When greedy-type algorithms fail 

For many other problems, greedy algorithms may produce the unique worst possible solutions. One example is the nearest neighbor algorithm mentioned above: for each number of cities there is an assignment of distances between the cities for which the nearest neighbor heuristic produces the unique worst possible tour (G. Gutin, A. Yeo and A. Zverovich, 2002). For more information, see the references.

In mathematics and computer science, dynamic programming is a method of solving problems exhibiting the properties of overlapping subproblems and optimal substructure (described below) that takes much less time than naive methods. ... Figure 1. ...

Applications

For most problems, greedy algorithms mostly (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 which prevent them from finding the best overall solution later. For example, all known greedy 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. A 3-coloring suits this graph, but fewer colors would result in adjacent verticies of the same color. ... In complexity theory, the NP-complete problems are the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. The reason is that if you could find a way to solve an NP-complete problem quickly, then you could use...

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 optimisation methods like dynamic programming. Examples of such greedy algorithms are Kruskal's algorithm and Prim's algorithm for finding minimum spanning trees, Dijkstra's algorithm for finding Single-Source Shortest paths, and the algorithm for finding optimum Huffman trees. Kruskals algorithm is an algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph. ... Prims algorithm is an algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph. ... The minimum spanning tree of a planar graph. ... Dijkstras algorithm, named after its discoverer, Dutch computer scientist Edsger Dijkstra, is a greedy algorithm that solves the single-source shortest path problem for a directed graph with non negative edge weights. ... In computer science, Huffman coding is an entropy encoding algorithm used for data compression that finds the optimal system of encoding strings based on the relative frequency of each character. ...

The theory of matroids, and the more general theory of greedoids, provide whole classes of such algorithms. In combinatorial mathematics, a matroid is a structure that captures the essence of a notion of independence (hence independence structure) that generalizes linear independence in vector spaces. ... In combinatorics, a greedoid is a type of set system. ...

Greedy algorithms appear in network routing as well. Using greedy routing, a message is forwarded to the neighboring 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 tables. This article is about routing (or routeing) in computer networks. ... Geographic routing refers to a family of techniques to route data packets in a communication network. ... A mobile ad-hoc network (MANET) is a self-configuring network of mobile routers (and associated hosts) connected by wireless links—the union of which form an arbitrary topology. ... In network theory, small world routing refers to routing methods for small-world networks. ... Distributed hash tables (DHTs) are a class of decentralized distributed systems that provide a lookup service similar to a hash table: (name, value) pairs are stored in the DHT, and any participating node can efficiently retrieve the value associated with a given name. ...

Examples

• 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. Unfortunately, the artificial intelligence does not account for obstacles, so the demo mode often ends quickly.

Macintosh, also known as Mac, is a family of personal computers manufactured by Apple Computer, Inc. ... Crystal Quest is an action computer game for the Apple Macintosh and Apple IIgs. ... If a salesman starts at point A, and if the distances between every pair of points are known, what is the shortest route which visits all points and returns to point A? The traveling salesman problem (TSP) is a problem in discrete or combinatorial optimization. ... Bold text[[Link title]] “AI” redirects here. ...

References

• Introduction to Algorithms (Cormen, Leiserson, and Rivest) 1990, Chapter 17 "Greedy Algorithms" p. 329.
• Introduction to Algorithms (Cormen, Leiserson, and Rivest) 2001, Chapter 16 "Greedy Algorithms" .
• G. Gutin, A. Yeo and A. Zverovich, Traveling salesman should not be greedy: domination analysis of greedy-type heuristics for the TSP. Discrete Applied Mathematics 117 (2002), 81-86.
• J. Bang-Jensen, G. Gutin and A. Yeo, When the greedy algorithm fails. Discrete Optimization 1 (2004), 121-127.
• G. Bendall and F. Margot, Greedy Type Resistance of Combinatorial Problems, Discrete Optimization 3 (2006), 288-298.

External links

• Simple example code of Greedy algorithm, C++