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

2 回答

• 0

  广度优先搜索是搜索 . 在这里您返回步行顺序，如果您需要最短路径，则必须修改搜索算法实现以某种方式跟踪路径 . 这意味着您展开的每个节点都应该包含有关它的最短路径的信息 . 您可以通过传递此信息手动完成 .

  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 处的向量，一个带有左右兄弟的 Map ，在 :l 和 :r ，这个节点的路径（不是步行顺序）在 :pnodes ， :ppath 中此节点的父拉链结构 .

  那么你使用拉链然后在 :pnodes 中跟踪你的路径 .

  附：你的评论后

  如果你需要实现，那么这里就像是教科书：

  (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.您可以根据需要使用拉链走路 . 只需修改您的代码即可使用树上方的拉链，您将获得两者，步行顺序和最短路径 .

  回复于 2024-05-04T14:03:50+08:00
• 1

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

  回复于 2024-05-04T14:03:50+08:00