Re: Prediction of local code modifications

Tim Frink <plfriko@xxxxxxxx> writes:

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.

Actually, that is exactly the kind of problem dynamic programming is
designed to solve. The criteria for dynamic programming is only that
if you have already picked all the other problems with the value that
leads to the optimal solution, then you can pick the value to the last
problem that leads to the optimal solution (and so on working
backwards). Dynamic programming does not require the choices to be
independent (and in fact is designed to solve the case where the
choices are interdependent). If the choices are independent, simpler
solutions can be used.

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

Hope this helps,
-Chris

******************************************************************************
Chris Clark Internet: christopher.f.clark@xxxxxxxxxxxxxxxxxxxxxx
Compiler Resources, Inc. or: compres@xxxxxxxxxxxxx
23 Bailey Rd Web Site: http://world.std.com/~compres
Berlin, MA 01503 voice: (508) 435-5016
USA fax: (978) 838-0263 (24 hours)
------------------------------------------------------------------------------
.

Relevant Pages

  • Re: How to approach
    ... The concept behind dynamic programming is to basically do what you would do with a recursive solution, except cache values so you don't have to recompute them. ... in which you build tables of solutions to subproblems. ... Recursion with memoization can be efficient because you only solve ...
    (comp.lang.java.programmer)
  • Re: Dynamic programming and job scheduling
    ... Dave wrote: ... > In attempting to use dynamic programming for a job scheduling problem, ... > show that overlapping subproblems exist. ... > The optimal solution to this is to assign job 1 to machine B and to assign ...
    (comp.programming)
  • Re: Prediction of local code modifications
    ... optimization on the global code performance for complex processors? ... independent subproblems which can be solved separately and then their ... optimal solution can be used to construct the global optimal solution. ... Do you see another way to cope with my optimization problem? ...
    (comp.compilers)
  • Re: Possible Knapsack NP Complete problem?
    ... but I'm presuming you want an implementable solution:). ... you can also use linear programming to get an optimal solution to ... optimality is not needed) or dynamic programming (if you want pretty-much ... Michael Brown ...
    (comp.lang.pascal.delphi.misc)
  • Re: Prediction of local code modifications
    ... independent subproblems which can be solved separately and then their ... optimal solution can be used to construct the global optimal solution. ... You don't compute just the locally optimal solutions for ...
    (comp.compilers)