Re: Prediction of local code modifications

> 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

Return to the comp.compilers page.
Search the comp.compilers archives again.