Performance of an A* search implemented in Clojure

Question

I have implemented an A* search algorithm for finding the shortest path between two states. The algorithm uses a hash-map for storing best-known distances for visited states. And one hash-map for storing child-parent relationships needed for reconstruction of the shortest path.

Here is the code. Implementation of the algorithm is generic (states only need to be "hashable" and "comparable") but in this particular case states are pairs (vectors) of ints [x y] and they represent one cell in a given heightmap (cost for jumping to neighboring cell depends on the difference in heights).

Question is whether it's possible to improve performance and how? Maybe by using some features from 1.2 or future versions, by changing the logic of the algorithm implementation (e.g. using a different way to store path) or changing state representation in this particular case?

Java implementation runs in an instant for this map and Clojure implementation takes about 40 seconds. Of course, there are some natural and obvious reasons for this: dynamic typing, persistent data structures, unnecessary (un)boxing of primitive types...

Using transients didn't make much difference.

Answer 1

You have to use priority-map instead of sorted-set for storing the open nodes, as it helps to improve the performance. You can have a look at this implementation done by Christophe Grand. It can help you a lot for implementing your code- clj-me.cgrand.net/2010/09/04/a-in-clojure

If you are looking to learn more about Artificial Intelligence then you visit Artificial Intelligence Tutorial. Also, if you are appearing for job profiles of AI Engineer or AI Expert then you can prepare for the interviews on Artificial Intelligence Interview Questions.