Geek Answers Handbook

Performing A * search implemented in Clojure

I applied the search algorithm * to find the shortest path between the two states. The algorithm uses a hash map to store the best known distances for visited states. And one hash map to store the relationship between parents and parents needed to restore the shortest path.

Here is the code. The implementation of the algorithm is general (the states must be "hashable" and "comparable"), but in this particular case the states are ints [xy] pairs (vectors) and represent one cell in a given height map (the cost to go to a neighboring cell depends on height difference).

The question is, is it possible to improve performance and how? Perhaps using some functions from version 1.2 or in the future, changing the logic of the algorithm implementation (for example, using a different way of storing the path) or changing the state view in this particular case?

A Java implementation starts in an instant for this map and Clojure 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 is not a big deal.

+6
performance artificial-intelligence clojure a-star
source share
2 answers

Using priority-map instead of sorted-set

I first used sorted-set to store open nodes (search front), switching to priority-map improved performance: now it takes 15 -20 seconds for this map (before that it took 40 seconds).

This blog post was very helpful. And the “my” new implementation is almost the same.

A new * -isk can be found here .

+4
source share

I do not know Clojure, but I can give you general advice on improving the performance of Vanilla A *.

  • Consider using IDA * , which is an A * option that uses less memory if appropriate for your domain.

  • Try using a different heuristic. Good heuristics can significantly affect the number of node extensions required.

  • Use a cache, often called a " transpose table " in search algorithms. Since search graphs are usually Directional acyclic graphs , not true trees, you can end up repeating a state search more than once; a cache for remembering previously found nodes reduces the decomposition of a node.

R. Jonathan Schaeffer has a few slides on this subject:

http://webdocs.cs.ualberta.ca/~jonathan/Courses/657/Notes/10.Single-agentSearch.pdf

http://webdocs.cs.ualberta.ca/~jonathan/Courses/657/Notes/11.Evaluations.pdf

+3
source share

More articles:


All Articles