2

環境

自分自身の練習として (私は clojure を学んでいます)。Depth-first searchアルゴリズムを実装したかったの です。

どのように私はそれをやった

再帰の使用

(def graph 
  {:s {:a 3 :d 4}
   :a {:s 3 :d 5 :b 4}
   :b {:a 4 :e 5 :c 4} 
   :c {:b 4} 
   :d {:s 4 :a 5 :e 2} 
   :e {:d 2 :b 5 :f 4} 
   :f {:e 4 :g 1}})

(def stack [[:s]])

(def goal :g)

(defn cost [Graph start goal]
  (goal (start Graph)))

(defn hasloop? [path]
  (not (= (count path) (count (set path)))))

(defn atgoal? [path]
  (= goal (last path)))

(defn solved? [stack]
  (some true? (map atgoal? stack)))

(defn addtopath [path node]
    (conj path node))

(defn pop* [stack]
    (last stack))


(defn findpath [stack]
    (if (not (solved? stack))
        (let [first* (pop* stack) l (last first*) ] 
                (findpath (drop-last 
                    (remove hasloop?  (lazy-cat
                                            (map #(addtopath first* %) 
                                            (keys (l graph))) stack)))))
        [(first stack)]))

使い方

(findpath スタック)

質問

このコードをどのように改善できるか、本当に興味があります。読みやすさ、効率、パフォーマンスの両方において。

4

1 に答える 1

4

怠惰な猫を使用しないでください、あなたがそれを使用するとあなたのseqが実現drop-lastされます。

Clojureでの再帰は、スタックオーバーフローを回避するために、 loop/を使用して実行する必要があります。recur

let1行に複数のsを配置しないでください。

(let [first* (pop* stack)
      l      (last first*)]

(if-notの代わりに使用してください(if (not。についても同じ(not=

小文字の変数名（graphではなく、Graph）を使用します。クラス、レコード、プロトコルを大文字にしてください。

于 2013-01-28T19:32:30.470 に答える