Dear all

Can I know if dynamic programming can solve any optimization problem and if the obtained solution from DP is always optimal? If not, in what cases DP is not able to find the optimal solution?

Thanks

asked 28 Oct '17, 12:53

Amin-Sh's gravatar image

Amin-Sh
6116
accept rate: 0%


In theory, dynamic programming can solve any optimization problem involving a finite number of discrete decisions variables, each of which has a finite domain. Assuming dynamic programming is done properly, and assuming it does not run out of time or memory, it is guaranteed to find an optimal solution. In practice, the number of stages and states can explode exponentially, so DP is not always practical.

link

answered 29 Oct '17, 19:58

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412
accept rate: 19%

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×9

Asked: 28 Oct '17, 12:53

Seen: 202 times

Last updated: 29 Oct '17, 19:58

OR-Exchange! Your site for questions, answers, and announcements about operations research.