[R] Dynamic Programming in R
pinard at iro.umontreal.ca
Fri Jan 20 00:54:24 CET 2006
>A concern that has been cited that may discourage R use for solving
>dynamic programs is its memory handling abilities.
For a dynamic programming problem defined over N steps, one usually
needs a N*N matrix, so problems should be tractable for N being "not too
big". In those I studied, CPU time usually was the scarse resource.
As extreme paths were known to be very unlikely, this (and memory as
well) could be alleviated somehow by limiting the solution search into
bands (more or less wide) following the diagonal of the solution matrix.
I also had some success in splitting big problems into a sequence of
smaller subproblems, and recursively: such approximations are likely not
acceptable in the general case.
I would guess that most dynamic programming problems have their own
specific artifacts and speed-up techniques, a universal solution might
be uneasy. Who knows (I'm not sure): R might well offer a powerful
environment for building a dynamic programming framework.
François Pinard http://pinard.progiciels-bpi.ca
More information about the R-help