Talk:Dynamic programming

Example

I (FvdP 21:51 Oct 22, 2002 (UTC)) had begun an example but do not feel the motivation to finish it cleanly right now (and perhaps not in the immediate future either). Here is it if anyone wants to complete it::

Suppose that we have to compute the product of n matrices A₁.A₂. ... .A_n, and we want to minimize the total number of operations by executing the matrix products in the best possible order.

The product of two matrices of size i × j and j × k

........

---

This example is published in Cormen's Introduction to Algorithms textbook. Will we run into copyright issues by putting it here?

Absolutely not! Ideas cannot be copyrighted, only a particular way of expressing those ideas. CLRS itself based this section on various papers. In other words, we can write an explanation of the problem and its solution in our own words, but should be careful not to copy text or even the precise presentation of the problem. Derrick Coetzee 20:09, 5 Oct 2004 (UTC)

Confusion

The first paragraph of the second part and the article on algorithms states that dynamic programming is a bottom-up approach, but later this article says dynamic programming may use bottom-up or top-down approaches. --zeno 11:46, 9 Feb 2004 (UTC)

I've revised that section. It was very vague and somewhat incorrect. I hope there's less confusion now. Derrick Coetzee 20:18, 5 Oct 2004 (UTC)

Mild correction of pseudocode.

The article's pseudocode was inconsistent. At times, it used a Python-like indenting to represent the code structure. But it also included brackets at times. I have added brackets so that the pseudocode follows a C-like syntax: if the result of a loop, conditional, or whatnot is longer than one line, it is surrounded by brackets.

A more aggressive editor might prefer that no brackets be used. I don't know whether a bracket-less pseudocode would be clearer, but any consistent use of brackets would be clearer than what was there. (Would always using brackets be clearer -- for people who use a text-to-speech synthesizer, for example -- or would it just put in too much punctuation?) Chip Unicorn

In pseudocode I like to prefer indentation to braces where it's not unclear, to avoid eye-clutter, but I don't disagree with your changes - it's still sparse enough to be readable. Deco 01:10, 23 Jun 2005 (UTC)

I tried it without braces, and it looks visually clearer. If Wikipedia gets complaints that this is un-understandable by some group. we can put in some way to distinguish the levels. Chip Unicorn 12:41, 23 Jun 2005 (UTC)

Weirdness

The page says "i dont know" in those terms, which is not only weirdly misplaced, but also improperly formatted. Someone check.

Smith-Waterman Algorithm

I don't see any mention of the Smith-Waterman algorithm, which is a dynamic programming algorithm just like the Needleman-Wunsch. Would it be appropriate to add that one as well? --scskowron 13:57 , 13 December 2006 (UTC)

Misplaced section

The part following "The steps for using dynamic program goes as follows:" is out of place. Out of nowhere the article starts using terms like 'gap penalties' and 'sequence alignment.' Seems like this was copied from some article on a specific application, such as protien sequencing. Anon, Wed Jul 11 14:11:43 EDT 2007

too many examples

This is not a textbook. One good example would suffice. Even worse, many of them are just too long (and boring). Put them in wikibooks. Unfortunately, any attempt to fix this article would be blocked as "vandalism". Way to go, Wikipedia!

Dr. Fabbri's comment on this article

Dr. Fabbri has reviewed this Wikipedia page, and provided us with the following comments to improve its quality:

I would like first of all the clarify that I give some comments on this Wikipedia article only because I have been invited in doing so and I feel a little embarassed in criticising the work of other people that spent generously their time for the community.

My overall impression is that the article is well done but it only concerns a part of the story (and, to tell the truth, the part on which I am less expert).

The dynamic programming (expression that is not equivalent to "dynamic optimization" as stated in the second line) can aso be applyed to continuous time optimisation problems both in a deterministic and in a stochastic framework, both in finite and infinite dimensions.

The use of dynamic programming for continous time optimization problem is strictly related to the study of the Hamitlon-Jacobi-Bellman (HJB) equation associated to the problem. If the problem is deterministic (resp. stochastic) the HJB equation is of the frst (resp. second) order. Under suitable hypotheses the value function of the optimization problem can be identified with the solution of the HJB equation. A particolarly suited notation of solution for HJB equations appear to be that of viscosity solution.

I mention some books on the subjet:

Deterministic problems, finite dimension:

- M. Bardi and I. Capuzzo-Dolcetta, Optimal control and viscosity solutions of Hamilton-Jacobi-Bellman equations, Systems and Control: Foundations and Appli- cations, Birkhäuser, Boston, 1997.

- W. H. Fleming and R. W. Rishel, Deterministic and stochastic optimal control, Ap- plications of Mathematics, vol. 1, Springer, Berlin, 1975. (also stochastic)

