-1

所以我正在对一个 8 谜题进行 A* 搜索，它似乎有效，但问题是一旦找到解决方案，它就会继续遍历优先级映射并输出所有可能性。一旦我满足条件，有没有办法停止并输出？

注意：我觉得用 for 循环让 doseqs 变得懒惰，让它们不评估整个事情会是最好的。有没有办法做到这一点？

这是我的代码：

(defn a-star

   ([board history]

     (if (at-end? board) (print-board board)


           (let [options (filter #(possible-move? % board) *moves*)
                move (into (pm/priority-map) (for [move options] [move (global-man-dis (move-tile board move))]))]


              (doseq [pair move :let [next-move (key pair)]] 


                  (print-board (move-tile board next-move))
                  (println)
                  (a-star (move-tile board next-move) next-move (conj history board))

              )
          )
    ))



  ([board prev-move history]

     (if (or (at-end? board) (history-check history board)) (print-board board)


      (let [options (get-queue board (dont-go-back prev-move))
            move (into (pm/priority-map) (for [move options] [move (global-man-dis (move-tile board move))]))]

        (doseq [pair move :let [next-move (key pair)]] 


             (print-board (move-tile board next-move))
             (println)
             (a-star (move-tile board next-move) next-move (conj history board))

         )
       )
     )))



(defn -main [& args]
  (println "insert a list all numbers no spaces or letters")
  (def board (mapv (fn [^Character c] (Character/digit c 10)) (read-line)))
  ;(def testt [0 8 4 7 2 1 3 5 6])
  ;(def testt [1 2 3 5 4 6 8 0 7])
  (a-star board [])
  )
4

2 回答 2

2

为了扩展我昨天的评论，这里是 Clojure 中完整的通用 A* 实现。由于您没有a-star在您的问题中包含您的函数调用的各种辅助函数，我不知道您如何将 8 难题问题转换为图形搜索问题，但您应该能够自己调整以下代码.

(ns a-star.core
  (:require [clojure.data.priority-map :refer [priority-map]]))

(defn pred->path
  "Determine the path to GOAL from the map of predecessors PRED."
  [pred goal]
  (loop [node goal, path ()]
    (if (contains? pred node)
      (recur (pred node) (cons node path))
      (cons node path))))

(defn expand
  [node h [open g pred] succ cost]
  (let [g-succ (+ (g node) cost)]
    (if (and (contains? open succ)
             (>= g-succ (g succ)))
      [open g pred]
      [(assoc open succ (+ g-succ (h succ)))
       (assoc g succ g-succ)
       (assoc pred succ node)])))

(defn a*
  "Determine the shortest path from START to GOAL in graph GRAPH
with heuristic cost function H. GRAPH format is {from {to cost}}."
  [start goal graph h]
  (loop [open (priority-map start 0)
         closed ()
         g {start 0}
         pred {}]
    (if (empty? open)
      :no-path-found
      (let [node (key (peek open))]
        (if (= node goal)
          [:path-found (pred->path pred goal) (g goal)]
          (let [successors (apply dissoc (graph node) closed)
                [open* g* pred*] (reduce-kv (partial expand node h)
                                            [(pop open) g pred]
                                            successors)]
            (recur open* (conj closed node) g* pred*)))))))

测试代码应阐明如何使用该a*功能：

(ns a-star.core-test
  (:require [clojure.test :refer :all]
            [a-star.core :refer :all]))

(deftest test-a*
  (is (= (a* :sb :wb
             {:sb {:kl 70, :kr 145}
              :kl {:ff 103, :lh 53}
              :ff {:wb 116}
              :lh {:wb 183}
              :kr {:hb 84}
              :hb {:wb 102}}
             {:sb 222, :kl 158, :ff 96, :wb 0, :lh 108, :kr 140, :hb 87})
         [:path-found '(:sb :kl :ff :wb) 289])
      "Find path in a directed graph.")
  (is (= (a* :sb :wb
             {:sb {:kl 70, :kr 145}
              :kl {:sb 70, :ff 103, :lh 53}
              :ff {:kl 103, :wb 116}
              :lh {:kl 53, :wb 183}
              :kr {:sb 145, :hb 84}
              :hb {:kr 84, :wb 102}
              :wb {:ff 116, :lh 183, :hb 102}}
             {:sb 222, :kl 158, :ff 96, :wb 0, :lh 108, :kr 140, :hb 87})
         [:path-found '(:sb :kl :ff :wb) 289])
      "Find path in an undirected graph.")
  (is (= (a* :sb :wb
             {:kl {:sb 70}
              :ff {:kl 103}
              :lh {:kl 53}
              :kr {:sb 145}
              :hb {:kr 84}
              :wb {:ff 116, :lh 183, :hb 102}}
             {:sb 222, :kl 158, :ff 96, :wb 0, :lh 108, :kr 140, :hb 87})
         :no-path-found)
      "Find no path in reversed directed graph."))
于 2013-09-27T20:55:34.330 回答
1

一种常见的方法是if在结尾处围绕递归调用放置一个语句。就像是：

(if-not (finished? move)
   (a-star ... ))

)ps：一个无关紧要的格式化点，一些clojure程序员发现如果所有连续的关闭都在同一行上会更容易阅读，尽管这纯粹是个人喜好。

于 2013-09-24T22:07:23.767 回答