25
$\begingroup$

I have a greedy algorithm that I suspect might be correct, but I'm not sure. How do I check whether it is correct? What are the techniques to use for proving a greedy algorithm correct? Are there common patterns or techniques?

I'm hoping this will become a reference question that can be used to point beginners to; hence its broader-than-usual scope. Please take care to give general, didactically presented answers that are illustrated by at least one example but nonetheless cover many situations. Thanks!

$\endgroup$
23
$\begingroup$

Ultimately, you'll need a mathematical proof of correctness. I'll get to some proof techniques for that below, but first, before diving into that, let me save you some time: before you look for a proof, try random testing.

Random testing

As a first step, I recommend you use random testing to test your algorithm. It's amazing how effective this is: in my experience, for greedy algorithms, random testing seems to be unreasonably effective. Spend 5 minutes coding up your algorithm, and you might save yourself an hour or two trying to come up with a proof.

The basic idea is simple: implement your algorithm. Also, implement a reference algorithm that you know to be correct (e.g., one that exhaustively tries all possibilities and takes the best). It's fine if your reference algorithm is asymptotically inefficient, as you'll only run this on small problem instances. Then, randomly generate one million small problem instances, run both algorithms on each, and check whether your candidate algorithm gives the correct answer in every case.

Empirically, if your candidate greedy algorithm is incorrect, typically you'll often discover this during random testing. If it seems to be correct on all test cases, then you should move on to the next step: coming up with a mathematical proof of correctness.

Mathematical proofs of correctness

OK, so we need to prove our greedy algorithm is correct: that it outputs the optimal solution (or, if there are multiple optimal solutions that are equally good, that it outputs one of them).

The basic principle is an intuitive one:

Principle: If you never make a bad choice, you'll do OK.

Greedy algorithms usually involve a sequence of choices. The basic proof strategy is that we're going to try to prove that the algorithm never makes a bad choice. Greedy algorithms can't backtrack -- once they make a choice, they're committed and will never undo that choice -- so it's critical that they never make a bad choice.

What would count as a good choice? If there's a single optimal solution, it's easy to see what is a good choice: any choice that's identical to the one made by the optimal solution. In other words, we'll try to prove that, at any stage in the execution of the greedy algorithms, the sequence of choices made by the algorithm so far exactly matches some prefix of the optimal solution. If there are multiple equally-good optimal solutions, a good choice is one that is consistent with at least one of the optima. In other words, if the algorithm's sequence of choices so far matches a prefix of one of the optimal solutions, everything's fine so far (nothing has gone wrong yet).

To simplify life and eliminate distractions, let's focus on the case where there are no ties: there's a single, unique optimal solution. All the machinery will carry over to the case where there can be multiple equally-good optima without any fundamental changes, but you have to be a bit more careful about the technical details. Start by ignoring those details and focusing on the case where the optimal solution is unique; that'll help you focus on what is essential.

There's a very common proof pattern that we use. We'll work hard to prove the following property of the algorithm:

Claim: Let $S$ be the solution output by the algorithm and $O$ be the optimum solution. If $S$ is different from $O$, then we can tweak $O$ to get another solution $O^*$ that is different from $O$ and strictly better than $O$.

Notice why this is useful. If the claim is true, it follows that the algorithm is correct. This is basically a proof by contradiction. Either $S$ is the same as $O$ or it is different. If it is different, then we can find another solution $O^*$ that's strictly better than $O$ -- but that's a contradiction, as we defined $O$ to be the optimal solution and there can't be any solution that's better than that. So we're forced to conclude that $S$ can't be different from $O$; $S$ must always equal $O$, i.e., the greedy algorithm always outputs the correct solution. If we can prove the claim above, then we've proven our algorithm correct.

Fine. So how do we prove the claim? We think of a solution $S$ as a vector $(S_1,\dots,S_n)$ which corresponds to the sequence of $n$ choices made by the algorithm, and similarly, we think of the optimal solution $O$ as a vector $(O_1,\dots,O_n)$ corresponding to the sequence of choices that would lead to $O$. If $S$ is different from $O$, there must exist some index $i$ where $S_i \ne O_i$; we'll focus on the smallest such $i$. Then, we'll tweak $O$ by changing $O$ a little bit in the $i$th position to match $S_i$, i.e., we'll tweak the optimal solution $O$ by changing the $i$th choice to the one chosen by the greedy algorithm, and then we'll show that this leads to an even better solution. In particular, we'll define $O^*$ to be something like

