递归树搜索：生成具有副作用的并发工作者

Question

我目前正在研究一种树搜索算法，以便在树结构中找到最优的、成本效益高的路径。

(def tree 
         '([1]
          [3 5]
         [5 6 4]
        [2 3 4 5]))

该函数通过递归函数调用启动多个“worker”，每次到达一个新节点。

(defn treewalk [tree]
       (let [worker_history {}]
       (letfn [(get-neighbours [level current_position]
                               (;; get adjacent nodes one level below)
                (worker [current_level current_position cost individual_history]
                        (if (;; current level above bottom)
                            (let [neighbours (get-neighbours  current_level current_position)]
                            ;; recursive worker call for next 2 branches
                            (worker (+ level1 1) (first_neighbour) (+ cost (current_cost)) 
                               (;; updated individual_history))
                            (worker (+ level1 1) (second neighbour) (+ cost (current_cost)) 
                                (;; updated individual_history)))
                                 ;; else: worker at bottom -> insert cost and individual history into worker_history
                            (assoc worker_history cost individual_history))
                                 )))))

worker_history 地图应该存储成本和个人路径，并在每个工人到达树结构底部时使用这些值进行更新。我知道处理这些副作用并不是在 Clojure 中解决该问题的最优雅方式！

目前，我运行遇到这样的问题，即 worker_history 只有 returns 最后一个工人的入口已经完成并且在函数中不表现为静态变量作用域，因此没有对该对象的并发访问。我怎样才能修改我的方法以达到这种“并发”水平？

Answer 1

为了同时更新worker_hisoty，你可以试试atom

...
  (let [worker_history (atom {})]
...

然后更新为 swap!

...
            (swap! worker_history assoc cost individual_history)
...

简单地说，您将 atom 视为具有原子更新的全局可变变量

Answer 2

你的结构不是树。在函数式语言中，树通常被写成嵌套列表（或向量），像这样：'(3 (4) (5)) 或这个 '(3 (4 (2) (8)) (5))。如果我坚持你的指示 递归树搜索，return 所有工人的成本和路径 ，这应该有效：

(defn tree-costs [tree]
  (let [worker-history (atom [])]
    (letfn [(treewalk [tree cost history]
              (if (= (count tree) 1) (swap! worker-history
                                            conj [(+ (first tree) cost)
                                                  (conj history (first tree))])
                                     (doseq [node (rest tree)]
                                       (treewalk node
                                                 (+ cost (first tree))
                                                 (conj history (first tree))))))]
      (treewalk tree 0 [])
      @worker-history
      )))

(tree-costs '(3 (4) (5))) => [[7 [3 4]] [8 [3 5]]]
(tree-costs '(3 (4 (2) (8)) (5))) => [[9 [3 4 2]] [15 [3 4 8]] [8 [3 5]]]

同时检查 clojure.core.async 线程并发。

Answer 3

我会提醒您不要使用有状态技术，因为您会错过纯函数的好处。在不知道您要解决的问题的完整上下文的情况下，我不能说使用 atom 是否会很好地为您服务。

不是为每个树路径更新 atom，而是可以使用 reduce:

构建地图

(defn paths [tree]
  (when-let [root (ffirst tree)]
    (if-let [r (next tree)]
      (let [left (paths r)
            right (paths (map rest r))]
        (map #(cons root %) (concat left right)))
      [[root]])))

(defn tree-costs [tree]
  (reduce (fn [m path] (update m (reduce + path) (fnil conj #{}) path))
          {}
          (paths tree)))

递归树搜索：生成具有副作用的并发工作者

Recursive tree search: Spawning concurrent workers with side effect

clojure