Tree Search Saving Execution State

Question

Tôi có một cây,

 A 
    /\ 
    B C 
    /\ \ 
D E F 

biểu diễn dưới dạng một danh sách,

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

Nó thực sự là một cây rất lớn vì vậy những gì tôi muốn làm là bắt đầu tìm kiếm nếu tôi không thể tìm thấy những gì tôi đang tìm kiếm trong nói 100 ms tiết kiệm nhà nước, trở về, làm một số nhà giữ và sau đó gọi tìm kiếm một lần nữa và tiếp tục nơi tôi rời đi. Về cơ bản mô phỏng tôi đang làm việc với là cho tôi một số tiền nhất định của thời gian không đủ để hoàn thành việc tìm kiếm. Tôi đang tìm kiếm các ý tưởng/kỹ thuật về cách đạt được điều này? (trong Clojure, Java)

Answer 1

Threading có thể sẽ là giải pháp đơn giản nhất, nhưng nó không phải là rất khó khăn để quản lý nó bản thân trên một chủ đề duy nhất. Môi trường "Mô phỏng" chỉ cung cấp cho bạn 100ms thường không cho phép bất kỳ chủ đề mới nào, vì vậy đây là một thay thế.

Ý tưởng cơ bản là tạo ra một đóng cửa đại diện cho những công việc cần phải làm để hoàn thành nhiệm vụ, và trở về mà thay vì vậy nếu bạn không có thời gian để kết thúc. Dưới đây là một phác thảo: nó thêm một chuỗi các con số lên, và bị gián đoạn mỗi mười hoạt động thay vì mỗi 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 

Chỉnh sửa: Do Clojure không có tối ưu hóa cuộc gọi đuôi, tạo một đoạn và sau đó gọi nó sử dụng hết ngăn xếp. Nếu, có khả năng, bạn có thể thực hiện nhiều hơn một vài nghìn bước trước khi bạn cần phải bị gián đoạn, bạn sẽ nhận được tràn ngăn xếp. Các giải pháp thực tế duy nhất là để lặp lại trong cơ thể của thunk trong cả một recur và trong việc tiếp tục, như

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

Bạn có thể có thể trừu tượng này ra với một macro nếu bạn phải viết nhiều như vậy chức năng "suspendable".

Answer 2

Nếu bạn không để ý đến chi phí của một sợi, hãy đặt tìm kiếm trên một chuỗi làm một ít công việc và sau đó thu lại theo thời gian.

Ưu điểm của chủ đề là bạn không cần phải tiết kiệm nhà nước theo chương trình; hệ thống sẽ làm điều đó cho bạn.

Bạn phải trả tiền cho điều này trong phức tạp, như là kết quả của việc tìm kiếm sẽ có không đồng bộ và bạn sẽ phải sắp xếp để có được nó bằng cách nào đó. Ngoài ra, bạn có thể cần thiết lập bộ tính giờ 100ms. Rất nhiều mã. :)

Answer 3

điều tốt nhất để làm là để ghi điểm nơi bạn có thể dễ dàng lưu nhà nước và tiếp tục sau đó (bạn có thể thử để làm cho hàm đệ quy để tìm ra điểm tốt nhất một cách dễ dàng)

sau đó ở những điểm sau đó bạn có thể chọn để tiết kiệm nước hoặc tiếp tục