State space search: A*

Posted on February 1, 2012 by Tommy McGuire
Labels: data structure, toy problems, java

Last time, I quoted Wikipedia, "For the 15-puzzle, lengths of optimal solutions range from 0 to 80 moves". Unfortunately, the two solutions I found require 255 and 205 moves. That seems less than satisfactory.

So, here's the state of 15-puzzle solutions as it stands: we have depth-first search, which is relatively fast but which is not guaranteed to find a solution. On the other hand, we have breadth-first search, which is guaranteed to find an optimal solution, in the sense of the smallest number of moves for the 15-puzzle, but which is slow and expensive. And finally, we have a couple of heuristics which, used alone, relatively quickly find a solution, having some of the benefits of depth-first search, but which find markedly sub-optimal solutions.

What this situation calls for is a slightly modified algorithm. The algorithm I have in mind is called A*. A* is actually a basic modification of the state evaluation function used by an informed search. Instead of the Manhattan distance or the number of tiles out of position (which I have learned should be called the Hamming distance) as the evaluation function, A* uses the sum of a forward-looking heuristic function and the cost of the path from the initial state to the state being evaluated. For the 15-puzzle, this would be, say, the Manhattan distance of the current state from the goal state plus the number of moves from the initial state to the current state.

A* works by being a best-first search; by expanding the state that looks like it will produce the best solution, rather than a state that is simply structurally next (as in the case of uninformed searches) or a state that looks like it is nearest to a solution. As a result, A* is likely to use fewer resources than breadth-first search while finding a better solution than an informed depth-first search.

In fact, A* has a very nice property: if the forward-looking heuristic function is admissible, then the search algorithm is guaranteed to find the optimal solution. Admissible simply means that the heuristic function does not overestimate the cost of the path from the current state to a goal. Possibly the simplest way of finding an admissible heuristic function is to relax some of the constraints on the problem; for example, the Hamming distance heuristic relaxes the 15-puzzle problem by allowing tiles to be directly moved to their goal position and counting the number of tiles thus moved while the Manhattan distance heuristic relaxes the constraints by allowing tiles to move directly to their goal states (rather than requiring sliding them into the empty space) and counting the number of moves needed. Both the Hamming distance and the Manhattan distance are admissible.

Converting the fifteenpuzzle code to use A* is incredibly easy:


public static class AStarDistance implements Comparator<FState>
{
@Override
public int compare(FState o1, FState o2)
{
return (o1.totalDistance() + o1.pathLength) - (o2.totalDistance() + o2.pathLength);
}
}

I created a new implementation of Comparator<FState> which compares the two states by computing the totalDistance value (the Manhattan distance) of each object and the length of the path from the initial state to the states and then comparing the resulting sums. When creating an instance of Search<FState>, use a PriorityQueue based on this Comparator.

How well does it work? I've got no clue. Sorry. The A* search goes through hundreds of thousands of states before it exhausts the default JVM heap size, and it takes long enough to do so that I don't really feel interested in trying it with more memory. The implementation could be optimized, but this is an exponential algorithm and optimization would be unlikely to make too much of a dent. (On the other hand, there is the possibility, however remote, that I've really hoarked something up. If so, I'd appreciate knowing about it.)

But I have the next best thing: by modifying the A* evaluation function, I can bias the evaluation towards the heuristic function, producing a solution in reasonable time and space. Unfortunately by doing so, I am likely to effectively make the heuristic function inadmissible, meaning that A* is no longer guaranteed to find an optimal solution. This is the implementation:


public static class BiasedAStarDistance implements Comparator<FState>
{
private final int bias;

public BiasedAStarDistance(int bias)
{
this.bias = bias;
}

@Override
public int compare(FState o1, FState o2)
{
return (bias * o1.totalDistance() + o1.pathLength) - (bias * o2.totalDistance() + o2.pathLength);
}
}

For me, it works significantly better than the un-biased A* search.

BiasStates examinedPath length
5386575
4426683
315,44273
219,87957

You can get the code on github. The previous posts are State space search: the basics and State space search: heuristics.

active directory applied formal logic ashurbanipal authentication books c c++ comics conference continuations coq data structure digital humanities Dijkstra eclipse virgo electronics emacs goodreads haskell http java job Knuth ldap link linux lisp math naming nimrod notation OpenAM osgi parsing pony programming language protocols python quote R random REST ruby rust SAML scala scheme shell software development system administration theory tip toy problems unix vmware yeti
Member of The Internet Defense League
Site proudly generated by Hakyll.