40 Algorithms Every Programmer Should Know

Using a brute-force strategy

The first solution that comes to mind to solve the TSP is using brute force to come up with the shortest path in which the salesperson visits every city exactly once and returns to the initial city. So, the brute-force strategy works as follows:

1. Evaluate all possible tours.

2. Choose the one for which we get the shortest distance.

The problem is that for n number of cities there are (n-1)! possible tours. It means that five cities will produce 4! = 24 tours and we will select the one that corresponds to the lowest distance. It is obvious that this method will only work since we do not have too many cities. As the number of cities increases, the brute-force strategy becomes unstable due to a large number of permutations ...