The major difference between searching a graph and searching a tree is that a graph may contain cycles. If you're not careful you'll end up in a infinite loop, constantly searching the same cycle.
graph-searchhandles this by keeping track of old states and defining an equality function that allows you to customize the way two states are considered equal (for example, in a board game, states may be equal if they are rotations of each other).
new-statesgenerates successors that haven't been seen before.
This code compares quite well with the ANSI Common Lisp code in PAIP, not needing to use
funcallsimplifies the code a little, and
lambdais less verbose. The implementation of A* search below doesn't fair so well!
The A* Search algorithm is a best-first graph search algorithm based on the heuristics you supply. Paths with the least cost so far are explored first. The code below gives an implementation heavily based on the one in PAIP. The code feels butt-ugly and I think this is due to the mutable state that I've ported over from the original. There's almost certainly a nicer functional implementation in there somewhere!
So how can we see what the A* search is doing? I wrote a quick maze algorithm to visualize which is shown in the image. The app uses the A* algorithm to find a route from the top-left to the bottom-right, avoiding the black walls. It's is interactive, left clicking builds a wall, left clicking again destroys it. Right-clicking solves the maze if possible, and shows the shortest solution in pink.