A* in Clojure
Thanks to Mark Engelberg there’s now a nice priority map in contrib. With such a facility, it becomes really easy to write a nice implementation of the A* algorithm.
(ns net.cgrand.clj-me.a-star (:use [clojure.contrib.priority-map :only [priority-map]])) (defn A* "Finds a path between start and goal inside the graph described by edges (a map of edge to distance); estimate is an heuristic for the actual distance. Accepts a named option: :monotonic (default to true). Returns the path if found or nil." [edges estimate start goal & {mono :monotonic :or {mono true}}] (let [f (memoize #(estimate % goal)) ; unsure the memoization is worthy neighbours (reduce (fn [m [a b]] (assoc m a (conj (m a #{}) b))) {} (keys edges))] (loop [q (priority-map start (f start)) preds {} shortest {start 0} done #{}] (when-let [[x hx] (peek q)] (if (= goal x) (reverse (take-while identity (iterate preds goal))) (let [dx (- hx (f x)) bn (for [n (remove done (neighbours x)) :let [hn (+ dx (edges [x n]) (f n)) sn (shortest n Double/POSITIVE_INFINITY)] :when (< hn sn)] [n hn])] (recur (into (pop q) bn) (into preds (for [[n] bn] [n x])) (into shortest bn) (if mono (conj done x) done))))))))
Example:
(defn euclidian-distance [a b] ; multidimensional (Math/sqrt (reduce + (map #(let [c (- %1 %2)] (* c c)) a b)))) ;; generate a grid graph whose outlying edges are one-way (defn grid [x y w h] (into {} (for [i (range w) j (range h) :let [x0 (+ x i) y0 (+ y j) x1 (inc x0) y1 (inc y0)]] {[[x0 y0] [x1 y0]] 1 [[x1 y0] [x1 y1]] 1 [[x1 y1] [x0 y1]] 1 [[x0 y1] [x0 y0]] 1}))) (def g (apply dissoc (grid 0 0 4 4) (keys (grid 1 1 2 2)))) (comment user=> (A* g euclidian-distance [0 3] [4 2]) ([0 3] [1 3] [2 3] [3 3] [3 2] [4 2]) )
Shameless plug: if you are in Europe and want to learn Clojure, don’t forget to register for the Frankfurt course, October 26-28.
Hey, I have generic AI search (including A*) in clojure (http://github.com/aria42/mochi/blob/master/src/mochi/search.clj)
and it was using java.util.PriorityQueue, clojure.contrib.priority-map would be much better.
This appears to be not A* but a simplified algorithm which assumes that your heuristic is monotonic.
@foo I may have commited an oversight in implementing A* so I’d really like to hear more from you. However note that the closed set is augmented (monotonic A*) only when the option :monotonic is set to true.
it’s still moonspeak.
[...] may also be interesting to compare this a* search function to that of cgrande’s. a* algorithm, dijkstra's algorithm, [...]
Thanks for the nice example. I couple of minor comments:
The Math/sqrt is kinda slow and seems unnecessary in Eucl-dist; and if all the costs were integers, one could avoid Math/sqrt and replace the Double constant in A* with a Long (cheaper comparisons?).
The memoize is indeed worthy (question you posed above) as lookups of the same node may be done multiple times (node x may be rejected once but selected at a later time). I wonder though whether memoize is a better choice than sticking values into a regular hash-map.(?)
Hi,
Thanks for your post, insightful as usual ☺.
Just passing by, I wondered if you had considered using cheplist [*].
Best Regards,
B.
[*]http://nakkaya.com/2011/10/10/cheaplist-in-clojure/
@Bernard, no I haven’t, merci pour le pointeur.
This is brilliant and beautiful!
My favorite part is the code to trace back through the preds to recover the path: (reverse (take-while identity (iterate preds goal))) … what could be more succinct?
These usually consist of a sizeable array of emotional,
social and attitudinal variables. The concept
of Total Asset Management come into play as building owners start to focus on not only the development cost of a building but also the cost to
maintain the building throughout the building life cycle.
IT consulting Canberra companies stand beside IT infrastructure and
business organizations to help them in finding the
best candidate for their jobs.
The root cause of the problem was that the union negotiators could not strike up a collective bargaining
agreement that could protect the baseball players from the shrewd
manipulations of the team owners. At the rear of the cave may
be a Toktz-Ket-Dill (level 100), who’s armor you initially ought to break edge tool before you’ll deal
harm. Counter MVP – Kill the #1 player on the enemy team ten times in a
single match.
Rattling fantastic information can be found on weblog. I believe in nothing, everything is sacred. I believe in everything, nothing is sacred. by Tom Robbins.