Поиск по дереву Сохранение состояния выполнения - PullRequest
Новая
       16

Поиск по дереву Сохранение состояния выполнения

8 голосов
/ 21 августа 2011

У меня есть дерево, 

     A
    / \
   B   C
  /\    \
 D  E    F

, представленное в виде списка, 

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

На самом деле это очень большое дерево, поэтому я хотел бы начать поискЯ не могу найти то, что я ищу, скажем, в состоянии сохранения 100 мс, вернуться, сделать домашнее хозяйство, а затем снова выполнить поиск и продолжить с того места, где я остановился.В основном симуляция, с которой я работаю, дает мне определенное количество времени, не достаточное для завершения поиска.Я ищу идеи / методы, как этого достичь?(в Clojure, Java)

Ответы [ 3 ]

7 голосов
/ 21 августа 2011

Потоки, вероятно, будут самым простым решением, но не очень сложно управлять им самостоятельно в одном потоке. Среды «моделирования», которые дают вам только 100 мс, часто не допускают никаких новых потоков, поэтому это альтернатива.

Основная идея состоит в том, чтобы создать замыкание, представляющее работу, которую необходимо выполнить, чтобы завершить задачу, и вернуть ее вместо результата, если у вас нет времени, чтобы закончить. Вот эскиз: он добавляет последовательность чисел и прерывается каждые десять операций вместо каждых 100 мс. 

(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

Редактировать: поскольку Clojure не имеет оптимизации хвостового вызова, создание thunk и последующий вызов использует стек вверх. Если, скорее всего, вы сможете выполнить более нескольких тысяч шагов, прежде чем вам понадобится прервать работу, вы получите переполнение стека. Единственное реалистичное решение - продублировать тело thunk как в recur, так и в продолжении, например 

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

Вы могли бы, вероятно, абстрагировать это с помощью макроса, если бы вам пришлось написать несколько таких "приостановленных" функций.

2 голосов
/ 21 августа 2011

Если вы не возражаете против издержек потока, включите поиск в потоке, который выполняет небольшую работу, а затем время от времени дает результат.

Преимущество потоков заключается в том, что выне нужно сохранять состояние программно;система сделает это за вас.

Вы должны заплатить за это по сложности, так как результат поиска придет асинхронно, и вам придется договориться о том, как его получить.Также вам может понадобиться установить 100 мс таймеры.Много кода.:)

0 голосов
/ 21 августа 2011

лучшее, что нужно сделать, - это создать точки, в которых вы можете легко сохранить состояние и возобновить работу позже (вы можете попытаться сделать функцию рекурсивной, чтобы легко находить лучшие точки)

, затем в этих точках вы сможетевыбрать сохранение состояния или продолжить

...