$$O^* = (O_1,O_2,\dots,O_{i-1},S_i,O_{i+1},O_{i+2},\dots,O_n),$$

except that often we'll have to modify the $O_{i+1},O_{i+2},\dots,O_n$ part slightly to maintain global consistency. Part of the proof strategy involves some cleverness in defining $O^*$ appropriately. Then, the meat of the proof will be in somehow using facts about the algorithm and the problem to show that $O^*$ is strictly better than $O$; that's where you'll need some problem-specific insights. At some point, you'll need to dive into the details of your specific problem. But this gives you a sense of the structure of a typical proof of correctness for a greedy algorithm.

A simple example: Subset with maximal sum

This might be easier to understand by working through a simple example in detail. Let's consider the following problem:

Input: A set $U$ of integers, an integer $k$
Output: A set $S \subseteq U$ of size $k$ whose sum is as large as possible

There's a natural greedy algorithm for this problem:

  1. Set $S := \emptyset$.
  2. For $i := 1,2,\dots,k$:
    • Let $x_i$ be the largest number in $U$ that hasn't been picked yet (i.e., the $i$th largest number in $U$). Add $x_i$ to $S$.

Random testing suggests this always gives the optimal solution, so let's formally prove that this algorithm is correct. Note that the optimal solution is unique, so we won't have to worry about ties. Let's prove the claim outlined above:

Claim: Let $S$ be the solution output by this algorithm on input $U,k$, and $O$ the optimal solution. If $S \ne O$, then we can construct another solution $O^*$ whose sum is even larger than $O$.

