Introduction
Given a problem, finding a procedure that brings to the right solution can be a tough task. Programmers know the feeling of believing to have solved a problem by writing down an algorithm, but then realize that it does not work perfectly in every situation, most likely because built focusing on a specific scenario instead of looking at the general case.
This is presumably true when working on optimization problems where the goal is to find out the best possible solution to the given problem.
An example of the optimization problem is known as TSP, an acronym standing for Travelling salesman problem, where you are given a set of vertices and you must find the shortest path connecting them all by visiting each vertex just once. To make things clearer, let's see the following set of vertices:
The scenario consists of the 4 vertices of a square. An approach could be to randomly choose a vertex as a starting point and move to the nearest unvisited vertex. Once visited, remove the vertex from the set of unvisited vertices and repeat the approach until all vertices have been visited. At this point, we connect with an edge the last visited vertex with the first one. In pseudocode it would be something like:
Pick a random vertex v0 from the set of unvisited vertices V
v = v0
Mark v as visited and remove from V
Until V is not empty:
Choose the point w as the nearest point to v
Visit w and remove it from V
v = w
Connect v with v0
Following this approach, we would find the following solution to the previously defined scenario:
where we defined the path A->B->C->D->A. The solution is optimal and we could think that such an approach is actually the right algorithm to solve the TSP problem. But let's apply the same approach to the following scenario where we pick vertex A as the starting vertex:
As you can see, the solution is not optimal. You might argue that we could always choose the leftmost vertex as starting point instead of picking randomly, and it would work fine for both the scenarios depicted above. But what about the one below?
As you can see, it is evident how the method is doomed to fail at some point. This procedure is indeed not an algorithm, but a heuristic, known as the nearest neighbour heuristic.
What is an algorithm?
To understand the difference between algorithms and heuristics we need to give some definitions. So, when can we consider a procedure eligible to be named "algorithm"?
An algorithm is a procedure with a finite number of steps that always produce a correct solution for a given problem.
Let's break down this definition. First, an algorithm must bring to a solution in a limited number of steps. The reason for this definition lies in the fact that algorithms must produce a solution on finite machines (e.g. computers) which have limited time and limited space. Think for example to the problem of defining π: would you choose between an algorithm that produces all the digits of π but never ends or would you pick one producing only the first 100 digits of π but ends after some milliseconds? I would go for the second option.
Second, an algorithm needs a proof of correctness, which is a demonstration, based on a set of hypothesis, that a procedure cannot lead to an incorrect result for a given problem. They are usually defined in mathematical language and are very complex to make. We are not going in the details of demonstrating correctness, but you can have an example watching this video:
https://www.youtube.com/watch?v=SElE4RlAji0
What is a heuristic?
On the other side, a heuristic can be defined as follows:
An heuristic is a procedure for solving a problem without proof of correctness.
Demonstrating incorrectness is easier than doing the inverse. It only requires to find a counter-example: indeed nobody could claim for correctness after a counter-example has been found. If you look back at what we've done before, it's exactly the process of showing incorrectness.
Does this mean that heuristics are wrong and useless?
Absolutely not. On the contrary they are widely used for finding an approximate solution to problems whose exact solution would be impossible to find for time or space constraints. The TSP problem is again a valid example: as a combinatorial NP-problem, its exact solution can only be found with a brute-force search algorithm, which has an O(n!) complexity.
How to find counter-examples
Finding counter-examples is an essential skill for developers, as it speeds up the process of spotting weaknesses in the design phase of an algorithm, which usually starts with the definition of a greedy heuristic that is refined fail after fail until it starts looking more and more like an algorithm. This skill can be useful in many situations, from work to interviews. Thus, let me give some tips in the hunt for counter-examples:
-
Hack the greedy rules: greedy heuristics are usually based on some basic choices to move from a state to the next until a solution has been found. These choices often give a good starting point for our hunt, thus we could focus on them to find a valid counter-example. Think at the rule "...always take the leftmost..." proposed in the TSP heuristic and at the proposed counter-example;
-
Go for a tie: greedy heuristics move forward chasing for differences. What if we present a scenario where there are no differences? The approach could fail and the just found counter-example would be useful to improve the procedure. In the case of the TSP heuristics based on the "...always take the leftmost..." rule, we could for example present the following scenario where no point is on the left of the others:
- Work on extremes: greedy heuristics can define bounds to pick the next move to perform. If so, there's a good chance that the counter-example we're seeking sits on the bound: what if we present a scenario where we reach this bound? Does the greedy approach handle it? Does it give a correct result?
Conclusion
Algorithm design is a tedious refinement process that can require a lot of time. Improving the ability to spot algorithm weaknesses sharpens intuition and allows to be faster, write better algorithms and be more productive.
In this post we depicted the difference between heuristics and algorithms, focusing on the process of spotting counter-examples to better distinguish between what is indeed an algorithm solving a problem and what is a heuristic solving just a specific instance of that problem. Stay tuned for the next post!
Sources
- The Algorithm Design Manual (Skiena)
Also published here.
