Tree Search Saving Execution State

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 hou开发者_JAVA技巧se 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)

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.

If you don't mind the overhead of a thread, put the search on a thread that does a little bit of work and then yields from time to time.

The advantage of threads is that you don't have to save state programmatically; the system will do it for you.

You have to pay for this in complexity, as the result of the search will come in asynchronously and you will have to arrange to get it somehow. Also you might need to set up 100ms timers. A lot of code. :)

best thing to do is to make points where you can easily save the state and resume later (you can try to make the function recursive to find the best points easily)

then at those points you can then choose to save state or continue