Source code online books for professionals by professionals

Listing 9-10.  The A* Algorithm
from heapq import heappush, heappop
inf = float('inf')
 
def a_star(G, s, t, h):
    P, Q = {}, [(h(s), None, s)]                # Preds and queue w/heuristic
    while Q:                                    # Still unprocessed nodes?
        d, p, u = heappop(Q)                    # Node with lowest heuristic
        if u in P: continue                     # Already visited? Skip it
        P[u] = p                                # Set path predecessor
        if u == t: return d - h(t), P           # Arrived! Ret. dist and preds
        for v in G[u]:                          # Go through all neighbors
            w = G[u][v] - h(u) + h(v)           # Modify weight wrt heuristic
            heappush(Q, (d + w, u, v))          # Add to queue, w/heur as pri
    return inf, None                            # Didn't get to t
 
As you can see, except from the added check for u == t, the only difference from Dijkstra’s algorithm is really the 
adjustment of the weights. In other words, if you wanted, you could use a straight point-to-point version of Dijkstra’s 
algorithm (that is, one that included the u == t check) on a graph where you had modified the weights, rather than 
having a separate algorithm for A*.
Of course, in order to get any benefit from the A* algorithm, you need a good heuristic. What this function should 
be will depend heavily on the exact problem you’re trying to solve, of course. For example, if you’re navigating a 
road map, you’d know that the Euclidean distance, as the crow flies, from a given node to your destination must be 
a valid heuristic (lower bound). This would, in fact, be a usable heuristic for any movement on a flat surface, such as 
monsters walking around in a computer game world. If there are lots of blind alleys and twists and turns, though, this 
lower bound may not be very accurate. (See the “If You’re Curious ...” section for an alternative.)

---

Chapter 9 
■
 From a to B with edsger and Friends
205
The A* algorithm is also used for searching solution spaces, which we can see as abstract (or implicit) graphs. 
For example, we might want to solve Rubik’s Cube
9
 or Lewis Carroll’s so-called word ladder puzzle. In fact, let’s have a 
whack at the latter puzzle (no pun intended).
Word ladders are built from a starting word, such as lead, and you want to end up with another word, say, gold. 
You build the ladder gradually, using actual words at every step. To get from one word to another, you can replace a 
single letter. (There are also other versions, which let you add or remove letters, or where you are allowed to swap the 
letters around.) So, for example, you could get from lead to gold via the words load and goad. If we interpret every 
word of some dictionary as a node in our graph, we could add edges between all words that differ by a single letter.  
We probably wouldn’t want to explicitly build such a structure, but we could “fake” it, as shown in Listing 9-11.