árbol de búsqueda Guardar estado de ejecución

Question

Tengo un árbol,

 A 
    /\ 
    B C 
    /\ \ 
D E F 

representado como una lista,

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

En realidad, es un árbol muy grande así que lo que me gustaría hacer es iniciar la búsqueda si no puedo encontrar lo que estoy buscando, digamos 100 ms guarde el estado, regrese, haga algo de mantenimiento y luego llame de nuevo a la búsqueda y continúe donde lo dejé. Básicamente, la simulación con la que estoy trabajando me da una cierta cantidad de tiempo que no es suficiente para completar la búsqueda. Estoy buscando ideas/técnicas sobre cómo lograr esto? (en Clojure, Java)

Answer 1

Enhebrar es probable que sea la solución más fácil, pero no es muy difícil de gestionar usted mismo en un solo hilo. Los entornos de "simulación" que solo le dan 100 ms a menudo no permiten ningún subproceso nuevo, por lo que esta es una alternativa.

La idea básica es crear un cierre que represente el trabajo que se debe realizar para finalizar la tarea, y devolverlo en lugar de un resultado si no tiene tiempo para terminar. Aquí hay un boceto: agrega una secuencia de números y se interrumpe cada diez operaciones en lugar de cada 100 ms.

(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 

Editar: Debido Clojure no tiene optimización de llamada, la creación de un golpe seco y luego llamando utiliza encima de la pila. Si, como es probable, puede ejecutar más de unos miles de pasos antes de que deba interrumpirse, obtendrá un desbordamiento de la pila. La única solución realista es duplicar el cuerpo del golpe seco, tanto en un recur y en la continuación, como

(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)) 

que probablemente podría abstracta esto con una macro si tuviera que escribir varias funciones tales "suspendibles".

Answer 2

Si no te importa la sobrecarga de un hilo, coloca la búsqueda en un hilo que trabaje un poco y luego ceda de vez en cuando.

La ventaja de los hilos es que no es necesario guardar el estado mediante programación; el sistema lo hará por ti.

Tienes que pagar por esto en complejidad, ya que el resultado de la búsqueda vendrá de forma asíncrona y tendrás que organizar para conseguirlo de alguna manera. También es posible que deba configurar temporizadores de 100 ms. Mucho código :)

Answer 3

mejor que puede hacer es hacer puntos donde puede guardar fácilmente el estado y reanudar más tarde (se puede tratar de hacer que el recursiva función para encontrar los mejores puntos fácilmente)

entonces en esos puntos a continuación, puede elegir para guardar el estado o continuar