Intro to Greedy Algorithms feat. Uncle Scrooge
Remember Uncle Scrooge? You might know him as Donald Duck’s rich and stingy uncle. His favorite pastime is diving into and swimming in his money. According to this 2011 Forbes article, his net worth estimate is $44.1 billion.
Let us invite him as a celebrity guest to our new game show, one similar to ‘Deal or No Deal’. We’ll call this one ‘Open Sesame’ and it will have doors instead of briefcases. There will be a twist though, more on that later.
We begin the game. “Uncle Scrooge, there are two doors. You have to choose one of them. Door 1 has $500 and Door 2 has $2000. Which one do you want?”
Uncle Scrooge cannot believe his luck; he has to make a simple choice and the money will be his! His greediness kicks in and like most of us, he chooses Door 2. Uncle Scrooge has just won $2000! Now if only life were that easy..
Consider this rich duck as the personification of Greedy algorithms. The algorithm chooses a ‘locally optimal’ solution. In other words, the solution that looks the best and most profitable at a given state. After all, who wouldn’t pick $2000 over $500?
Once Uncle Scrooge is done celebrating his win, we resume the game. Here’s a twist — not only does he win Door 2, but he also gets Door 4 with it. Had he chosen Door 1, he’d have got Door 3 along with it. But what’s behind Door 4, you ask?
Door 4 has more money! $300 to be precise. Uncle Scrooge cannot stop dancing with joy! As is customary, we need to reveal what he missed out on — what was behind Door 3.
Oh no, Door 3 has $3000! Had Uncle Scrooge chosen Door 1 (and Door 3) he’d have won $3500 as opposed to $2300 with Door 2 (and Door 4) :(
Uncle Scrooge is not happy. He feels cheated. But this is what happens with Greedy algorithms, there is no guarantee of arriving at the best overall solution. You can only cross your fingers and hope to reach the ‘global optimum’. Let’s take a deeper look at what happened:
The diagram above shows a decision tree which is nothing but a graphical representation of the different options and their outcomes. Choosing Door 1 and Door 3 is the best route to maximize gain. But when presented with just Door 1 and Door 2, the greedy algorithm (Uncle Scrooge) chooses Door 2 as the contents of Door 3 and 4 are unknown. This is the short-sighted nature of this class of algorithms and may not always lead to maximum profit.
However, in certain cases greedy algorithms may end up choosing the globally optimum solution. If Doors 3 and 4 were interchanged, the resulting decision tree would be:
In this case, the greedy algorithm would choose Door 2, the locally optimal choice (and Door 3) which would lead to a globally optimal solution.
And thus ends our tryst with greedy algorithms and Uncle Scrooge. The success of greedy algorithms depends on the nature of the problem. In some cases, being greedy and short-sighted might be like being the Grasshopper that ends up starving. At other times, greediness might work to your advantage when you get all the desserts you want at the start of an all-you-can-eat buffet before they run out of them :P
Thanks for reading! If you liked this article, consider giving applause or sharing it to recommend it to others.
Want to read more such articles? Follow me and leave a comment on what I should write next.
