Objectives of the Episode
We saw at the last Episode that the traveling salesman problem is complex to solve. However, it is possible to drastically reduce the complexity of the algorithm, provided that you are satisfied with a good-enough solution (instead of the optimal one).
We introduce in this Episode the notion of approximate algorithm. An approximate algorithm proposes a feasible solution, probably not the optimal one, but possibly close to the best solution. The advantage of a good approximate algorithm is that it runs much faster.
One category of effective approximate algorithms for the traveling salesman problem are greedy algorithms. We will see in this Episode several examples of greedy algorithms. We will also see how to compare these algorithms, taking into account both their approximation quality and their complexity.
Articles to study before the Lab
Test your knowledge of this Episode!
Lab instructions
Follow this link for the Lab contents!
Work to do for the next episode
- Finish the implementation of the program in Lab 6;
- Study the articles of Episode 7.
- Be prepared for the 5-minute interview during the next Lab, in which you’ll have to present the work done in Labs 5 and 6.
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.