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 by taking the following quiz.

Lab description

In this Lab, we program a greedy algorithm that approximates finding the shortest path that goes through all pieces of cheese with finding a series of shortest paths from a piece of cheese to another.

There are multiple ways of doing so. In a first step of this Lab, we program a greedy algorithm as seen in the course. Then, we take a step back and see how we could improve it in the eventuality of a second player in the maze.

Let’s go!

Work to do for the next episode

  • Finish the implementation of the program in Lab 5;
  • Study the articles of Episode 6.