Hi! It’s me again. I can see you’re hungry for more graph theory. Me too!

Sometimes, when a problem is too complex to solve, approximate algorithms are used. Approximate algorithms provide a solution close to the exact solution, but in a much shorter time. One example of approximate algorithms are greedy algorithms.

Principle

The purpose of a greedy algorithm is to approximate the solution to a problem by a succession of locally optimal solutions. To illustrate this, let’s consider the traveling salesman problem, the TSP, which we’ve seen is a complex problem to solve.

Don’t forget, this algorithm is only one example of a greedy algorithm to answer the TSP. As well as systematically choosing the nearest neighbor, which was the example we’ve just seen, other heuristics can be used. Here are some examples:

You can choose the path of minimum length by exploring remaining vertices ? If , then this is the simple greedy algorithm we have just seen,

You can choose to go towards a dense area of a maze where there’s many pieces of cheese to be found,

Or, you can choose to randomly launch several possible searches, and retain the best option.

A case where the greedy algorithm is optimal

By looking for all possible combinations, we can see that this is indeed the optimal solution. To show this, it’s enough to notice that each coin has a value at least equal to twice the coin of lower value. This means that it’s always going be more efficient to give priority to the higher value piece, because one piece will be returned instead of several.

Concluding words

To recap, this lesson has introduced you to greedy algorithms to find approximate solutions to complex problems such as the TSP.