Objectives of the Episode
In this Episode, we learn how to find the shortest path that goes through all vertices in a graph. To do so, we study the traveling salesman problem, that formalizes this objective.
We show that this problem is particularly difficult to solve, i.e., that any algorithm that can solve it has at least a certain complexity. To do this, we introduce the notion of complexity classes, and present the most standard ones.
Articles to study before the Lab
- The traveling salesman problem.
- Bruteforce and backtracking to solve NP-complete problems.
- Problem complexity and NP-completeness.
Work to do for the next episode
- Finish the implementation of the program in Lab 5;
- Study the articles of Episode 6;
- Be prepared for the 5-minute interview during the next Lab, in which you’ll have to present the work done in Labs 4 and 5.
Important! It is important to be prepared for this interview (see evaluation sheet for details). You should have your programs ready for a demo, and have your codes already open not to lose time searching for them. Having figures ready (if you have some) is already a good way of saving time. Remember that 5 minutes is extremely short.