Greedy Algorithm

CORE DEFINITION

A greedy algorithm is an algorithmic paradigm that follows the problem solving heuristic of making the locally optimal choice at each stage with the hope of finding a global optimum. For example, in the traveling salesman problem, if the salesman always chooses the nearest city, that is a greedy algorithm. Greedy algorithms are particularly effective for problems with optimal substructure, meaning that local optimal solutions can determine the global optimal solution. Simply put, the problem can be broken down into subproblems, and the optimal solutions to subproblems can be recursively extended to the optimal solution of the overall problem. The difference between greedy algorithms and dynamic programming is that greedy algorithms make a choice for each subproblem and cannot backtrack, whereas dynamic programming saves previous computation results and uses them to make current choices, allowing backtracking. Greedy methods can solve some optimization problems, such as finding the minimum spanning tree in a graph and Huffman coding. For other problems, greedy methods generally cannot produce the desired answer. Once a problem can be solved by a greedy method, it is usually the best approach.