[R] Dynamic Programming in R

[François Pinard]

[Arnab mukherji]

>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