統一成本搜索

Question

似乎是在這個程序中的錯誤我很感激，如果有人可以幫助

(defn findmincostindex [frontier] 
    (loop [i 0 n 0] 
    (if (< i (count frontier)) 
     (if (< (:cost (get frontier i)) (:cost (get frontier n))) 
     (recur (inc i) i) 
     (recur (inc i) n)) 
     n))) 


(defn uniformcostsearch [graph start end] 
    ((fn [frontier explored] 
    (if (empty? frontier) 
     "Failure" 
     (let [pathwithmincost (findmincostindex (into [] frontier)) 
     ;(let [pathwithmincost (findmincostindex frontier) 
      path (:path (get frontier pathwithmincost)) 
      cost (:cost (get frontier pathwithmincost)) 
      node (peek path) 
      childs (keys (graph node))] 
     (if (= node end) 
      path 
      (recur 
      (concat (subvec frontier 0 pathwithmincost) (subvec frontier (inc pathwithmincost)) 
       (map (fn [c] {:path (conj path c) :cost (+ cost ((graph node) c))}) 
       (filter #(not (contains? explored %)) childs))) 
      (conj explored node)))))) 
    [{:path [start] :cost 0}] #{})) 



(def graph { 
     "Oradea" { 
      "Zerind" 71, 
      "Sibiu" 151 
     }, 
     "Zerind" { 
      "Oradea" 71, 
      "Arad" 75 
     }, 
     "Arad" { 
      "Zerind" 75, 
      "Sibiu" 140, 
      "Timisoara" 118 
     }, 
     "Sibiu" { 
      "Oradea" 151, 
      "Arad" 140, 
      "Fagaras" 99, 
      "Rimnicu Vilcea" 80 
     }, 
     "Fagaras" { 
      "Sibiu" 99, 
      "Bucharest" 211 
     }, 
     "Rimnicu Vilcea" { 
      "Sibiu" 80, 
      "Pitesti" 97, 
      "Craiova" 146 
     }, 
     "Timisoara" { 
      "Arad" 118, 
      "Lugoj" 111 
     }, 
     "Lugoj" { 
      "Timisoara" 111, 
      "Mehadia" 70 
     }, 
     "Pitesti" { 
      "Rimnicu Vilcea" 97, 
      "Craiova" 138, 
      "Bucharest" 101 
     }, 
     "Mehadia" { 
      "Lugoj" 70, 
      "Drobeta" 75 
     }, 
     "Drobeta" { 
      "Mehadia" 75, 
      "Craiova" 120 
     }, 
     "Craiova" { 
      "Drobeta" 120, 
      "Rimnicu Vilcea" 146, 
      "Pitesti" 138 
     }, 
     "Bucharest" { 
      "Pitesti" 101, 
      "Fagaras" 211, 
      "Giurgiu" 90, 
      "Urziceni" 85 
     }, 
     "Giurgiu" { 
      "Bucharest" 90 
     }, 
     "Urziceni" { 
      "Bucharest" 85, 
      "Vaslui" 142, 
      "Hirsova" 98 
     }, 
     "Hirsova" { 
      "Urziceni" 98, 
      "Eforie" 86 
     }, 
     "Eforie" { 
      "Hirsova" 86 
     }, 
     "Vaslui" { 
      "Iasi" 92, 
      "Urziceni" 142 
     }, 
     "Iasi" { 
      "Neamt" 87, 
      "Vaslui" 92 
     }, 
     "Neamt" { 
      "Iasi" 87 
     }}) 

(println (uniformcostsearch graph "Neamt" "Iasi")) 
(println (uniformcostsearch graph "Neamt" "Vaslui")) 
(println (uniformcostsearch graph "Bucharest" "Arad")) 

應該輸出這些行

['Neamt', 'Iasi'] 
['Neamt', 'Iasi', 'Vaslui'] 
['Bucharest', 'Pitesti', 'Rimnicu Vilcea', 'Sibiu', 'Arad'] 

而是它說：

clojure.lang.LazySeq不能投射到 clojure.lang.IPersistentVector

當我使用

(into [] frontier) 

如果我用前沿獨自它說

顯示java.lang.NullPointerException

Answer 1

唯一的例外發生在第一subvec在recur。您重複發生的結果爲concat，這是一個懶惰的序列，並且您不能採用惰性序列的子向量。速戰速決是隻把它包在vec：

(vec (concat (subvec frontier 0 pathwithmincost) (subvec frontier (inc pathwithmincost)) 
       (map (fn [c] {:path (conj path c) :cost (+ cost ((graph node) c))}) 
       (remove explored childs)))) 

一些其他提示：

1. findmincostindex本質上是min-key一個重新實施，少將軍，你很可能通過使這個吸塵器那。
2. 集合也是函數，如果它是集合的成員，則返回參數（真值）。你可以用這個來改善一點(filter #(not (contains? explored %)) childs))) - 例如(remove explored childs)
3. 你的let可以使用destructuring縮短一點。

這裏是我的嘗試：

(let [[idx {:keys [path cost]}] (apply min-key (comp :cost second) (map-indexed vector frontier)) 
     node (peek path) 
     childs (keys (graph node))] 

過程這裏是

1. (map-indexed vector frontier)使得frontier成對指數和節點。
2. min-key找到具有最低值(:cost (second pair))的一對。
3. let結合名稱idx到對索引，path和cost到節點的:path和:cost密鑰。