4

I have tried a few backtracking algorithms and successfully converted them to dynamic programming by applying the concept of memoization.

Is it possible to convert every backtracking algorithm to dynamic programming?

If dynamic programming is so much efficient than backtracking, why we still use backtracking?

Sai Krishna Palagummi
  • 150
  • 1
  • 12
  • 1
    We use dynamic programming for problems that have overlapping sub-problems. Thats the criteria for a problem to be solve using dynamic programming. – Haris Jan 21 '16 at 14:25
  • Thank u Haris. But can we convert every backtracking algorithm to dynamic programming algorithm? Because backtracking generally have overlapping sub problems. – Sai Krishna Palagummi Jan 21 '16 at 14:28
  • 1
    I would solve a sodoku puzzle with backtracking, though I do not see how we could apply dynamic programming there. So I don't think the set of problems that can be solved by backtracking is a subset of the set of problems that can be solved by some sort of dynamic programming. – Glubus Jan 21 '16 at 14:29
  • 1
    Backtracking algorithms often make use of pruning, you usually can't prune in DP because you don't know what you'll need yet. (I'm excluding memoization from DP here because it's not DP, it's memoization) – harold Jan 21 '16 at 14:32
  • @Glubus Yeah that's what I am looking for i.e., possibility of conversion of a backtracking algorithm to DP. Thank u :) – Sai Krishna Palagummi Jan 21 '16 at 14:33
  • @SaiKrishnaPalagummi if you're looking for a conversion of a problem using a backtracking algorithm to DP you should focus on that problem, not on the concept of backtracking. – Glubus Jan 21 '16 at 14:34
  • But generally saying you can implement memoization/dp in any backtracking function (even though each state might be visited only once and there is no need in dp). The only problem is resources as storing all states might be simply impossible with current hardware limitations. – serhiyb Jan 21 '16 at 14:42
  • @serhiyb DP does not suggest storing all possible states, the reason to even use DP is to NOT consider all possible states. – Glubus Jan 21 '16 at 14:59
  • @harold Memoization is one of the ways to implement a dynamic program – Niklas B. Jan 21 '16 at 15:07
  • @Glubus, yes of course. I'm just considering worst case scenario. – serhiyb Jan 21 '16 at 15:09
  • @NiklasB. it is often counted. But it's the cheating trivial way, not the true way. – harold Jan 21 '16 at 15:28
  • @harold Is "cheating trivial way" just your opinion, or can you provide a citation? Every source that I've encountered, including http://stackoverflow.com/questions/6184869/what-is-difference-between-memoization-and-dynamic-programming, says that memoization counts as DP. – btilly Jan 22 '16 at 01:05
  • @btilly this has been a bit of a holy war for decades, cherry picked sources will have either viewpoint. I'm hardly alone in this. For example Loay Hany's answer [here](https://www.quora.com/What-is-the-difference-between-bottom-up-and-top-down-dynamic-programming-method), the [top answer here](http://stackoverflow.com/q/6164629/) acknowledges the war (but doesn't really take a side). I don't think it should count because it's not a special technique that deserves to have the same name as the real deal, just a simple trick. – harold Jan 22 '16 at 10:01
  • @harold I read both your links and don't see either as "acknowledging a war" let alone being a holy war. There is a large fundamental difference between memoization and tabulation. But both achieve the same fundamental optimization with the same fundamental tradeoffs. That fundamental optimization is known as dynamic programming. (Generally memoization is easier to write, tabulation is slightly more efficient.) – btilly Jan 22 '16 at 17:21
  • @btilly it's more obvious in Loay's post. Anyway memoization does not involve the "reordering" step, which generally takes a prominent place in explanations of how DP works. So it's not DP. It still avoids redundant work, but merely saving redundant work doesn't make things DP, lots of completely unrelated things also save redundant work. – harold Jan 22 '16 at 19:47
  • @harold Loay's post just seems sloppy with terminology. But you gave me enough of a tip to search for "dynamic programming tutorial" and the second link, https://www.codechef.com/wiki/tutorial-dynamic-programming, takes a strong stance that DP is not memoization. Which I guess makes some sense. Pedagogically they are very different, even if the theoretical underpinning is the same. – btilly Jan 23 '16 at 00:18
  • As for the difference in practice, compare the top down and bottom up implementations at http://stackoverflow.com/questions/19126796. I wrote a reasonable bottom up version, but the top down is MUCH clearer. – btilly Jan 23 '16 at 00:23
  • @harold Just out of interest, I checked some more sources that I am taking a bit more serious than random stack overflow answers and codechef tutorials. [CLRS](http://citc.ui.ac.ir/zamani/clrs.pdf), for example, has to say "There are usually two equivalent ways to implement a dynamic-programming approach. We shall illustrate both of them with our rod-cutting example. The first approach is top-down with memoization." [Erik Demaine from MIT in his introductory algorithms lecture](https://www.youtube.com/watch?v=ENyox7kNKeY&t=180) uses the term "memoization": Really no "war" to be found. – Niklas B. Jan 23 '16 at 14:42
  • Of course it's true that tabulation is more powerful and generic. E.g. you can't compute shortest paths with top-down memo, but you can fill a DP table using a priority queue to tell you which state to process next (Dijkstra). – Niklas B. Jan 23 '16 at 14:48
  • @NiklasB. we're having a nice little war right here though, so it evidently exists. There's a bit of it in the Talk page of the wiki article too, though it seems to be ignored. A bunch of people overly-vehemently arguing that DP *can* be done with merely memoization can also be found. [This guy](http://blog.racket-lang.org/2012/08/dynamic-programming-versus-memoization.html) strongly argues that they're different. I do not deny that there are lots of texts that treat memoization as a way to implement DP, I just disagree with them. – harold Jan 23 '16 at 17:24

0 Answers0