Кратчайший путь, используя поиск в ширину поиск в Clojure

Я представляю дерево 

     A
    / 
   B   C
  /    
 D  E

Как [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)

Именно так при первом поиске по ширине будет просматриваться весь набор данных. Однако я не могу понять, как найти и распечатать кратчайший путь к истинному узлу. Прежде чем вы спросите меня, я уже посмотрел на другие алгоритмы breadth first в стеке переполнение.

Обновление:

Я посмотрел на застежку-молнию clojure, и это решает мою проблему. Тем не менее, это прежде всего глубина, и мне нужно что-то, что в первую очередь ширина. Есть ли способ, которым я мог бы использовать функции z/down, z/left, z/right, чтобы создать первую обертку вокруг него?
2 2
clojure algorithm breadth-first-search

2 ответа:

Широта первый поиск-это поиск. Здесь вы возвращаете порядок обхода, и если вам нужен кратчайший путь, то вам нужно изменить реализацию алгоритма поиска, чтобы как-то отследить путь. Это означает, что каждый узел, который вы расширяете, должен иметь информацию о кратчайшем пути к нему. Вы можете сделать это вручную, передав эту информацию.

Также 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, путь к этому узлу (не порядок ходьбы) в :pnodes, родительская структура молнии для этого узла в :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. Вы можете использовать молнии, чтобы ходить, как вы хотите. Просто измените свой код, чтобы использовать молнии, сделанные над вашим деревом, и вы получите оба, порядок ходьбы и кратчайший путь.

1

@JustAnotherCurious имеет правильный ответ, но я бы сформулировал реализацию BFS немного иначе, для более идиоматического стиля (используя when-let, а не if, nil и let, и использование нулевого каламбура вместо 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)))))))))
0