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. Simply, suppose I wish to calculate the factorial of 10, then "later" the factorial of 5. I have already calculated the factorial of 5, but now I must do it again. I have thought of various ways of preventing this; perhaps passing an Array in a state monad. I'm wondering if there is a general solution for this kind of problem. Thanks for any tips. -- Tony Morris http://tmorris.net/
On 2/25/07, Tony Morris
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.
Simply, suppose I wish to calculate the factorial of 10, then "later" the factorial of 5. I have already calculated the factorial of 5, but now I must do it again. I have thought of various ways of preventing this; perhaps passing an Array in a state monad. I'm wondering if there is a general solution for this kind of problem.
Thanks for any tips.
-- Tony Morris
You may be able to glean some ideas from a previous discussion at: http://comments.gmane.org/gmane.comp.lang.haskell.cafe/19623 Bryan Burgers
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.
participants (3)
-
Bryan Burgers -
Jeremy Shaw -
Tony Morris