# A* in Python

A* is a directed search algorithm. Given a good heuristic function, it can perform much better than a blind breadth-first search.

## A* code

First, the main algorithm itself. I like using Python for lots of reasons. One that stands out, though, is that functions are first class. This allows us to write a generic A* function that works on many problems.

(Python is not unique in this. But it is still fun.)

Here is the main solving code.

```import heapq
import math
import random
def solve(start, finish, heuristic):
"""Find the shortest path from START to FINISH."""
heap = []

h = {} # heuristic function cache
g = {} # shortest path to a node

g[start] = 0
h[start] = 0

heapq.heappush(heap, (0, 0, start))
# keep a count of the  number of steps, and avoid an infinite loop.
for kk in xrange(1000000):
f, junk, current = heapq.heappop(heap)
if current == finish:
print "distance:", g[current], "steps:", kk
return g[current], kk, build_path(start, finish, link)

moves = current.get_moves()
distance = g[current]
for mv in moves:
if mv not in g or g[mv] > distance + 1:
g[mv] = distance + 1
if mv not in h:
h[mv] = heuristic(mv)
heapq.heappush(heap, (g[mv] + h[mv], -kk, mv))
else:
raise Exception("did not find a solution")
```

`solve` takes two positions, a start and finish, and a heuristic function. The heuristic function must always return a distance that is less or equal to the actual distance between two positions. The whole algorithm rests on that assumption.

`g[mv]` holds the length of the shortest known path to `mv`, and `h[mv]` holds the estimated distance from `mv` to finish according to the `heuristic` function. Then, `g[mv] + h[mv]` is the current best estimate of the distance from `start` to `finish` through `mv`.

We keep a the nodes to search next in a priority queue, ordered by the the current best estimates of the distance to `finish`.

`solve` is a generic function, and it realized on duck-typing to work. The position objects must provide a `get_moves` method that returns neighboring positions, a hash function `__hash__`, and an equality operator `__eq__`.

Whenever the goal position is at the top of the heap we are done. This is because the heap is ordered by the best possible score from a position to the goal. If there is a shorter path to the goal, it would have already been explored, since we explore by the best possible path first. Since it hasn't been seen before, this path is the best.

Note that this isn't true about positions other than the goal. That is because the heuristic provides an optimistic guess for the shortest path from a position to the goal, not the shortest path between any two positions. This is the reason that in the inner loop, we check if we are in the shortest path seen so far to a node. A node may be visited multiple times by A*, with shorter paths to the node each time.

The function `build_path` reconstructs the path to the solution for us. This is useful for debugging, and because we often want to know the path, not just the path length.

```def build_path(start, finish, parent):
"""
Reconstruct the path from start to finish given

"""
x = finish
xs = [x]
while x != start:
x = parent[x]
xs.append(x)
xs.reverse()
return xs
```

Here is a heuristic that does nothing, just for testing. Using this heuristic will lead to Dijkstra's algorithm, which is a good, but uninformed search algorithm.

```def no_heuristic(*args):
"""Dummy heuristic that doesn't do anything"""
return 0
```

## A grid example

Here is a simple test class where the program must find a path on a rectangular grid. We will assume the grid is infinite, but will also hope that our search doesn't go that far off course.

```class GridPosition(object):
"""Represent a position on a grid."""
def __init__(self, x, y):
self.x = x
self.y = y

def __hash__(self):
return hash((self.x, self.y))

def __repr__(self):
return "GridPosition(%d,%d)" % (self.x, self.y)

def __eq__(self, other):
return self.x == other.x and self.y == other.y

def get_moves(self):
# There are times when returning this in a shuffled order
# would help avoid degenerate cases.  For learning, though,
# life is easier if the algorithm behaves predictably.
yield GridPosition(self.x + 1, self.y)
yield GridPosition(self.x, self.y + 1)
yield GridPosition(self.x - 1, self.y)
yield GridPosition(self.x, self.y - 1)
```
```grid_start = GridPosition(0,0)
grid_end = GridPosition(10,10)
```
```def grid_test_no_heuristic():
solve(grid_start, grid_end, no_heuristic)
```

This gives us:

`distance: 20 steps: 840`

Now, we can add a heuristic. An obvious one is to Euclidean distance, since the shortest path between two points is a straight line.

```def euclidean_h(goal):
def f(pos):
dx, dy = pos.x - goal.x, pos.y - goal.y
return math.hypot(dx, dy)
return f
```
```def grid_test_euclidean_heuristic():
solve(grid_start, grid_end, euclidean_h(grid_end))
```
`distance: 20 steps: 134`

That result is significantly better.

We can do even better. Since our grid movements are restricted to left, right, up and down, we can use Manhattan distance as the heuristic. In this simple case, Manhattan distance is a perfect heuristic. Adding obstacles, or changing the cost of moving through grid points would keep Manhattan from being perfect.

