Thu, 03 Apr 2008 10:22:36 -0500

Related articles |
---|

[5 earlier articles] |

Re: Prediction of local code modifications preston.briggs@gmail.com (preston.briggs@gmail.com) (2008-03-29) |

Re: Prediction of local code modifications plfriko@yahoo.de (Tim Frink) (2008-04-01) |

Re: Prediction of local code modifications preston.briggs@gmail.com (preston.briggs@gmail.com) (2008-04-01) |

Re: Prediction of local code modifications max@gustavus.edu (Max Hailperin) (2008-04-02) |

Re: Prediction of local code modifications cfc@shell01.TheWorld.com (Chris F Clark) (2008-04-02) |

Re: Prediction of local code modifications gah@ugcs.caltech.edu (glen herrmannsfeldt) (2008-04-03) |

Re: Prediction of local code modifications max@gustavus.edu (Max Hailperin) (2008-04-03) |

Re: Prediction of local code modifications plfriko@yahoo.de (Tim Frink) (2008-04-03) |

Re: Prediction of local code modifications find@my.address.elsewhere (Matthias Blume) (2008-04-04) |

Re: Prediction of local code modifications gneuner2@comcast.net (George Neuner) (2008-04-04) |

Re: Prediction of local code modifications cfc@shell01.TheWorld.com (Chris F Clark) (2008-04-04) |

Re: Prediction of local code modifications cfc@shell01.TheWorld.com (Chris F Clark) (2008-04-05) |

Re: Prediction of local code modifications mayan@bestweb.net (Mayan Moudgill) (2008-04-05) |

[2 later articles] |

From: | Max Hailperin <max@gustavus.edu> |

Newsgroups: | comp.compilers |

Date: | Thu, 03 Apr 2008 10:22:36 -0500 |

Organization: | Compilers Central |

References: | 08-03-105 08-03-109 08-04-003 08-04-009 |

Keywords: | optimize |

Posted-Date: | 03 Apr 2008 11:39:25 EDT |

Chris F Clark <cfc@shell01.TheWorld.com> writes:

*> Tim Frink <plfriko@yahoo.de> 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*

*> fashion. 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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.