5. Algorithmic Thinking Series — Greediness Is All It Takes

Greediness is natural; we, as individuals, inherently strive to achieve the maximum gain. However, we tend to become impatient and myopic. What may seem most beneficial in the immediate moment might not necessarily be the best choice for our long term.

Anyway, ultimately, greed is the driving force behind our decisions and problem-solving approaches. The key lies in being smart about how we navigate and apply our greedy tendencies, whether we apply them immediately or delay them. Immediate gratification doesn’t always yield optimal results, as the environment in which we operate is often complex and does not conform to our whims and fancies at every step. Your previous actions make an impact on your future options. Taking a step back and examining the bigger picture proves to be a more insightful approach.

While it’s true that, in some instances, the strategy aiming for immediate gratification aligns with the whole picture as well, this isn’t a universal truth. Just because a person with myopia can see some objects doesn’t mean they don’t need glasses. What provably works is adopting a broader perspective, considering the larger context, planning, and applying it only in later scenarios where greediness is guaranteed to be the best strategy. In the real world, greedy strategies (this is the term used for strategies that seek immediate best rewards) don’t always guarantee success.

We use the robot tour example from here, to illustrate that although greed may be lucrative in certain scenarios, blindly following it is not a foolproof strategy and may not satisfy our “greed” in the long run.

Basically, here, a robot wants to join all the points given to it on a plane in order into one cycle in the minimum amount of time. Starting from a point, a naturally greedy, near-sighted approach is to join the nearest point one sees and continue it till all the points are joined. Here, we will use proof by contradiction to prove that this method is incorrect. So, we use the example below to show how choosing the nearest point might not be the optimal solution. Here, starting from point 0, we see a wasteful to-and-fro movement of the robot when a straight line and and final closing line from start to end would have sufficed.

Let us understand where we went wrong with this. We made a subtle assumption here. We assumed that the line joining a point to its nearest neighbor at any stage of the algorithm should be a part of the optimal solution. Why did we think so? Maybe because there is a notion where we think adding up small pieces gives us a small total as well. However, we need to understand that this problem is not just adding small pieces. It is adding up small pieces, but in each step, we do not have all the choices; the choices of points we have at any step are dependent on what points we have chosen till then, and hence, it is possible to limit ourselves to a very poor set of choices by acting hastily earlier while we might have been better off with a different sequence of actions till now. The other notion that could have prevailed is to think that joining two close points directly should be better than joining them via a path with intermediate points, which would obviously be longer, but here we make the mistake of comparing two things that do not do the same task at all. The line that directly joins two points doesn’t bother about other points, but, the path going via other points is also joining these other points. So, it is not just increasing the time taken; it also has another role that can balance out the extra time by looking out for the other points.

If we had two ways joining two points directly, one of which is greater than the other, it is clear that the shorter way will always be better. But, when two things are not doing exactly the same thing, looking at only one aspect of it greedily often leads to wrong conclusions. Striving for a proof of correctness can help avoid such mistakes. The issue is not with the greedy thought process but with the blind acceptance of its correctness. Rather, it is often a good approach to think of a simple greedy strategy and understand the loopholes; else, if you can prove that the greedy strategy works, that’s awesome. We will look into ways of proving the correctness of an algorithm in later blogs.

What about another approach? Say we join all the pairs that are closest till we have the loop. See the example below, and you can see why this also fails. Interestingly, here too, we make the same mistakes in the assumptions and wrong comparisons as the previous method.

Then, should we look at all possible orders of choosing points and take the minimum out of it? We can see that this is obviously correct as the actual solution would be in all possible orderings. However, this exhaustive search would be clearly computationally expensive.

In conclusion, while greed dictates our actions, following a purely greedy, near-sighted path may or may not be the right choice. Be greedy, but with foresight. We will look deeply into the discussed problem and more using this philosophy in later blogs.

Next Article: https://medium.com/@the.first.principle.lover/algorithmic-thinking-series-proving-correctness-by-mathematical-induction