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
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.
Example
However, it’s not an optimal solution, as we can find a path with a smaller weight.
The TSP in everyday problems
The TSP is a recurrent problem found in many fields of computing. Here are some examples.
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 is reducible to problem if an algorithm for efficiently solving problem can also be used to solve problem . In a way, this means that when you solve problem , a part of what you’re doing can also be considered as solving problem .
More formally, reducing a problem to a problem is done by finding two polynomial algorithms and such that, if algorithm solves problem , then the concatenated algorithm solves problem .
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 is reducible to , then you can solve using an algorithm designed to solve .
This doesn’t tell you anything about the ability to solve using an algorithm designed to solve . So, we can only say that is at least as difficult as .
The meta-graph
Let’s now see how picking up all the pieces of cheese in a maze is a reduction of the TSP.
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.