Tue, 1 Apr 2008 23:01:46 -0700 (PDT)

Related articles |
---|

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

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

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

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

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

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) |

[6 later articles] |

From: | "preston.briggs@gmail.com" <preston.briggs@gmail.com> |

Newsgroups: | comp.compilers |

Date: | Tue, 1 Apr 2008 23:01:46 -0700 (PDT) |

Organization: | Compilers Central |

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

Keywords: | optimize |

Posted-Date: | 02 Apr 2008 10:22:45 EDT |

*> I'm not sure if dynamic programming is an approach that I can apply to*

*> my problem. When I understand the idea of dynamic programming*

*> correctly, it exploits the idea of "overlapping subproblems" and*

*> "memoization", i.e. it is assumed that the problem can be divided into*

*> independent subproblems which can be solved separately and then their*

*> optimal solution can be used to construct the global optimal solution.*

*>*

*> For my problem with the alignment I could divide the code into smaller*

*> subproblems where I could try to find an optimal local*

*> solution. However, these subproblems are not independent. When I move*

*> some code locally in one place (let's say that's the region of the*

*> first subproblem), then this might possibly also influence some*

*> following code in another region that I consider as a further*

*> subproblem. Thus, calculating separate optimal local solutions and*

*> them combine them will not work for me.*

Despite our disagreement about the history, I think Glen's intuition

is right on. You don't compute just the locally optimal solutions for

the subproblems, you compute all the solutions for each subproblem and

the cost for each, then consider the all the combinations, picking the

one that yields the globally optimal result.

It's not always easy to come up with such an approach;

that's why the people who do it publish and become famous!

Preston

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.