Chris F Clark <cfc@[EMAIL PROTECTED]
> writes:
> Thus, dynamic programming is often a backtracking approach, you pick a
> solution for each of the problems in some order (often a greedy
> algorithm is used to come up with the initial solution) and compute
> the final score. Then, you revisit the items in the opposite order
> you originally picked them and try a different value for each one,
> until you have the best result. It is useful to think of the choices
> as a tree, where each choice made constrains the other subsequent
> choices (i.e. when you put one block in a regions of memory, you are
> then constrained not to put another block in that same memory), and
> you are visiting the tree of all possible choices in an organized
> fa****on. Now, as I recall (and I haven't done any significant dynamic
> programming recently), there usually is a method to prune unfruitful
> subtree explorations, i.e. a way to determine if changing the value of
> some value cannot possibly lead to a better solution than the one that
> has already been calculated, but that may or may not be a required
> feature of the method.
I think you are confusing dynamic programming with branch-and-bound
methods. (What you are describing sounds more like branch-and-bound.)
Dynamic programming works for problems where there is extensive
overlap between sub-problems, i.e., where the number of unique
sub-problems is much smaller than the size of the naive search tree.
(In other words, a naive search would visit many sub-problems over and
over again.) One can turn such a naive search into an efficient one
by caching the results for sub-problems that have already been solved
in a table. A more efficient way of doing the same thing is to fill
this table bottom-up -- and that is what dynamic programming does.
> It is worth noting, that because of the required backtracking,
> dynamic programming solutions usually grow exponentially with input
> problem size.
No, they don't. Dynamic programming problems run in time that is
roughly O(p times s) where p is the number of unique sub-problems and
where s is the "size" of each sub-problem, i.e., the time required to
solve it given the solutions to its own sub-problems. For many
typical problems, dynamic programming yields polynomial-time
algorithms.
Branch-and-bound, on the other hand, does usually result in worst-case
exponential-time algorithms.
Matthias
|