```def manhattan_h(goal):
def f(pos):
dx, dy = pos.x - goal.x, pos.y - goal.y
return abs(dx) + abs(dy)
return f
```
```def grid_test_manhattan_heuristic():
solve(grid_start, grid_end, manhattan_h(grid_end))
```
`distance: 20 steps: 20`

We found the path without exploring any unnecessary nodes.

## Block Puzzle

In the Stanford AI class offered online, they discussed A* in the context of the classic fifteen puzzle, but simplified to just eight pieces.

Here is a class for the block puzzle. Usually the 15 puzzle is used, but the 8 puzzle is a lot faster to solve.

```class BlockPuzzle(object):
def __init__(self, n, xs=None):
"""Create an nxn block puzzle

Use XS to initialize to a specific state.
"""
self.n = n
self.n2 = n * n
if xs is None:
self.xs = [(x + 1) % self.n2 for x in xrange(self.n2)]
else:
self.xs = list(xs)
self.hsh = None
self.last_move = []

def __hash__(self):
if self.hsh is None:
self.hsh = hash(tuple(self.xs))
return self.hsh

def __repr__(self):
return "BlockPuzzle(%d, %s)" % (self.n, self.xs)

def show(self):
ys = ["%2d" % x for x in self.xs]
xs = [" ".join(ys[kk:kk+self.n]) for kk in xrange(0,self.n2, self.n)]
return "\n".join(xs)

def __eq__(self, other):
return self.xs == other.xs

def copy(self):
return BlockPuzzle(self.n, self.xs)

def get_moves(self):
# Find the 0 tile, and then generate any moves we
# can by sliding another block into its place.
tile0 = self.xs.index(0)
def swap(i):
j = tile0
tmp = list(self.xs)
last_move = tmp[i]
tmp[i], tmp[j] = tmp[j], tmp[i]
result = BlockPuzzle(self.n, tmp)
result.last_move = last_move
return result

if tile0 - self.n >= 0:
yield swap(tile0-self.n)
if tile0 +self.n < self.n2:
yield swap(tile0+self.n)
if tile0 % self.n > 0:
yield swap(tile0-1)
if tile0 % self.n < self.n-1:
yield swap(tile0+1)
```

We also need a way to create a shuffled puzzle. Here is a generic method for shuffling.

```def shuffle(position, n):
for kk in xrange(n):
xs = list(position.get_moves())
position = random.choice(xs)
return position
```

Now, we need a heuristic. The empty heuristic approach will take too long here.

The first, and simplest heuristic is to count how many tiles are out of place.

```def misplaced_h(position):
"""Returns the number of tiles out of place."""
n2 = position.n2
c = 0
for kk in xrange(n2):
if position.xs[kk] != kk+1:
c += 1
return c
```

Here is a sample run

```def test_block_8_misplaced(num_tests):
for kk in xrange(num_tests):
p = shuffle(BlockPuzzle(3), 200)
print p.show()
solve(p, BlockPuzzle(3), misplaced_h)
```
``` 0  2  5
8  3  7
1  6  4
distance: 19 steps: 872
2  7  0
6  8  3
1  5  4
distance: 19 steps: 958
1  5  4
7  2  8
0  3  6
distance: 25 steps: 13027
6  8  7
2  5  4
0  1  3
distance: 27 steps: 26762
3  8  4
7  0  6
2  1  5
distance: 21 steps: 3008```

Now, another heuristic is to measure the distance that each tile must move. This heuristic is ok, because we only move one tile at a time, and we know that each tile must move at least this many steps.

```def distance_h(position):
n = position.n
def row(x): return x / n
def col(x): return x % n
score = 0
for idx, x in enumerate(position.xs):
if x == 0: continue
ir,ic = row(idx), col(idx)
xr,xc = row(x-1), col(x-1)
score += abs(ir-xr) + abs(ic-xc)
return score
```

And another sample run.

```def test_block_8_distance(num_tests):
for kk in xrange(num_tests):
p = shuffle(BlockPuzzle(3), 200)
print p.show()
solve(p, BlockPuzzle(3), distance_h)
```
``` 4  7  2
1  0  5
6  8  3
distance: 22 steps: 941
6  5  1
4  0  3
2  7  8
distance: 16 steps: 59
1  3  4
2  0  5
7  8  6
distance: 16 steps: 235
4  5  0
3  8  2
6  1  7
distance: 24 steps: 1038
6  7  2
5  8  3
0  1  4
distance: 24 steps: 705```

For similar sizes, the results from this heuristic are much better. This testing methodology was pretty poor, though. A more detailed analysis would be better, but this writeup is getting long as it is.

Here is a short sample of one to one comparisons.

```def test_block(steps=100, count=5):
for kk in xrange(count):
p = shuffle(BlockPuzzle(3), steps)
print p.show()
print "misplaced",
x = solve(p, BlockPuzzle(3), misplaced_h)
print "distance",
x = solve(p, BlockPuzzle(3), distance_h)
```
``` 2  6  1
4  8  5
0  3  7
misplaced distance: 24 steps: 14962
distance distance: 24 steps: 862```