Functional A*

a_star.cljc

;; Rewrite of https://en.wikipedia.org/wiki/A*_search_algorithm#Pseudocode in a functional way

#?(:cljs (def INFINITY 9007199254740991)) ;; Math.pow(2,53)-1
#?(:clj  (def INFINITY Integer/MAX_VALUE))

(defn a*
  ([graph start goal heuristic] (a* graph start goal heuristic
                                    #{start} #{} {}
                                    {start 0} {start (heuristic start goal)}))
  ([graph start goal h
    open-set closed-set came-from
    g-score f-score]

   (if (empty? open-set)       
     :disjoint-graph-no-route-possible

     (let [current    (apply min-key #(get f-score % INFINITY) open-set)
           open-set   (disj open-set current)
           closed-set (conj closed-set current)]

       (if (= current goal)

         ;; We made it!  Reconstruct the path using the came-from map
         (loop [path [goal]]
           (if (came-from (last path))
             (recur (conj path (came-from (last path))))
             (reverse path)))

         (loop [neighbours (graph current)
                open-set   open-set
                came-from  came-from
                f-score    f-score
                g-score    g-score]

           (if-let [[neighbour cost] (first neighbours)]
             
             (if (or ;; we already finished with this neighbour
                     (closed-set neighbour)
                     ;; or the score isn't any better coming this way
                     (>= (+ cost (g-score current)) (get g-score neighbour INFINITY)))
               ;; disregard this neighbour and carry on
               (recur (rest neighbours) open-set came-from f-score g-score)

               ;; We found a new best path to this neighbour!
               (recur (rest neighbours)
                      (conj open-set neighbour)
                      (assoc came-from neighbour current)
                      (assoc f-score neighbour (+ cost (g-score current) (h neighbour goal)))
                      (assoc g-score neighbour (+ cost (g-score current)))))

             (a* graph start goal h open-set closed-set came-from g-score f-score)))))))) ;; NON-TCO :(

(def the-graph                
  {:a [[:b 2] [:c 1]]         ;;   a --(2)-- b --(9)-- e
   :b [[:a 2] [:d 3] [:e 9]]  ;;   |         |        /            
   :c [[:a 1] [:d 9]]         ;;  (1)       (3)     (4)            
   :d [[:c 9] [:b 3] [:e 4]]  ;;   |         |      /              
   :e [[:b 9] [:d 4]]})       ;;   c --(9)-- d-----/ 

(a* the-graph :c :e (constantly 0)) ;; => (:c :a :b :d :e)

                             

Can you please post the numbers when you have time..I'm interested to see the difference