Greedy Algorithm Explained


There are various types of algorithms. Greedy algorithms are one of them. They are used to solve various problems.

Now, let us understand what a greedy algorithm is.

  1. Technically speaking, a greedy algorithm makes a locally optimum decision based on the current information available in the hopes of making a global optimum decision.
  2. What this means is, it makes a choice which seems the best decision in the short term but may not be the best decision in the long term.
  3. Basically, it lives up to its name of being greedy:- it makes a decision which is the best in the short term.
  4. To understand better lets take an example. Suppose you want to count Rs 100 using the smallest amount of coins possible. The available coins are Re 1, Re 2,  and Re 5.
  5. Now, what a greedy algorithm will do is, it will look at the amount remaining and choose the largest denomination which will not exceed Rs 100.
  6. This might lead to the total not reaching 100 or exceeding it.

To get the algorithm more clear, lets take a programming example.

The following number tree is given and you have to find a path which will give you the highest total. You can choose only one number in each row and that number has to be either directly or to one side of the number chosen in the previous row.

23

13    39

11    21    1

9      2    4    71

In this problem, if a greedy algorithm is employed, it will choose the first number 23, then 39 then 21 and then finally 9, whereas the real path which would have given you the greatest total is 2, then 39, then 1 and then 71.

Thus, a greedy algorithm gives you the wrong solution globally. For an optimal solution, you would need other algorithms such as Backtracking. This will be explaind in another post.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s