Greedy Algorithms

Greedy Algorithms follow a problem solving approach wherein they make the locally optimal choice at each stage, with the hope of finding a global optimum.

The focus is, however, on finding the local optimums at each step, regardless of whether a global optimum is ever obtained.

The image below depicts the result of a greedy algorithm that needed to find the largest possible sum, starting from the root. It focused on choosing the maximum value at each step, leading to a solution that wasn't globally optimal.

The image below depicts the globally optimal solution (in green).

Pros of Greedy Algorithms:

  • simple
  • easy to implement
  • reasonable complexity

Cons of Greedy Algorithms:

  • may not result in a globally optimal solution for any given problem

Where do we use Greedy Algorithms?

Problems that can be solved using Greedy Algorithms satisfy the following properties:

  • Greedy choice property: from a local optimum we can reach a global optimum, without having to reconsider the decisions already taken
  • Optimal Substructure: an optimal solution can be constructed efficiently from the optimal solutions of its subproblems

A Greedy Algorithm never reconsiders its choices!

Some common problems solved using the greedy approach include:

  • Activity Selection problem
  • Fractional Knapsack Problem
  • Minimum Number of Coins
  • Huffman Coding
  • Job Sequencing problem
  • Kruskal's Minimum Spanning Tree
  • Prim's Minimum Spanning Tree
  • Dijkstra's Shortest Path problem

results matching ""

    No results matching ""