Searching Graphs

Continuing from the previous post, Finding the Target, it's now time to focus on the basic graph searching algorithms introduced in Chapter 6 of PAIP.

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-search handles 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-states generates successors that haven't been seen before.

This code compares quite well with the ANSI Common Lisp code in PAIP, not needing to use funcall simplifies the code a little, and fn instead of lambda is 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.



The complete code can be seen in my Git repository. There's a really nice Javascript visualization out there if you don't fancy building the Clojure code.