Determine if the optimal solution can be solved using the greedy algorithm.

Question

In most cases, the confusing fact is whether you should look for an exhaustive search (dynamic programming or backtracking or brute force) to solve the problem or go for a greedy approach.

I'm not talking about using greedy to determine the best possible solution, I'm talking about using greedy to find a "solution." I am trying to get some standard ways by which I can check if a problem can be solved with a greedy approach. Like the optimal substructure, memorization for dynamic programming. And no specific problems are related.

Is there any evidence of induction that I can do to decide if a greedy approach will always give a better solution?

Answer 1

Usually

To prove that the optimization problem can be solved using a greedy algorithm, we need to prove that the problem has the following:

• Optimal property of a substructure : an optimal global solution contains optimal solutions to all its subtasks.

• Property of greedy choice : a global optimal solution can be obtained by a greedy choice of a locally optimal choice.

---

Example

Consider the classical problem of choosing activity . We have a set S of n actions, each of which has a start time s[i] and an end time e[i] . We want to select a subset of S so that the selection maximizes the number of non-overlapping events .

This problem can be solved using a greedy algorithm , but how can we prove that?

We need to show his exhibits:

• Optimal substructure

Consider the general activity a contained in the global optimal solution S = {A', a, A''} , where S is the global optimal solution, a is our small activity, and A' and A'' are two subtasks for finding actions up to a and after a.

If the problem has the property of an optimal substructure, the optimal solution for subtasks A' and A'' should be contained in the global optimal solution S

It is true, but why?

Assume that the optimal solution for subtask A' not in S Then we could substitute the optimal one for A' , say S' , in A to get a new global optimal solution, which is better than S But S was a global optimal solution! Contradiction.

• Greedy choice :

We need to prove that our greedy choice (to choose an action that ends first) is the right one.

Let B be a subtask. Let b be the action of subtask B , which ends first, so b is our (first) greedy choice. We need to prove that b enters into some optimal solution for B

Let X be the optimal solution for subtask B Let x be the operation in X that ends first.

• If b = x, then b is in X , the optimal solution for B , and we have shown that the greedy choice is included in the optimal solution.

• If b! = X, then we have this end_time[b] < end_time[x] .

  Since b is our greedy choice (that is, an activity that ends primarily in subproblem B ), we can replace X with b in X to get another optimal solution: X' = (X \ {x}) U {b} . X' is optimal because it has the same number of actions X , and X is optimal, in which case b is in X' , the optimal solution for B

Thus, our greedy choice of B included in some optimal solution for B in one case.

---

Matroids

In addition, there is a powerful mathematical theory that can, in some cases, be used to mechanically prove that a particular problem can be solved using the greedy approach.

In short:

• You can define a specific combinatorial structure named matroid .

• Some intelligent person has proved in the past that these matroids have the Optimal Substructure property and the Greedy Choice property .

• This means that you can run the greedy algorithm in your optimization and it will find the optimal solution. You only need to verify that your problem is defined on the matroid structure .

Further information on this can be found here .