A* Interactive Tutorial

Click on Run Example A* to see the algorithm compute the path from start to goal. Then try the Interactive A* mode!

Click the next node on the A* path to follow the optimal route from start to goal.

Answer each question about A*: f(n)=g(n)+h(n), admissible/consistent heuristics, and min-heap selection.

Fill in the blanks in the A* skeleton to practice selecting the min-f node and updating f.

from collections import defaultdict

def astar(graph, start, goal, h):
    open_set = { start }
    came_from = {}
    g = defaultdict(lambda: float('inf'))
    f = defaultdict(lambda: float('inf'))

    g[start] = 0
    f[start] = h(start)

    while open_set:
        # choose node in open_set with the smallest f-score
        current =    # blank #1

        if current == goal:
            return reconstruct_path(came_from, current)

        open_set.remove(current)
        for nb in graph[current]:
            # assume unit edge cost if not otherwise provided
            tentative = g[current] + cost(current, nb)
            if tentative < g[nb]:
                came_from[nb] = current
                g[nb] = tentative
                # update f with g + h
                f[nb] =    # blank #2
                open_set.add(nb)

A* Search (A*) — Interactive Tutorial