Contents of the page


On this page, we’re going to talk about solving NP-complete problems with two algorithms, an exhaustive one and backtracking. At the end of the video, you should be able to implement these two algorithms to solve the traveling salesman problem.


Computing a solution

Classicaly, NP-complete problems are tackled either through:

  • exact algorithms, which are reasonably fast for small problems, 
  • or, suboptimal or heuristic algorithms, which deliver good-enough solutions, but which are not necessarily optimal.

Today, let’s explore two exact algorithms to solve the traveling salesman problem, or TSP. 

Brute force algorithm

The most direct solution to the TSP is to try all possible elementary paths, or, permutations of the n cities, and see which one is the cheapest. This is known as a brute force, or exhaustive search.

If the starting city is fixed, the number of such permutations equals $$(n-1)$$. Consequently, the calculation time, or the time it takes for the computer to solve the problem with this approach, lies within a polynomial factor of \mathcal{O}(n!).

To give some more concrete meaning to this complexity, imagine that evaluating one permutation, or one elementary path, takes 1 microsecond. The following table summarizes the calculation time when the number of cities increases. 

For example, for a problem with 5 cities, the number of possible elementary paths equals 24, and the calculation time will be 24 microseconds. Multiplying the number of cities by only 3 increases the resolution time to approximately 24 hours, and multiplying the number of cities by 10, thus increasing it to 30, will take around 3 millions of billions of centuries.

So it’s quite obvious that this algorithm becomes impractical even for only 20 cities. Let’s have a look at an example. Consider this graph.

Graph Example

The starting point for the traveling salesman is vertex v_1, and imagine for the sake of simplicity that he does not have to return to v_1 in the end. The number of solutions to explore is therefore $$(n-1)$$ if n is the number of cities.

Trying all possible solutions starting from v_1 can be done using a depth-first search, during which we keep in memory the shortest possible path encountered. So far in this MOOC, we considered DFS for which each vertex is explored only once. Here, we are interested in the case where a vertex does not appear twice on the same path, but can appear twice if in different paths. So, here we consider a variation of the DFS where the list of explored vertices is modified for the current explored branch, and not for the other branches.

The tree of all the possible paths is shown here.

Tree

The search starts on the left, by proposing the first solution v_1 \to v_2 \to v_3 \to v_4 with a cost of 16. This solution is stored in memory as the best solution identified so far. The next explored solution is v_1 \to v_2 \to v_4 \to v_3, which has a cost of 10. This solution is better than the currently known best one, v_1 \to v_2 \to v_3 \to v_4, and so this new solution is stored in memory as the current best solution. The search continues until all possible solutions have been evaluated. The output of the algorithm is solution v_1 \to v_3 \to v_4 \to v_2, which has the lowest possible cost of 7. A total of six solutions have been evaluated in this depth-first search.

Tree all

The algorithm that runs through the previous tree can be seen here.

best = infinity
def bruteforce(remaining, vertex, path, weight, graph):
  if remaining is empty:
    if weight < best:
      best = weight
      best_path = path
  else:
    for each vertex i in remaining:
      bruteforce(remaining - i, i, path + i, weight + graph[vertex][i],graph)

It is a recursive algorithm that calls itself until a stopping condition is reached. The idea behind the algorithm is to keep in memory the best possible path that has been encountered thus far, and to update it when a better or shorter one is encountered. 

The algorithm is then called as follows. 

bruteforce(vertexes_List - starting_vertex, starting_vertex, empty_list, 0, graph)

The arguments of the call are as follows: 

  • the list of vertexes (minus the starting point),
  • the initial vertex,
  • an empty list, which will contain the optimal path in the end,
  • the initial weight of this empty list, which is 0,
  • and the graph.

Backtracking solution

A quick improvement of the previous algorithm is to stop the depth search when it’s certain that the currently explored branch will not generate a better solution than the current best one. This is the case when the total weight of the edges used in the current branch of the tree is already larger than the total weight of the best solution found. This means that the branch that’s explored at each step has an influence on the overall calculation time. For example, imagine that by chance we start with the branch that generates the optimal solution. When exploring the other branches, we will abort exploring them as soon as the total weight exceeds the one found for the first branch, which will save a lot of calculation time. 