Stochastic problems, finite dimension:

- J. Yong and X. Y. Zhou, Stochastic controls, Hamiltonian systems and HJB equa- tions, Applications of Mathematics, vol. 43, Springer, New York, 1999.

Deterministic problems, infinite dimensions:

- X. J. Li and J. M. Yong, Optimal control theory for infinite-dimensional systems, Systems and Control: Foundations and Applications, Birkhäuser, Boston, 1995.

Stochastic problems, infinite dimensions

Stochastic Optimal Control in Infinite Dimensions: Dynamic Programming and HJB Equations (to appear).

This said, again, I wuold not like to give marks to anybody. I love Wikipedia and I only need to thank the people that work for it.

Kind regards

We hope Wikipedians on this talk page can take advantage of these comments and improve the quality of the article accordingly.

We believe Dr. Fabbri has expertise on the topic of this article, since he has published relevant scholarly research:

• Reference : Bambi, Mauro & Fabbri, Giorgio & Gozzi, Fausto, 2009. "Optimal policy and consumption smoothing effects in the time-to-build AK model," MPRA Paper 17128, University Library of Munich, Germany.

ExpertIdeasBot (talk) 16:07, 11 July 2016 (UTC)

Factual accuracy tag

This article has beed tagged for factual accuracy, yet there is no discussion in the talk page. I've introduced this section to allow for such conversation.--Work permit (talk) 19:06, 5 November 2016 (UTC)

Lead rewrite needed

Having read some of the above comments, and clicked on a few things, it strikes me that the material at Bellman equation is far more appropriate for the lead than what we presently have. The present lead almost seems to suggest that dynamic programming is a specialized form of divide and conquer, but I personally regard its core motivation as something quite different.

The present leads dives into memoization rather briskly, which I regard as primarily an accounting trick. Neither the word "discrete" nor the word "continuous" is presently found in the lead. Yuck.

If someone wishes to rewrite the lead from scratch, beginning with a short statement of what characterized the problem class as motivated from the Bellman page, then provides a paragraph about discrete/continuous, deterministic/stochastic, finite/infinite domain distinctions, and only then dives into the accounting trick of memoization and other algorithmically motivated material, consider this my earnest vote to fill your boots. — MaxEnt 20:46, 12 November 2016 (UTC)

The material from Bellman equation is suitable only for the economic/engineering version of dynamic programming. It does not even approximate the way dynamic programming is taught in computer science. —David Eppstein (talk) 21:22, 12 November 2016 (UTC)

As an academic with a foot in Computater Science and another in Management Science/Operations Research I tend to agree with MaxEnt about the fact that the original motivation of dynamic programming has little to do with divide and conquer, memoization, or dynamic programming algorithms taught in computer science. Probably there should be different pages: dynamic programming (computer science) and dynamic programming (management science). The term programming in dynamic programming is clearly linked to the origins of other programming techniques such as linear programming and stochastic programming. As Dijkstra explains in Reminiscences about the origins of linear programming the term programming is related to mathematical formulations (linear or otherwise) of military programs, i.e. plans for allocating resources, scheduling operations, etc. In his seminar work (Bellman 1957) Bellman is also mainly concerned with multi-stage (deterministic or stochastic) decision problems and their applications in "economics, physics, biology, or otherwise" (page 7); for instance, the book at page 3 begins with a motivating example involving a multi-stage resource allocation process. Most importantly, Bellman explicitly states at page 7, that [...] we must realise that the essential purpose in formulating many of these mathematical models [...], is not so much to calculate numbers [...] but rather to determine the structure of the solution and also at page ix The problem is not to be considered solved in a mathematical sense until the structure of the optimal policy is understood. With this statement, Bellman clearly positions his research in the same club as the one carried out in the previous decade by Dijkstra, Arrow and von Neumann. The structural properties Bellman is interested are mostly analytical characterisations of the optimal policy for a given system (e.g. Scarf 1960, "The optimality of (S,s) policies in the dynamic inventory problem"), rather than efficient numerical procedures. In Chapter I, Section 4, page 7-9, Bellman illustrates the essence of a backward recursion algorithm, he then goes on and states that "a digital computer may be programmed to print out the sequence of values" (i.e. the value function and the policy function). Bellman is aware of the computational advantages, and he mentions them, but he seems to be also clearly aware of the curse of dimensionality. He believes numerical approaches should be used only to gain insights. His chief concern is ultimately to determine analytically the structure of the optimal policy for a given class of problems, so that closed form solutions can be obtained, or dedicated algorithms - not necessarily dynamic programming ones - can be developed. --Dr.roberto.rossi (talk) 23:55, 27 March 2017 (UTC)