Proof. Assume $S \ne O$, and let $i$ be the index of the first iteration where $x_i \notin O$. (Such an index $i$ must exist, since we've assumed $S \ne O$ and by the definition of the algorithm we have $S=\{x_1,\dots,x_k\}$.) Since (by assumption) $i$ is minimal, we must have $x_1,\dots,x_{i-1} \in O$, and in particular, $O$ has the form $O=\{x_1,x_2,\dots,x_{i-1},x'_i,x'_{i+1},\dots,x'_n\}$, where the numbers $x_1,\dots,x_{i-1},x'_i,\dots,x'_n$ are listed in descending order. Looking at how the algorithm chooses $x_1,\dots,x_i$, we see that we must have $x_i > x'_j$ for all $j\ge i$. In particular, $x_i > x'_i$. So, define $O^ = O \cup \{x_i\} \setminus \{x'_i\}$, i.e., we obtain $O^*$ by deleting the $i$th number in $O$ and adding $x_i$. Now the sum of elements of $O^*$ is the sum of elements of $O$ plus $x_i-x'_i$, and $x_i-x'_i>0$, so $O^*$'s sum is strictly larger than $O$'s sum. This proves the claim. $\blacksquare$

The intuition here is that if the greedy algorithm ever makes a choice that is inconsistent with $O$, then we can prove $O$ could be even better if it was modified to include the element chosen by the greedy algorithm at that stage. Since $O$ is optimal, there can't possibly be any way to make it even better (that would be a contradiction), so the only remaining possibility is that our assumption was wrong: in other words, the greedy algorithm will never make a choice that is inconsistent with $O$.

This argument is often called an exchange argument or exchange lemma. We found the first place where the optimal solution differs from the greedy solution and we imagined exchanging that element of $O$ for the corresponding greedy choice (exchanged $x'_i$ for $x_i$). Some analysis showed that this exchange only can only improve the optimal solution -- but by definition, the optimal solution can't be improved. So the only conclusion is that there must not be any place where the optimal solution differs from the greedy solution. If you have a different problem, look for opportunities to apply this exchange principle in your specific situation.

$\endgroup$
  • $\begingroup$ This is an old question, but it is the first result in Google for me. The line then we can tweak O to get another solution O∗ that is different from O and strictly better than O confuses me. If there are multiple optimal solutions, it is possible to have S != O and both still be optimal; we can tweak O to be "more like" S (creating O∗) and yet be just as good as (not strictly better than) O. $\endgroup$ – citelao Sep 8 '18 at 17:04
  • $\begingroup$ @citelao, I'm sorry to hear that it confused you. Alas, I'm not sure how to explain it more clearly. Yes, there could be multiple optimal solutions, all with the same value. That is correct. What you wrote and what I wrote are both valid; there is no contradiction. The difference is that what you wrote doesn't help prove a greedy algorithm correct; what I wrote does. I can only suggest going through what I wrote again, and see if you can figure out how what I wrote is useful. If that doesn't help, maybe find a different write-up. I realize it's tricky and confusing. $\endgroup$ – D.W. Sep 8 '18 at 18:53
  • $\begingroup$ thanks for the quick response! I missed the point where you focus on proving the algorithm if there is only a single, unique optimal solution. Since this question is about proving any greedy algorithm correct, I'd like to provide an answer for cases where multiple optimal solutions can exist. It's been a while since I studied all of this, but isn't it sufficient to prove that you can exchange each element O_i in any optimal solution O that differs from the alg. solution S with S_i and still have a solution O' that is no worse than O? $\endgroup$ – citelao Sep 8 '18 at 19:16
  • $\begingroup$ @citelao, the technique also applies to cases where there are multiple optimal solutions. I suggested focusing on the case where the optimal solution is unique only because, the first time you see this, it is easier to understand how these proofs work in that setting. But the same strategy works even if there are multiple optimal solutions. I suggest studying this, making sure you understand how it works when there is a single optimal solution, then applying it to the general case. Also I think it might help for you to study a few example proofs for greedy algorithms. $\endgroup$ – D.W. Sep 9 '18 at 0:24
  • $\begingroup$ To answer your latter question, no, that is not sufficient. That doesn't prove that S is optimal. (If you only demand that O' be no worse than O, there are cases where S is sub-optimal yet it's possible to do that kind of exchange. So proving that it's possible to achieve an O' that is no worse than O doesn't prove anything about whether S is optimal and doesn't prove the greedy algorithm is correct. I suggest studying the method described in the answer a bit more. It's tricky. Proof by contradiction is often tricky to understand.) $\endgroup$ – D.W. Sep 9 '18 at 0:26
14
$\begingroup$

I will use the following simple sorting algorithm as an example:

repeat:
  if there are adjacent items in the wrong order:
     pick one such pair and swap
  else
     break

To prove the correctness I use two steps.

  • First I show that the algorithm always terminates.
  • Then I show that the solution where it terminates is the one I want.

For the first point, I pick a suitable cost function for which I can show that the algorithm improves it in every step.

For this example I choose the number of inversions in the input list. An inversion in a list $A$ is a pair of entries $A[i]$, $A[j]$ such that $A[i] > A[j]$ but $i<j$. The number of inversions is always non-negative and a sorted list has 0 inversions.

Clearly swapping two adjacent items $A[i]$, $A[i+1]$ that are in the wrong order removes the inversion $A[i],A[i+1]$ but leaves any other inversion unaffected. Hence the number of inversions is reduced in every iteration.

This proves that the algorithm eventually terminates.

The number of inversions in a sorted list is 0. If all goes well the algorithm will reduce the number of inversions down to 0. We only need to show that it doesn't get stuck in a local minimum.

I usually prove this by contradiction. I assume that the algorithm stopped, but the solution is not correct. In the example, this means the list is not yet sorted, but there are no adjacent items in the wrong order.

If the list is not sorted, there must be at least two items that are not in the correct position. Let $A[i]$ and $A[j]$, $i<j$, $A[i]>A[j]$ be two such items s.t. the difference between $i$ and $j$ is minimal. Since the algorithm didn't stop, they are not adjacent, so $i+1 < j$. Because we assumed minimality, $A[i]<A[i+1]$ and $A[i+1]<A[j]$, but then $A[i]<A[j]$ and we have a contradiction.

This proves that the algorithm only stops when the list is sorted. And hence we're done.

$\endgroup$
  • $\begingroup$ The techniques explained are so general that they virtually have nothing particular about greedy algorithm, the topic of this question. $\endgroup$ – Apass.Jack Aug 5 '18 at 7:38

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.