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
Work to do for the next episode
- Finish the implementation of the program in Lab 6;
- Study the articles of Episode 7.