Chris F Clark <cfc@[EMAIL PROTECTED]
> writes:
> Tim Frink <plfriko@[EMAIL PROTECTED]
> writes:
>
>> I'm not sure if dynamic programming is an approach that I can apply to
>> my problem. ...
> ... dynamic programming is often a backtracking approach, ...
> 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.
>
> It is worth noting, that because of the required backtracking, dynamic
> programming solutions usually grow exponentially with input problem
> size. That is, if your problem adds one more binary decision to the
> previous problem, the new problem takes roughly twice as long to
> solve, because you have doubled the size of tree you have to explore
> to find the correct solution.
I don't want to sound like there is something wrong with making a good
faith effort to be helpful -- that all any of us can do, myself
included. However, in this particular case, perhaps help from someone
who regularly works with dynamic programming would be more useful. In
particular, dynamic programming does not entail a backtracking search
through an exponential space of possibilities. Instead, it takes
advantage of the fact that though subproblems interact, they do so in
a restricted way. When considering whether to put item number N into
the knapsack, all that matters is the total weight and value of the
items from 1 through N-1 that were selected -- not the specific
choices that were made. As a result, it isn't necessary to actually
trace out all 2^N possibilities of what to include and what to
exclude. Instead, the problem can be solved in quadratic time. I
sent Tim an outline for such an algorithm by private email. -max
|
