Tree Search Saving Execution State

Question

I have a tree,

     A
    / \
   B   C
  /\    \
 D  E    F

represented as a list,

(A (B (D) (E)) (C (F)))

It actually is a very large tree so what I would like to do is start the search if I can't find what I am looking for in say 100 ms save state, return, do some house keeping and then call search again and continue where I left off. Basically simulation I am working with is giving me a certain amount of time not enough to complete the search. I am looking for ideas/techniques on how to achive this? (in Clojure, Java)

Answer 1

Threading is likely to be the easiest solution, but it's not very difficult to manage it yourself on a single thread. "Simulation" environments that only give you 100ms often don't allow any new threads, so this is an alternative.

The basic idea is to create a closure representing the work that needs to be done to finish the task, and return that instead of a result if you don't have time to finish. Here's a sketch: it adds a sequence of numbers up, and gets interrupted every ten operations instead of every 100ms.

(let [timer (atom 9)]
  (defn keep-going? []
    (not= 0 (swap! timer #(mod (inc %) 10)))))

(defn saving-addition [sum xs]
  (if-let [[x & more] (seq xs)]
    (let [next-thunk (fn [] (saving-addition (+ x sum) more))]
      (if (keep-going?)
        (next-thunk)
        next-thunk))
    sum))

(defn monitor [xs]
  (loop [thunk (saving-addition 0 xs)]
    (if (fn? thunk)
      (do
        (println "Saving execution state")
        (recur (thunk)))
      thunk)))

user> (monitor (range 25))
Saving execution state
Saving execution state
Saving execution state
300

Edit: Because Clojure does not have tail-call optimization, creating a thunk and then calling it uses up stack. If, as is likely, you are able to execute more than a few thousand steps before you need to be interrupted, you will get a stack overflow. The only realistic solution is to duplicate the body of the thunk in both a recur and in the continuation, like

(defn saving-addition [sum xs]
  (if-let [[x & more] (seq xs)]
    (let [sum (+ x sum)]
      (if (keep-going?)
        (recur sum more)
        #(saving-addition sum more)))
    sum))

You could probably abstract this out with a macro if you had to write multiple such "suspendable" functions.