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

Question

我目前正在研究一种树搜索算法，以在树结构中找到最佳、经济高效的路径。

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

该功能启动多个"；工人"；通过递归函数调用，每次到达一个新节点时。

(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映射应该存储成本和单个路径，并在每个单独的worker到达树结构的底部时使用这些值进行更新。我知道在Clojure中处理这些副作用并不是解决这个问题的最优雅的方法！

目前，我遇到的问题是，worker_history只返回最后一个完成的工作人员的行条目，并且在函数范围内不作为静态变量，因此不存在对对象的并发访问。我怎么还能修改我的方法来达到这种水平；并发性"；？

Answer 1

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

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

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

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

然后用swap更新它！

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

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

Answer 3

我要提醒您不要使用有状态技术，因为您会错过纯函数的好处。在不了解您试图解决的问题的全部背景的情况下，我不能说使用atom是否对您有好处。

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

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