5
\$\begingroup\$

While working through some coding puzzles to brush up on Clojure, I encountered the need to use A* on some search problems. I tried to implement it from first principles/memory and that didn't go well, so I looked for existing implementations and found two (Joy of Clojure and cgrand's) but they were a little difficult to follow (for me) so I attempted to create my own. In the end it actually looks pretty close to cgrand's implementation.

I think this works as expected (using an example from here to verify), but just wanted to post to see if anybody can point out any glaring omissions / oversights. I've implemented this before in Python but it turned out to be quite different without using mutation.

The only issue I see is that I generate neighbors before testing whether I've already seen the node, so there is some inefficiency there. I couldn't figure out a good way to avoid this since my neighbor generation / filtering occurs in one step during the recursive call, whereas in languages allowing mutability you would process each child separately and you can test if it exists in the visited set each time.

(defn a-star-search 
 [start neighbor-func goal? remain-cost path-cost]
  (loop [q (conj (sorted-set) [0 start])
         cost-so-far {start 0}
         came-from   {start nil}]
    (if-let [[node-cost node :as node-state] (first q)]
      (if (goal? node)
          (reverse (take-while (complement nil?) (iterate came-from node)))
          (let [neighbors (neighbor-func node)
                prev-node (came-from node)
                prev-cost (cost-so-far node)
                cheaper (remove #(< (cost-so-far % Double/POSITIVE_INFINITY)
                                    (+ prev-cost (path-cost node %)))
                                neighbors)
                new-nodes (map #(vector (+ prev-cost
                                           (path-cost node %)
                                           (remain-cost %)) %)
                               cheaper)]
            (recur (into (disj q node-state) new-nodes)
                   (->> cheaper
                        (map #(vector % (+ prev-cost (path-cost node %))))
                        (into cost-so-far))
                   (into came-from (map (juxt identity (fn [_] node)) cheaper)))))
      "no more neigbors")))

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

(def h-vals {:s 7 :a 6 :b 2 :c 1 :g 0})

 (a-star-search :s
             #(-> % graph keys)
             #(= :g %)
             h-vals
             (fn [from to] (get-in graph [from to])))
\$\endgroup\$

1 Answer 1

Reset to default
4
\$\begingroup\$

I'm not going to be able to do a very thorough review. The code doesn't have anything outright wrong with it, and I'll admit, I've never been able to implement a decent A* implementation. It's just not something that's ever clicked for me very well (cue a new project to fix that).

That said, there's a few minor things that can be pointed out:

(fn [_] node) can be written as (constantly node). Your use of complement suggests you like to avoid explicit functions.

You can also replace:

(map (juxt identity (fn [_] node)) cheaper)

with:

(map vector cheaper (repeat node))

I personally find the latter to be much cleaner. (map vector xs ys) zips xs and ys together into pairs. Here, I'm just zipping cheaper with an infinite list of nodes. 

#(-> % graph keys)

can be replaced with:

(comp keys graph)

If, again, you want to avoid explicit functions (although that's not necessarily better).

I don't think returning "no more neighbors" is a great idea. If you need an indicator value for something like this, I'd probably define at the top something like:

(def no-neighbors ::no-neighbors)

Then return no-neighbors. You could also just use ::no-neighbors inline wherever you need it, but then you need to change it multiple places if you ever decide to change the keyword used. IDE's can help with that, but I like to just avoid the problem.

You could avoid the efficiency problem regarding neighbors if you had neighbor-f return a lazy sequence of keys. I can't off hand think of a good way to do that though.

You never use prev-node. It's good to remove dead code like that to remove bulk.

I think that's all I can really comment on. Hopefully someone else can give you a better review regarding the algorithm itself.

Good luck!

\$\endgroup\$
4
  • \$\begingroup\$ Thanks for the comments - I knew it just felt off writing (map (juxt identity (fn [_] node)) cheaper) - you're suggestion is much cleaner, also I agree constantly conveys intent more clearly than the explicit function I created. The return value on failure was left in by accident - you're right that definitely needs to go (was there for debugging earlier). I think returning the queue for inspection is traditional when you can't find the goal. Prev-node was also left in from an earlier iteration where I needed it (but factored out when came-from was added) - so thx for pointing that out! \$\endgroup\$ Commented Jul 7, 2018 at 0:43
  • \$\begingroup\$ I am going to leave it open just in case somebody comments further on the algorithm, but I very much appreciate your recommendations! \$\endgroup\$ Commented Jul 7, 2018 at 0:43
  • \$\begingroup\$ alright I don't think anybody is going to comment, accepting your answer. Thx for the pointers! \$\endgroup\$ Commented Jul 10, 2018 at 17:19
  • \$\begingroup\$ @Solaxun Np. Unfortunately, I'm really the only frequent Clojure reviewer here. There's Alan and a few others, but they don't seem to check CR often. It's a pain when I want my code reviewed lol. I usually check the Clojure tag at least once a day though, so if you ever need more code reviewed, I'll be here. \$\endgroup\$ Commented Jul 10, 2018 at 17:42

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.