在clojure中使用广度优先搜索的最短路径

Question

我代表一棵树

     A
    / \
   B   C
  /\    
 D  E

类似于 clojure 向量中的 [A [B [D] [E]] [C]]。我需要使用广度优先搜索来找到到达目标的最短路径。我的实际矢量看起来像这样 -

["33L" ["32R" ["31L" ["30R" [false]] ["11R" ["01L" ["00R" [true]]] ["00L" [false]]]] ["30L" [false]] ["22L" ["11R" ["01L" ["00R" [true]]] ["00L" [false]]] ["02R" ["01L" ["00R" [true]]] ["00L" [false]]]]] ["31R" ["30L" [false]] ["11L" ["01R" ["00L" [false]]] ["00R" [true]]]] ["22R" ["11L" ["01R" ["00L" [false]]] ["00R" [true]]] ["02L" ["01R" ["00L" [false]]] ["00R" [true]]]]]

所有以true结尾的节点都是我感兴趣的节点。有多个以true结尾的节点。我需要找到从第一个节点“33L”到真实节点的最短路径。例如，如果您查看顶部的树并假设 D 为真且 C 为真。从 A 到真正节点的最短路径是 A -> C

我想出了如何打印所有节点，就像使用广度优先算法搜索它们一样。

(defn bfs [& nodes]
    (if (seq nodes)
        (concat (map first nodes)
            (apply bfs (apply concat (map rest nodes))))))

运行它在我的树上给了我 -

("33L" "32R" "31R" "22R" "31L" "30L" "22L" "30L" "11L" "11L" "02L" "30R" "11R" false "11R" "02R" false "01R" "00R" "01R" "00R" "01R" "00R" false "01L" "00L" "01L" "00L" "01L" "00L" "00L" true "00L" true "00L" true "00R" false "00R" false "00R" false false false false true true true)

这正是广度优先搜索浏览整个数据集的方式。但是，我不知道如何找到并打印到真实节点的最短路径。在你问我之前，我已经看过其他关于堆栈溢出的广度优先算法。

更新：

我看过 clojure zipper，它解决了我的问题。但是，深度优先，我需要广度优先。有没有一种方法可以使用 z/down、z/left、z/right 函数围绕它创建广度优先包装器？

Answer 1

广度优先搜索是一种搜索。在这里你 return 步行顺序，如果你需要最短路径，那么你必须修改搜索算法实现以某种方式跟踪路径。这意味着您扩展的每个节点都应该有关于到它的最短路径的信息。您可以通过传递此信息手动完成此操作。

Clojure 几乎内置了 zippers 允许遍历树。您可能想使用它们。

(require '[clojure.zip :as z])

> (def a ["0" ["1L" [false] [false]] ["1R" [true]]])

> ;create a zipper where vector? is a branch and (vec (rest %)) are
> ;childrens
> (def ztree (z/zipper vector? (comp vec rest) nil a))
> ztree
[["0" ["1L" [false] [false]] ["1R" [true]]] nil]
> (vector? ztree) ;zipper is vector of your original vector and some aaditional info
true
> (meta ztree) ;here are the functions
{:zip/make-node nil, 
 :zip/children #<core$comp$fn__4192 clojure.core$comp$fn__4192@59bdcbda>,   
 :zip/branch? #<core$vector_QMARK_ clojure.core$vector_QMARK_@319449e4>}
> (-> ztree z/down z/down z/up z/right z/down) ;walk the tree
[[true] 
 {:l [], 
  :pnodes [["0" ["1L" [false] [false]] ["1R" [true]]] ["1R" [true]]],
  :ppath {:l [["1L" [false] [false]]], 
          :pnodes [["0" ["1L" [false] [false]] ["1R" [true]]]], 
          :ppath nil, 
          :r nil}, 
  :r nil}]

所以你可以看到，我如何手动遍历树和拉链结构是一个向量，当前分支或节点在 first 位置，地图是 :l 和 :r 中的左右兄弟节点，[=16= 中此节点的路径（不是行走顺序），:ppath 中此节点的父拉链结构。

所以你使用拉链然后你的路径在 :pnodes 中被跟踪。

P.S。在您发表评论后

如果您需要实现，那么这里就像教科书中的那样：

(defn queue [& vals]
  (apply merge (clojure.lang.PersistentQueue/EMPTY) vals))

(defn bfs [tree]
  (loop [expanding (queue {:node tree
                           :path []})]
    (if (empty? expanding)
      nil
      (let [{[val & childs] :node
             p :path}
            (peek expanding)
            curr-path (conj p val)]
        (if (true? val)
          p
          (recur
           (apply merge (pop expanding)
                  (map #(hash-map :node %
                                  :path curr-path)
                       childs))))))))

> (bfs your-vector)
["33L" "31R" "11L" "00R"]

但看起来最好还是尝试自己解决这个问题。

P.P.S。您可以根据需要使用拉链行走。只需修改您的代码以使用在您的树上方制作的拉链，您将同时获得步行顺序和最短路径。

Answer 2

@JustAnotherCurious 有正确的答案，但我会稍微不同地表述 BFS 的实现，以获得更惯用的风格（使用 when-let，而不是 if，nil 和 let，并使用 nil-punning 而不是 empty? 例如）。我还将树的数据表示隐藏在接口后面，以便在必要时更容易更改：

(defn goal? [[val]]
  (true? val))

(defn leaf? [tree]
  (= 1 (count tree)))

(defn tree-val [tree]
  (first tree))

(defn children [tree]
  (rest tree))

(defn queue [& vals]
  (apply conj clojure.lang.PersistentQueue/EMPTY vals))

(defn bfs [root]
  (loop [q (queue {:tree root :path []})]
    (when-let [{:keys [tree path]} (peek q)]
      (cond
        (goal? tree) path
        (leaf? tree) (recur (pop q))
        :else
        (let [new-path (conj path (tree-val tree))
              wrap     (fn [t] {:tree t :path new-path})]
          (recur (->> (children tree)
                      (map wrap)
                      (apply conj (pop q)))))))))

在clojure中使用广度优先搜索的最短路径

Shortest path using breadth first search in clojure

algorithm

tree

clojure

breadth-first-search