Boost logo

Boost :

From: Dave Gomboc (dave_at_[hidden])
Date: 2003-12-15 07:05:31


> dynamic programming (algorithmic technique)
>
> Definition: An algorithmic technique in which an optimization
> problem is solved by caching subproblem solutions (memoization)
> rather than recomputing them.
>
> seems to contradict Mr. Apple's definition.

Yes, hmmm. Well, I'll try to do better:

When an optimization problem exhibits both "overlapping subproblems" and
"optimal substructure", it is amenable to solution via Dynamic
Programming (DP) techniques. Subproblems are solved at most once, and
their solutions are stored for later lookup (this would be pointless
without overlapping subproblems). Solutions to subproblems are combined
to solve larger subproblems (which is not possible without optimal
substructure).

The distinction between conventional DP and memoisation is that with the
former, subproblems are solved in advance of any attempted use of their
solution to solve a larger subproblem. In contrast, memoization
attempts to compute the final problem solution directly, computing
subproblems on demand as their solutions are required.

Generally, conventional DP is preferred when all subproblems must be
solved to solve the original problem, while memoisation is for choice
when it is possible to avoid solving some subproblems. Whether
avoidance is possible or not depends upon the specific optimal
substructure relation inherent to the problem.

(I think this is in agreement with what Mr. Apple wrote earlier.)

Dave


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk