Video transcripts

Hi, and welcome to this lesson on algorithmics and discrete mathematics!

In today’s lecture, you will learn about the traveling salesman problem, which is probably one of the best known problems in computer science. It is also often used as a first example of an NP-Complete problem, which means that we haven’t yet identified a fast resolution algorithm.

The traveling salesman problem

Let’s begin with some basic definitions: given a set of cities and the cost of travel between each pair of cities, the traveling salesman problem, or TSP for short, is to find the cheapest way of visiting all of the cities and, optionally, returning to the starting point.

Problems such as the TSP are called « optimization problems », because the goal is to find parameters that optimize a certain quantity, which, in the TSP, is to minimize the total cost.

The TSP can be represented by a weighted graph, where the vertices represent the cities, and the weights on the edges represent the travel cost between the pairs of cities. Solving the TSP comes down to finding a path passing once and only once through all vertices of the graph and which has a minimal total weight.

Example

Let’s take an example. Consider the following graph, where the starting point is vertex v_1. Let’s consider a situation where the salesman doesn’t have to return to the initial vertex.
The path \{v_1,v_4\}, \{v_3,v_4\}, \{v_2,v_3\} has a total weight of 3 + 1 + 8 = 12. This path could potentially be a solution of the TSP.

However, it’s not an optimal solution, as we can find a path with a smaller weight.

The path \{v_1,v_3\}, \{v_3,v_4\}, \{v_2,v_4\}  has a total weight of 4 + 1 + 2 = 7, and is the shortest path starting from v_1 and passing through all the vertices of the graph. So, this is the optimal solution of the TSP for this graph.

The TSP in everyday problems

The TSP is a recurrent problem found in many fields of computing. Here are some examples.

The TSP naturally arises as a sub-problem in many transportation and logistics applications, such as, for example, planning school bus routes and picking up students from different locations. Other examples that can be modeled as TSPs include planning meal deliveries to people who are homebound and the routing of mail trucks for parcel collection.
The TSP also arises when it comes to minimizing the time and expense of a potentially long and costly journey. This is the case, for example, for satellites that have to pass through a number of different locations to carry out their missions.
The deployment of optical fiber raises the problem of serving a set of locations while limiting the construction work involved. Such a problem can usually be formalized as a TSP.
The scheduling of a machine to drill holes in an object in a manufacturing process can also be seen as a TSP. The holes to be drilled are the « cities », and the cost of travel is the time it takes to move the drill head from one hole to the next.

The TSP as a reduction for other problems

In computer science, a reduction is a method for transforming one problem into another problem, typically for which solutions are already known.

Intuitively, problem p is reducible to problem q if an algorithm for efficiently solving problem q can also be used to solve problem p. In a way, this means that when you solve problem q, a part of what you’re doing can also be considered as solving problem p.

More formally, reducing a problem p to a problem q is done by finding two polynomial algorithms alg_1 and alg_2 such that, if algorithm alg_q solves problem q, then the concatenated algorithm [alg_1, alg_q, alg_2] solves problem p.

To better understand reduction, think of language translation. Imagine you have a way to solve a problem in French, but your problem is expressed in English. A possible solution is to first translate your problem into French, solving it in French, then translating the solution back to English. This is an example of a reduction.

Let’s continue in English. No French, I promise!

Reduction is a very convenient way to quickly obtain results. For example, reduction can be used to prove that a problem can be solved by a given algorithm, or to show that a problem is at least as difficult as another one. In other words, if p is reducible to q, then you can solve p using an algorithm designed to solve q.

This doesn’t tell you anything about the ability to solve q using an algorithm designed to solve p. So, we can only say that q is at least as difficult as p.

The meta-graph

Let’s now see how picking up all the pieces of cheese in a maze is a reduction of the TSP.

Let’s consider this maze, which also shows its associated graph.
The pieces of cheese are represented by yellow vertices. Our starting position is shown in red.
It’s easy to see how determining the shortest path to collect all the pieces of cheese will somehow come down to solving a TSP. However, if we use this graph to solve the TSP, you can see that we will travel through many parasitic vertices, which don’t contain any cheese. We’d like to only go through vertices that contain a piece of cheese.
So, we propose to transform our graph to a new graph, that we call the « meta-graph ». The meta-graph’s vertices are the starting position plus the pieces of cheese. The weight between two vertices in the new graph corresponds to the length of a shortest path between corresponding vertices in the maze. If we do this for any colored vertex pair in the previous example, we get a complete graph with seven vertices. To decide how to move from one vertex to another, a routing algorithm has to be used.

Now we can solve the problem of finding the shortest route to grab all pieces of cheese. First we build the meta-graph. Then we solve the TSP on the meta-graph. Then we use routing to find the corresponding routes in the maze.

So, we concatenated three algorithms, the first and the third one being polynomial, and proved that our problem is reducible to the TSP.

Concluding words

In the next lesson, we will see how to code a solution to the TSP.




Quiz

In graph theory, the TSP corresponds to...
Reducing a problem p to a problem q involves...
The TSP processes an input that is best described as...