Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I wonder if dynamic programming and greedy algorithms solve the same type of problems, either accurately or approximately? Specifically,

  1. As far as I know, the type of problems that dynamic programming can solve are those that have "optimal structure". Can the same type of problems always be solved by greedy algorithms, either accurately or approximately? (I think yes)
  2. Are there optimal problems that do not have "optimal structure" and can be solved by greedy algorithms, either accurately or approximately? If yes, what characterize the type of problems that can be solved by greedy algorithms, either accurately or approximately?

Thanks and regards!

share|improve this question
    
The problems which have "optimal structure" are the ones that have the structure of a matroid. –  Harry Stern Sep 6 '11 at 15:12

4 Answers 4

up vote 11 down vote accepted

("Approximately" is hard to define, so I'm only going to address the "accurately" or "optimally" aspect of your questions.)

There's a nice discussion of the difference between greedy algorithms and dynamic programming in Introduction to Algorithms, by Cormen, Leiserson, Rivest, and Stein (Chapter 16, pages 381-383 in the second edition).

With respect to your first question, here's a summary of what they have to say. Both dynamic programming and greedy algorithms can be used on problems that exhibit "optimal substructure" (which CLRS defines by saying that an optimal solution to the problem contains within it optimal solutions to subproblems). However, in order for the greedy solution to be optimal, the problem must also exhibit what they call the "greedy-choice property"; i.e., a globally optimal solution can be arrived at by making locally optimal (greedy) choices. In contrast, dynamic programming is good for problems that exhibit not only optimal substructure but also overlapping subproblems. (This means that a particular subproblem can be reached in multiple ways. The dynamic programming algorithm calculates the value of each subproblem once and then can reuse these every time the algorithm revisits them.)

They then give the example of the 0-1 knapsack vs. the fractional knapsack problem here. Both exhibit the optimal substructure property, but only the second also exhibits the greedy-choice property. Thus the second one can be solved to optimality with a greedy algorithm (or a dynamic programming algorithm, although greedy would be faster), but the first one requires dynamic programming or some other non-greedy approach. See also Henry's example in the other answer.

It may also be helpful to read the following, which is the heart of their discussion of the difference and which I quote in full (emphasis mine):

In dynamic programming, we make a choice at each step, but the choice may depend on solutions to subproblems. In a greedy algorithm, we make whatever choice seems best at the moment and then solve the subproblems arising after the choice is made. The choice made by a greedy algorithm may depend on choices made so far, but it cannot depend on any future choices or on the solutions to subproblems. Thus, unlike dynamic programming, which solves the subproblems bottom up, a greedy strategy usually progresses in top-down fashion, making one greedy choice after another, iteratively reducing each given problem instance to a smaller one.

Basically, then, dynamic programming solves subproblems first and then uses the solutions to subproblems to construct solutions to larger problems. Greedy algorithms take on the entire larger problem first, and each greedy choice reduces the larger problem to a smaller subproblem. Thus the two kinds of algorithms are sort of inverses of each other.


With respect to your second question, here's another quote from CLRS (p. 380):

How can one tell if a greedy algorithm will solve a particular optimization problem? There is no way in general...

share|improve this answer

To answer your first question, there are problems which can be solved by dynamic programming but not satisfactorily by a greedy algorithm.

Take for example a Wikipedia example for finding a shortest path.
enter image description here

where the wavy lines have been calculated earlier by dynamic programming. The shortest overall path is clearly the top route, but a greedy algorithm would take the middle route since $2 < 5$. The values can be altered so that the greedy solution is not remotely close to the result from dynamic programming.

share|improve this answer
    
Thanks! But I asked a different question in my post. Note that when saying greedy algorithms can solve a problem, I mean either approximately or accurately. In the approximate case, the solution can be far from the optimal. –  Tim Sep 6 '11 at 13:14
    
@Tim: I would say that a purported solution which is completely wrong is not approximate. Otherwise you end up saying that any path is an approximation to the shortest path. –  Henry Sep 6 '11 at 13:20
    
I don't mean approximation to be that wrong/mismatching, but sub-optimal instead. For example, I think no one will use greedy algorithms to solve quadratic programming problems, because greedy algorithms are not supposed to. So my post actually asked what kind of problems greedy algorithms can supposedly apply to, possibly sub-optimally but not in a wrong/mismatching way, and if this kind of problems is the same as the kind of problems that can be solved by DP? –  Tim Sep 6 '11 at 13:30
1  
This is a poorly chosen example. Dijkstra's algorithm is greedy, so shortest paths is not a case that can be solved by DP but not via greedy. It just can't be solved by the particular greedy algorithm described in this answer. –  SigmaX Aug 15 at 0:03

I don't know how to put this formally, but when a problem has the notion of feasibility, it may be that a greedy algorithm will be unable to find a feasible solution. In your path example, the greedy algorithm could lead you into a dead end, or perhaps (not sure) an endless loop.

share|improve this answer

Greedy Algorithm focus on achieving the local optimal solution, while dynamic programming achieves global solution. Greedy pick the "current" best solution, while dynamic always achieves the best optimal solution.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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