Various strategies can be used to further optimize backtracking, by preselecting which branches to examine first. As an example, we could select the branch whose starting vertex is the closest to the current vertex. 

Example

Let’s illustrate this particular backtracking approach on the same graph again, shown here. 

Graph Example

The tree of all possible paths from vertex v_1 is shown here.

Tree All

First, we try to move to its closest neighbour, which is v_4. It costs 3 to move to v_4 so our route already has a cost of 3 so far. Then we continue to v_3, which is the closest unexplored neighbor of v_4. It costs 1 more and so the total length is 4. Finally, we move to v_2 the last remaining vertex. It adds 8 to our sum and so we obtain a total of 12. We thus have a first estimation of the shortest path, which is v_1,v_4,v_3,v_2 even though this path is not optimal.

Branch 1

There is no possible movement from this configuration, so we move backwards.

Again, there are no other alternatives here, as we’ve already explored v_2 after v_3, so we continue backwards.

Now we have an alternative option, which is to go to v_2. We add the corresponding weight of 2 and obtain a partial route with a length of 5.

Branch 2

There’s only one option left, which is to visit v_3. However, this move would cost us an additional 8, which would result in a total that’s more than our previously found path with a length 12. So, we move backwards instead.

We’ve now explored all the options starting with v_1 then v_4, so we continue backwards. We now select another option when starting at v_1, which is to go to the second nearest neighbor of v_1, which is v_3. From here we go to v_4 first. And finally we go to v_2. We obtain a total length of 7, and thus update the shortest route so far.

shortest path

We go backwards. Twice. Now we have the option to go to v_2, but it would cost too much compared to our best route, so we continue backwards. From v_1 there’s only one option left: going to v_2. It would already cost 7, which is as much as our best route, so we cannot expect to find a shortest path in this direction.

So, we can conclude that the shortest route has a length of 7, and yet we’ve only explored a fraction of the trees of all possible paths.

backtracking trees

So, the backtracking solution has a much lower complexity than the brute force approach. 


The branch-and-bound algorithm

A third algorithm for solving exactly the TSP is the branch-and-bound algorithm.

The branch-and-bound algorithm explores the tree of possibilities (in the case of the traveling salesman, the tree of possible paths). To do this, it uses a Dijkstra algorithm. At each vertex it encounters, it tries to estimate an interval (as narrow as possible) estimating the length of a shorter path obtained from the branch of the tree where it currently is.

To obtain these intervals, there are several techniques.

To obtain an upper bound, it is sufficient to use a greedy algorithm, that estimates the length of the remaining path by always going to the closest vertex. This results in a path that is not necessarily optimal, but which has a length that can only be longer than that of a shorter path.

To obtain a lower bound, we can for example count the number of vertices not yet visited (let’s call this number k). In the best case, they can be visited by going through the k edges with the lowest weights. The sum of these k weights gives the lower bound. This reduction is often coarse, and it is better to look for the finest.

When the algorithm has determined several intervals (one per branch to explore), it can compare them to each other. In the case of searching for a path of minimum length, if the interval of a branch i has as its upper bound a value smaller than the lower bound of an interval of another branch j, then the subtree corresponding to j is eliminated. Indeed, there is no point in exploring the subtree corresponding to the interval j knowing that the best solution found will in any case be less interesting than the worst ones by continuing on branch i.

Complexity

The complexity of the algorithm is in the worst case the same as an exhaustive search (if the estimation of the limits does not cost too much) this is for example the case with a complete graph in which all the edges have the same weight.

In practice, having good accuracy in estimating intervals can save a lot of time. An optimal case is one of linear complexity.

Precision-performance compromise

As in the case of the approximate algorithms that we will study in Episode 5, interval estimation poses the problem of the precision-performance trade-off. Indeed, the narrower the interval, the more it will allow parts of the tree to be pruned. However, if its estimation requires an expensive calculation, it has an impact on total complexity.

It is therefore necessary to find estimates of the bounds of the intervals that offer a good compromise between computation time and accuracy.


To go further


Quiz

A bruteforce algorithm...
A backtracking algorithm for the TSP...
We consider using a backtracking algorithm for the TSP. Which of the following are true?