Greedy Algorithms

A greedy algorithm is a simple, intuitive algorithmic paradigm that follows the problem-solving heuristic of making the locally optimal choice at each stage with the hopes of finding the global optimum.

Characteristics

• Heuristic

• Local optimum

• Intuitive

• No long term planning

• Exact when the greedy-choice property is justified; otherwise it may be approximate and may not find the best solution

• Often efficient, but runtime depends on the problem and implementation

Relationships with other paradigms

Greedy algorithms and backtracking are both decision-making paradigms in algorithm design, distinguished by their approach to finding solutions.

Greedy	Backtracking
Exact when justified; otherwise may be approximate	Exact for the feasibility search when the pruning test is sound
Make a decision	Make a decision
Never look back	Look back
No long term planning	Long term planning
Often efficient; no universal runtime ranking	May explore many candidates; pruning can reduce the search
May fail to find the best solution	Can find one or all feasible solutions; it finds the best only when configured to retain and compare candidates

Application Domain

Solve Optimization (find best) problems. Many combinatorial optimization problems can be solved by a greedy algorithm.

• Graph problems

  • Shortest path: Dijkstra’s algorithm

  • Minimum spanning tree: Prim’s algorithm, Kruskal’s algorithm

  • Graph coloring

• Bin packing problem

• Activity selection problem

• Fractional knapsack problem

• Huffman coding

Example Problems

• Greedy Solution to Bin Packing Problem
  • Bin Packing Problem
  • Algorithms to Solve Bin Packing Problem
  • Baseline Solution
  • Greedy Solution
• Greedy Solution to Huffman Coding Problem
  • Huffman Coding
  • Characteristics
  • Applications
  • Prefix Coding Tree
  • Example coding trees
  • Algorithm to build a Huffman coding tree
  • Steps to build the example tree