dynamic programming problems – my first look

The concept was well defined by the inventor but is now a bit vague. http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf is the best I have seen, but also check out http://mat.gsia.cmu.edu/classes/dynamic/dynamic.html . Below are some hallmarks of DP —

[C=comp science]

* solve sub-problems before solving the bigger problem. This approach/strategy is quite general
* [M] Principle of optimality
* [C] optimal substructure
* [M] stochastic dynamic programming
* [M] tail problems
* [C] DAGs

A major category of DP problems involve decision-making at discrete-time stages. Without stochastic elements, all the “contingent” decision-making could be (brought forward and) optimized upfront with clinical precision, like a robot analyzing a maze. In that case the stages are artificial, even unnecessary.

Therefore I now feel _ u n c e r t a i n t y _ is the major differentiator among DP problems. With uncertainty at each stage, we have no choice but break up the problem into periods. Without uncertainty, we can break up the problem artificially by period, or by segment…

Therefore, here are my classification of 3 categories of common DP problems (commonly found in tutorials) —
1) with uncertainty
2) with time periods without uncertainty
3) without time period. You create artificial stages. Often the simplest DP illustrations.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s