-1
$\begingroup$

In (Sniedovich 2006) "Dijkstra's algorithm revisited: the dynamic programming connexion", Sniedovich provides us another interpretation of Dijkstra's algorithm as a dynamic programming implementation. By curiosity, I found the historical book of Bellman 1954: "Dynamic Programming", in which Bellman bases Dynamic Programming on the following Principle of optimality (page 84):

An optimal policy has the property that whatever the initial state and initial decision are, the remaining decisions much constitute an optimal policy with regard to the state resulting from the first decision.

This is the core of dynamic programming while my feeling is that it's exactly the same as the "Principle of Greed".

So the question is, are DP and Greedy algorithms just two different views of exactly the same thing? Or let's say that they share the same philosophy? If the answer is no, what are the main differences between them?

$\endgroup$
3
$\begingroup$

The main difference, in my view, is that DP solves subproblems optimally, then makes the optimal current decision given those sub-solutions. Greedy makes the "optimal" current decision given a local or immediate measure of what's best.

Greedy doesn't reason about the subsequent choices to be made, so its measure of what's best is shortsighted and might be wrong. For example, a greedy pathfinding algorithm might always advance directly toward the target, since at each step this decreases the distance left to be traveled the most. But then it might run into a barrier and have to travel all the way around, resulting in a bad solution.

$\endgroup$
  • $\begingroup$ Nice comparison. When making the current decision, DP aims to finally arrive to an global optimal solution while GA (greedy algorithms) does not consider the potential impact on subsequent decisions. However, depending on the problems, the two ideologies may coincide as for the Dijkstra's algorithm. Let's see if there will be more answers. $\endgroup$ – Leo Feb 28 '16 at 13:38
  • $\begingroup$ @Leo I would not consider Djikstra's algorithm an instance of a greedy algorithm. Another feature of greedy is that it makes an immediate irrevocable choice at the current step. Djikstra's is willing to update or throw away past decisions when it finds better ones. $\endgroup$ – usul Feb 28 '16 at 14:43
  • $\begingroup$ It's true that if i'm asked to provide a greedy algorithm for the sortest path problem, I'll not give Dijkstra's algorithm! :-D It may be interesting to read Sniedovich 2006, since he stated that Dijkstra's has been generally considered as a greedy algorithm. $\endgroup$ – Leo Feb 29 '16 at 10:01
  • $\begingroup$ @Leo, it's interesting, but I don't see great support for that label. It does have a greedy component in the choice of which node to explore next (this is referenced as the greedy part of Dijkstra's in the paper), but I would argue it is not greedy in how it chooses its solution. $\endgroup$ – usul Feb 29 '16 at 14:07
  • $\begingroup$ perhaps you are right, Dijkstra's is not SO greedy especially when the current decision is somehow based on previous ones! $\endgroup$ – Leo Mar 7 '16 at 8:45
2
$\begingroup$

Dynamic programming is not a greedy algorithm. It just embodies notions of recursive optimality (Bellman's quote in your question).

A DP solution to an optimization problem gives an optimal solution whereas a greedy solution might not.

$\endgroup$
  • $\begingroup$ Thanks for the reply. If we read carefully the optimality principle of dp, there is obviously a greedy thinking there no? Consider the bottom-up setting of dp, at each level we are trying to construct a larger solution to the best (so greedy), and at that point dp is rather a greedy algo to the optimality. $\endgroup$ – Leo Feb 27 '16 at 21:40
  • $\begingroup$ @Leo. I don't think so. Let's take the example of a DP with n stages. Then DP (n) = min (DP(n-1,t), c(n-1,n,t)) where c(n-1,n, t) is the cost of going from stage n-1 to n via option t. So we are looking at not only stage n-1 but also the stages before it indirectly through DP(n-1,t). In this sense I think it's not greedy $\endgroup$ – wabbit Mar 4 '16 at 4:18
  • $\begingroup$ Thanks @Wabbit for the explanation, it's now clearer for me on the difference between the two. A decision in DP is always based on the information of previous decisions while GA only makes decisions based on its local view! $\endgroup$ – Leo Mar 7 '16 at 8:41

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.