At Mon, 26 Feb 2007 07:54:56 +1000, Tony Morris wrote:
[1
] [1.1 ] I have a backtracking algorithm that I need to memoise with. Rather than go into the intricacies of the algorithm, I figure (and hope) the factorial function is trivial enough to point out my problem.
Have you seen the paper, Modular Lazy Search for Constraint Satisfaction Problems by Thomas Nordin and Andrew Tolmach? http://web.cecs.pdx.edu/~apt/jfp01.ps It starts with simple backtracking, and then adds 'memoising' to extend the algorithm to conflict directed backtracking, backmarking, forward checking, dynamic variable ordering, and other fun stuff. Although the algorithms are designed around solving constraint satisfaction problems, is is pretty easy to apply the technique a domain specific solver as well. I definitely recommend reading the paper if you are doing any sort of backtracking-type solvers. j.