Blogging after quite a long time. I had thought of plenty of topics to write about but could not get myself to sit down and write.This blog post is titled 'The greedy algorithm' and is sure to make itself look like a geeky post. Some computer science jargon it would seem. But no, its just that analogy of the way this algorithm operates and the way some people behave appealed to me.
So to get started, lets first quickly understand what greedy algorithm is. Greedy algorithm is one of the strategies used to solve combinatorial optimization problems in computer science.Combinatorial optimization is broadly finding an optimal object from a finite set of objects
e.g.
Map Coloring: Colour different regions of a map such that no two adjacent regions have same colour and you use the fewest number of colors. Here greedy algorithm can often give you good results by choosing one color, and coloring as many regions as possible with that color before going on to another color. You proceed with the next color in the same way, not going to a third color until there are no regions that can be colored with the second color
Travelling salesman problem - Given a list of cities and their pairwise distances, the task is to find the shortest possible route that visits each city exactly once and returns to the origin city.
The greedy strategy is to make the best possible locally available choices at each stage and go to the next stage.Locally available best means that a particular choice 'a' made by this algorithm is best when we are at X stage of the problem,at this stage the entire structure of the problem is not visible to us. So making that choice 'a' we go to X+5. We come to know that 'a' was not actually the best choice 'b' which was not best at stage X would have been actually better but there is no way the mistake can be corrected. So greedy algorithm in such situation do not give you the optimal solution [ read optimal = best]
All this while you must have got a feeling that you are sitting in a computer science class and wondering why the hell you are supposed to know all this.I many times hear computer engineers saying this is 'theoretical knowledge' not of any practical value.Now from where does all this 'practical knowledge' come? It comes from theory, and how is theory formed from varied practical studies done by different people at different points in time. So I think dividing knowledge in to theoretical and practical is pure bullshit but I will not digress.
So now I come to the point- I have observed some humans are committed to employ greedy algorithm to the decisions of their life. How ? I will explain.
I will give three real life examples of decisions which are in increasing order of importance
Example 1:
Problem statement : Get the best possible dress from a shop for yourself
You go to a shop to buy clothes the shopkeeper shows you some dresses you notice that lady next to you has got a better dress in front of her. [Why do I take example of a lady, as ladies have the core quality of jelaousy packed in them which is needed to get in to the situation I am going to explain]. So you with all your smartness apply some tactics make sure she doesnt buy that dress and you without much thinking buy it.But just when you have paid your bill and are about to leave the shop you see that that lady ( the same one whom you outsmarted!) has got a better dress than what you smartly have bought.Since you have fixed budget you cannot buy that dress now. So you inspite of all your percieved smartness you are left with a suboptimal [ read: mediocre] choice.
Example 2:
Problem statement : Get your kid the best possible education.
You want to get admission to a school for your kid.You go to the best percieved school in the town pay them a hefty bribe [ Read building fund, charitable donation, whatever pleases you] Now this school imposes too much of its rules on how kids should study and put in place lot of unnecessary crap [ X day,Y day, cooking session, gardening session etc etc] which is actually not imparting required knowledge to your child. Your kids reaches 4th standard and cannot multiply / divide two numbers reliably. You see that your neighbors kid who goes to a very ordinary school can easily do this.
You scratch your head - What went wrong ?
Example 3 :
Problem statement: You want to marry the best guy in the world.
You 'search' for a best guy- i.e.
Best education,
Best salary,
Best looks,
No in-laws for you to live with.
This best guy too wants to marry you, and thus you get married. But in some time you come to know you two dont get along well.Because you two are polar
opposites. when you want piping hot coffee, he craves for a ice-cream and so on. So to spend time with each other is kind of a formality which of course you don't enjoy. You wonder what went wrong ? my choice was best ..
Answer to examples 1 2 & 3 : Locally optimal choice is not guaranteed to be globally optimal. In a non geeky language, you need to rise higher and view the problem in its entirety. From there you can see which is the ultimate best choice at a particular stage that will give overall best solution to the entire problem in the end.
Note: Above views expressed should be solely attributed to me, If you think otherwise, I dont want to challenge you.
