Content deleted Content added
m Fixed reference links that were broken |
Citation bot (talk | contribs) Add: s2cid, pages, volume, journal, year, title, doi, author pars. 1-1. Removed URL that duplicated unique identifier. Converted bare reference to cite template. Removed parameters. Formatted dashes. Some additions/deletions were actually parameter name changes. | You can use this bot yourself. Report bugs here. | Suggested by AManWithNoPlan | All pages linked from cached copy of User:AManWithNoPlan/sandbox2 | via #UCB_webform_linked |
||
Line 18:
The solution to this problem is an optimal control law or policy <math>\mathbf{u}^{\ast} = h(\mathbf{x}(t), t)</math>, which produces an optimal trajectory <math>\mathbf{x}^{\ast}</math> and a [[cost-to-go function]] <math>J^{\ast}</math>. The latter obeys the fundamental equation of dynamic programming:
:<math>- J_{t}^{\ast} = \min_{\mathbf{u}} \left\{ f \left( \mathbf{x}(t), \mathbf{u}(t), t \right) + J_{x}^{\ast \mathsf{T}} \mathbf{g} \left( \mathbf{x}(t), \mathbf{u}(t), t \right) \right\}</math>
a [[partial differential equation]] known as the [[Hamilton–Jacobi–Bellman equation]], in which <math>J_{x}^{\ast} = \frac{\partial J^{\ast}}{\partial \mathbf{x}} = \left[ \frac{\partial J^{\ast}}{\partial x_{1}} ~~~~ \frac{\partial J^{\ast}}{\partial x_{2}} ~~~~ \dots ~~~~ \frac{\partial J^{\ast}}{\partial x_{n}} \right]^{\mathsf{T}}</math> and <math>J_{t}^{\ast} = \frac{\partial J^{\ast}}{\partial t}</math>. One finds the minimizing <math>\mathbf{u}</math> in terms of <math>t</math>, <math>\mathbf{x}</math>, and the unknown function <math>J_{x}^{\ast}</math> and then substitutes the result into the Hamilton–Jacobi–Bellman equation to get the partial differential equation to be solved with boundary condition <math>J \left( t_{1} \right) = b \left( \mathbf{x}(t_{1}), t_{1} \right)</math>.<ref>{{cite book |
Alternatively, the continuous process can be approximated by a discrete system, which leads to a following recurrence relation analog to the Hamilton–Jacobi–Bellman equation:
Line 368:
For n=1 the problem is trivial, namely S(1,h,t) = "move a disk from rod h to rod t" (there is only one disk left).
The number of moves required by this solution is 2<sup>''n''</sup> − 1. If the objective is to '''maximize''' the number of moves (without cycling) then the dynamic programming [[Bellman equation|functional equation]] is slightly more complicated and 3<sup>''n''</sup> − 1 moves are required.<ref>{{Citation |author=Moshe Sniedovich |title= OR/MS Games: 2. The Towers of Hanoi Problem |journal=INFORMS Transactions on Education |volume=3 |issue=1 |year=2002 |pages=34–51 |
=== Egg dropping puzzle ===
Line 394:
: ''W''(''n'',''k'') = minimum number of trials required to identify the value of the critical floor under the worst-case scenario given that the process is in state ''s'' = (''n'',''k'').
Then it can be shown that<ref name="sniedovich_03">
: ''W''(''n'',''k'') = 1 + min{max(''W''(''n'' − 1, ''x'' − 1), ''W''(''n'',''k'' − ''x'')): ''x'' = 1, 2, ..., ''k'' }
Line 540:
}}
The word ''dynamic'' was chosen by Bellman to capture the time-varying aspect of the problems, and because it sounded impressive.<ref name="Eddy">{{cite journal |last=Eddy |first=S. R. |authorlink=Sean Eddy |title=What is Dynamic Programming? |journal=Nature Biotechnology |volume=22 |issue= 7|pages=909–910 |year=2004 |doi=10.1038/nbt0704-909 |pmid=15229554 |s2cid=5352062 }}</ref> The word ''programming'' referred to the use of the method to find an optimal ''program'', in the sense of a military schedule for training or logistics. This usage is the same as that in the phrases ''[[linear programming]]'' and ''mathematical programming'', a synonym for [[mathematical optimization]].<ref>{{cite book |
The above explanation of the origin of the term is lacking. As Russell and Norvig in their book have written, referring to the above story: "This cannot be strictly true, because his first paper using the term (Bellman, 1952) appeared before Wilson became Secretary of Defense in 1953."<ref>{{cite book |
== Algorithms that use dynamic programming ==
| |||