The A* algorithm in Clojure

As this snippet doesn't really help a lot to know what A* search actually is, here is the explanation from Artificial Intelligence: A Modern Approach (from Russel and Norvig):

The most widely-known form of best-first search is called A-start search (pronounced "A-star search"). It evaluates nodes by combining g(n) - the cost to reach the node, and h(n) - the cost to get from the node to the goal:

  f(n) = g(n) + h(n)

Since g(n) gives the path cost from the start node to node n, and h(n) is the estimated cost of the cheapest path from n to the goal, we have

  f(n) = estimated cost of the cheapest solution through n*

Thus, if we are trying to find the cheapest solution, a reasonable thing to try first is the node with the lowest value of g(n) + h(n). It turns out that this strategy is more than just reasonable: provided that the heuristic function h(n) satisfies certain conditions, K search is both complete and optimal.

So, for the following graph (tree actually):

  +---A---+
  |       |
  B h:1   E h:4
  |
  C h:2
  |
  D h:3

Where the function g(x) is the depth of the node in the tree, and the heuristic function h(x) is presented next to the node (random values), A-star will search for a solution first in the nodes with smaller values of f(n). So a traversal starting at node A will visit nodes in the following order: {A, B, C, E, D}

  f(B) = h(B) + g(B) = 1 + 1 = 2
  f(C) = 2 + 2 = 4
  f(E) = 4 + 1 = 5
  f(D) = 3 + 3 = 6

If there's anything wrong with my explanation please correct me.

P.S.: I know my heuristic function is probably not admissible.

10 second explanation of A star: you have a graph + matrix of node-node distances. You want to find shortest path from origin to destination. Standard Dijsktra only allows lookahead of one node at a time. A star allows you to incorporate a long range heuristic, like Euclidean distance from current node to destination. This gives a lower bound on current candidate path length and allows you to discard bad paths more rapidly.

Note that in all cases you need some basis for this heuristic (eg lat/lng of each node). Also, while 2D maps/nodes as cities is a great way to build your intuition for the algorithm, you can generalize it to arbitrary node types as long as heuristic function gives a good lower bound.