Dynamic Progamming: First Principles

[psykotic]

I'm fond of this old RAND report from Dreyfus, which is worth skimming if you're mathematically inclined: Dynamic Programming and the Calculus of Variations, https://www.rand.org/content/dam/rand/pubs/reports/2006/R441...

One important takeaway is that dynamic programming in the Bellman formulation is a discrete analogue of Hamilton-Jacobi theory in how it writes down an equation for the optimal value as a function of a given endpoint rather than writing down an equation for the path as with the Euler-Lagrange equations. (You can reconstruct the path from the value function after the fact by gradient descent.) The relationship between Hamilton-Jacobi and Euler-Lagrange is the classical version of wave-particle duality. A concrete example in geometrical optics is the eikonal equation, a Hamilton-Jacobi type PDE, versus the geodesic equation, an Euler-Lagrange type ODE. Not coincidentally, one common numerical method for the eikonal equation called the fast marching method is a dynamic programming algorithm, very similar to Dijkstra's algorithm for shortest paths.

It should be mentioned that any "local" equation like a PDE or ODE cannot describe a globally optimal solution without strong assumptions such as convexity. In fact, satisfying the Euler-Lagrange equation isn't even sufficient for local optimality without further qualifications (Weierstrass conditions). But the Bellman dynamic programming equation, being recursive, can describe globally optimal solutions.

[mlevental]

understand basically all of you've said here except this:

>The relationship between Hamilton-Jacobi and Euler-Lagrange is the classical version of wave-particle duality.

in what sense are two formalisms (hamiltonian and lagrange) related to the relationship between time and freq space for fourier solutions to pdes?

also holy shit i would pay pretty good money for a service that typeset these old monographs using latex.

[krat0sprakhar]

While dynamic programming is taught in almost all algorithms classes, I think I finally grokked it after implementing it in a few practice problems. Would strongly recommend giving a few exercises listed here a shot: https://leetcode.com/tag/dynamic-programming/

[hatred]

Personally, I prefer these more than the leet code problems: https://people.cs.clemson.edu/~bcdean/dp_practice/

[zerr]

I've grokked it a couple of times, implemented solutions for some problems (knapsack, matrix multiplication, etc...), but I always keep forgetting...

[baddox]

It’s odd that there would be algorithms classes that don’t require some implementations.

[akhilcacharya]

Interesting that you should mention that because not being able to do those problems is why I want to learn it!

[et2o]

Favorite examples for applications of dynamic programming? Mine are sequence alignment/BLAST in bioinformatics, but I'm sure there are many of which I am not aware in other fields.

[Terr_]

Ditto, my first "Ahah!" moment for DP was actually in a bioinformatics class, implementing Needleman–Wunsch global sequence alignment using a Blosum64 matrix door transition weights. (Details that aren't as impressive as they sound.)

I ended up using it as the basis for another extra-credit project that demonstrated the algorithm with a GUI: Select inputs, choose speed, hit Play, watch the numbers and lines, etc.

Anyway, it's stayed with me as my go-to DP example.

[thechao]

Line breaking. The Knuth-Plass algorithm I implemented is my all-time favorite piece of code.

[iandioch]

There are lots of interesting competitive programming problems (and their related algorithms) that involve it. For example, it was important in the solution to a problem in the UKIEPC (UK & Irish programming contest to gear up for the ACM ICPC) this past weekend: https://domjudge.bath.ac.uk/domjudge/public/problem.php?id=3... :)

[Bromskloss]

I guess someone have to mention finding an optimal line wrap for a paragraph of text.

https://doi.org/10.1002%2Fspe.4380111102

[TuringNYC]

Dont need DP here since there is an obviously better iterative approach, BUT, the easiest demonstration of DP value is the naive Recursive algo for Fibonacci sequence generation vs the DP+Recursive algo.

[joshvm]

Stereo image matching - specifically semi-global matching. The general idea is still considered a state of the art method.

[mlechha]

All of Reinforcement Learning :)

[santaclaus]

Image stitching is pretty fun!

[pmalynin]

Reinforcement Learning

[wht]

In O.R. graduate School, Professor Gene Woolsey told us that he'd rise from the grave and stand on our desks screaming 'No!No!No!' if we ever actually used it to solve a practical problem.

IIRC, his complaints were about the speed of formulation, difficulty to understand and communicate the model to others, and the processing required to regenerate answers when the model changed.

I believe Optiant used Dynamic Programming for supply chain optimization.. So people do or did use it for practical problem solving. ..I think.

[gwern]

You might be surpised how far you can get with DP on a modern computer! For example, in https://www.gwern.net/Coin-flip we consider a gambling game with 300 rounds and at least as many options each round, and while it initially sounds infeasible, you can still compute the optimal strategy in under a minute with some optimized C/C++ implementing the DP solution. Modern computers are fast. (And you can define a solution in like 5-10 lines of R/Python if you don't mind them being a lot slower. I don't know how you would solve it with LP or MIP but I suspect it will be both slower and longer.)

