A greedy algorithm is an algorithm that repeatedly makes the best choice at the current moment. In more fancy speak (quoting from Wikipedia): “A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage.”
For many problems (though far from all!) this happens to then also result in the right overall solution! Let’s see some examples of this.
<aside> 📝
<aside> 📝
But, is the previous exercise solution optimal?
First, we may want to answer the question of Why is there an optimal solution at all? Given n campsites, and the assumption that from every campsite there is at least one at most $C$ km away, we are looking for some subset of campsites to get to Copenhagen.
From R&L we remember that there are $2^n$ possible subsets (so a finite amount), from which not all solutions are feasible. However, if we can get to at least one campsite from every campsite and our first campsite is at distance $0$ and our last at distance $L$ (as defined by the question), then there must be at least one feasible solution.
In this finite set of feasible solutions, we can compute the size of each solution, simply as the number of campsites chosen. As a result there must be a (set of) solution(s) that have the smallest size, these are optimal solutions.
Now we want to check if this greedy solution is optimal. There are multiple ways to prove this.
Let’s do proof by Induction (Greedy stays ahead). First, we need to prove the lemma:
We can now use this Lemma to prove that this Greedy solution is optimal (Theorem). For example, by using proof by Contradiction:
