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.
Test your knowledge of this Episode by taking the following quiz.
In this Lab, we increase the difficulty once more by introducing multiple pieces of cheese in the maze.
The goal of the Lab is to program an exhaustive search of possible paths that go through all pieces of cheese, in order to find the solution to the traveling salesman problem. Then, we improve this exhaustive search using an optimization called backtracking.
Work to do for the next episode
- Finish the implementation of the program in Lab 4;
- Study the articles of Episode 5.
- Be prepared for the 5-minute interview during the next Lab, in which you’ll have to present the work done in Labs 3 and 4 (see evaluation sheet for details).
Important! It is important to be prepared for this interview. 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.