[mattkrause]

What were you supposed to use instead? My impression is that dynamic programming is sometimes sluggish but often better than the alternatives.

[gumby]

> I believe Optiant used Dynamic Programming for supply chain optimization.. So people do or did use it for practical problem solving. ..I think.

Yes, the least cost path problem is not just a classic DP problem but is an example in this article.

[hyperpallium]

Edit distance (nee Levenshtein distance) is solved with dynamic programming, and is used by spell-checkers.

I agree reformulating the problem can be confusing. It wouldn't be worth it, but for the incredible efficiency gains (not always needed).

[mratsim]

For the last part about economic optimization, I would not approach it with Dynamic Programming. As evidenced by go and many games, doing the "local" best move does not guarantee the best result in the end. If brute-forcing is untractable, the state-of-the-art is using Monte-Carlo Tree Search as evidenced by its dominance in board games, Magic the Gathering, Poker, robots competitions, RTS, etc ...

[sacado2]

Constraint solving works pretty well in these domains too, and AFAIK, top-level artificial players in board games is a mix of constraint solving and MCTS.

[charlysl]

I learned it as part of speech processing, first for Dynamic Time Warping and then as the Viterbi and Baum Welch algorithms. Together with Hidden Markov Models it's a thing of beauty how it is used to model speech.

All of this is explained very intuitively in speech.zone

In the wikipedia entry there is a fun (really) explanation of why its creator called it like this.

[HHest]

Please note, the last name of the author referenced in the article is "Trick", not Tick.

http://mat.gsia.cmu.edu/classes/dynamic/dynamic.html

[matt4077]

Together with memo(r)ization, and the typo in the title, I'm starting to thing the letter 'R' is having a bad day.

[tommsy64]

There appears to be a missing return statement in the Fibonacci Number example in the if block. Should look like this: https://repl.it/NLIf/1

[molikto]

Why use monospace font?????

[pingiun]

I agree, it's hard to read

[raister]

Best font ever... why not?

[goerz]

Totally love the font!

[misja111]

> Tail recursion [3], a variant of traditional recursion implements memoisation, which uses memoisation very economically.

I don't understand this part, can anybody explain?

[cdax]

In "traditional" recursion, each recursive call is pushed onto the function call stack. This means that your recursive solution will eventually run out of memory when the number of recursive calls is more than what the function call stack can handle.

e.g., consider the following recursive solution for calculating the sum of all positive integers up to a given `n`:

  fn sum(n):
    if n == 0:
      return 0
    else:
      return n + sum(n - 1)    // A

When n = 1000, your function call stack will have to hold ~1000 calls (fn(1000), fn(999), fn(998), fn(997), and so on...), before it's able to compute the sum. This is because the return statement in line A above, needs to keep track of the variable `n` from the calling function in order to be able to compute the return value. If only there was some way to eliminate that variable `n`...

That's where tail-recursion or tail-call optimization comes in:

  fn sum_tail(n, pre_sum):
    if n == 0:
      return pre_sum
    return sum_tail(n - 1, pre_sum + n)    // B
    
  fn sum(n):
    return sum_tail(n, 0)

In this solution, the return statement at line B does not depend on any variable from the calling function (it simply passes that value on to next function call), and so the calling function can immediately be popped off the stack, saving stack space and making your solution more memory-efficient.

It's useful to know that whether any stack space can actually be saved, depends on whether your language of choice implements tail-call optimization. e.g., JavaScript recently started supporting tail-call optimization after ES6 [1], and Python does not support it [2].

[1] http://2ality.com/2015/06/tail-call-optimization.html [2] https://stackoverflow.com/questions/13591970/does-python-opt...

[fmihaila]

Glaring typo in the title: it should say progRamming.

[santaclaus]

> Memorisation

It is memoization, not memorisation! Although for two weeks in algorithms class I did in fact think our prof was just pronouncing memorize in a cutesy manner.

[quotemstr]

Honestly though, we should just switch to using "memorization". It's a less obscure word that communicates the intended meaning better, IMHO.

[ram_rar]

Given the sad state of programming interviews. People mostly land up memorizing

[foxh0und]

Thanks all!

[throwaway7645]

I came on here to say that.

[dep_b]

That's simply the British English way of writing the word. The author is a Swede and most probably got educated in the official way of writing English.

[BucketSort]

Obligatory Demaine lectures - https://youtu.be/OQ5jsbhAv_M

[yandrypozo]

that's the best set of videos about DP !!

[yipopov]

Would it have killed him to use a proportional font? We have the technology to accomplish that now.