Skip to content
Hello Python
Algorithm1 Practice1 Interview

A* Search

Prioritize path states by cost-so-far plus an admissible heuristic toward the goal. Learn the algorithm's preconditions, state transition, correctness argument, Python cost model, and transfer from one focused drill to a full Interview Problem.

Recognize it when

Consider A* Search when the prompt's constraints and required operations match this shape: Prioritize path states by cost-so-far plus an admissible heuristic toward the goal.

Pybit demonstrates A* Search in a professional Python interview workspace.
On this page · Prioritize Cost So Far Plus Heuristic

Checking your account…

Sign in to save your code and progress across devices. The lesson and problem statement remain public.

A* Search Code Labs

Prioritize Cost So Far Plus Heuristic

A* orders frontier states by f = g + h: exact cost g from the start plus estimated remaining cost h to the goal. The heuristic changes exploration order, not the path-cost definition.

Require an Admissible Heuristic

An admissible heuristic never overestimates the true remaining cost. A consistent heuristic additionally obeys a triangle-like inequality, making finalized-state handling simpler.

Trace A-Star Priorities

Reference
def priority_trace(costs,heuristics):
    return [[node,costs[node],heuristics[node],costs[node]+heuristics[node]] for node in sorted(costs,key=lambda node:(costs[node]+heuristics[node],node))]
Practice

Implement priority_trace(costs,heuristics). Return [node,g,h,f] sorted by f then node for matching dictionaries.

Public tests

  • Order by cost plus heuristic

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Reopen States When Costs Improve

Store best known g separately from heap priorities. If a cheaper path reaches a state, update it and push a new entry; skip stale entries whose g no longer matches.

Find Grid Cost with A-Star

Reference
import heapq

def grid_a_star(grid,start,goal):
    rows,cols=len(grid),len(grid[0]);cost={tuple(start):0};heap=[(abs(start[0]-goal[0])+abs(start[1]-goal[1]),0,tuple(start))]
    while heap:
        _,current,node=heapq.heappop(heap)
        if current!=cost[node]:continue
        if node==tuple(goal):return current
        for dr,dc in ((1,0),(-1,0),(0,1),(0,-1)):
            neighbor=(node[0]+dr,node[1]+dc)
            if 0<=neighbor[0]<rows and 0<=neighbor[1]<cols and grid[neighbor[0]][neighbor[1]]==0:
                candidate=current+1
                if candidate<cost.get(neighbor,float("inf")):
                    cost[neighbor]=candidate;heuristic=abs(neighbor[0]-goal[0])+abs(neighbor[1]-goal[1]);heapq.heappush(heap,(candidate+heuristic,candidate,neighbor))
    return -1
Practice

Implement grid_a_star(grid,start,goal). Zero cells are open, one cells blocked; return shortest orthogonal step count or -1 using Manhattan heuristic.

Public tests

  • Use admissible Manhattan guidance

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Choose A Star or Dijkstra

Choose A* when a meaningful admissible heuristic guides a single-pair search. Choose Dijkstra when no useful heuristic exists or distances to many targets are needed. With h = 0, A* is Dijkstra.

Explain It in an Interview

Say: “g is known cost, h is a lower bound on remaining cost, so f prioritizes promising states without excluding an optimal path.” State admissibility or consistency, stale entries, unreachable output, and heuristic cost.

Python Version Note

Complexity & Invariants

Interview bounds depend on the stated representation, input model, and real Python operations.

OperationAverageWorstInterview note
A* Search complete workflowO(RC log(RC))O(RC log(RC))Use a min-heap ordered by g+h, Manhattan h, and a separate best-known g-score map.

Space

O(RC) for the focused Navigate a Grid with A* implementation.

Assumptions

  • Manhattan distance never overestimates four-directional remaining cost. Relaxation preserves best known g-scores, so the first non-stale goal removal has shortest path length.
  • The bound counts Python sorting, slicing, hashing, heap, recursion, and container-copy costs rather than treating syntax as free.

Invariants Worth Saying Aloud

  1. State the precise A* Search invariant before coding and preserve it after every update, traversal step, or recursive return.
  2. Distances are upper bounds backed by concrete discovered paths.
  3. A finalized distance cannot later be improved under the stated weight assumptions.
  4. Use Manhattan distance as an admissible heuristic. Preserve this claim after every transition.
  5. Relax a cell only when its g-score improves. Preserve this claim after every transition.

When To Use Or Avoid A* Search

Use It When

  • Use A* Search when this precondition is stated or can be proved: Edge direction and weight constraints match the relaxation and finalization rules of the chosen method.
  • Use it when this maintained state removes repeated work: Distances are upper bounds backed by concrete discovered paths.

Choose Another Tool When

  • Avoid A* Search when this precondition is absent: Edge direction and weight constraints match the relaxation and finalization rules of the chosen method.
  • Avoid it when a simpler direct scan satisfies the constraints with less implementation risk.

Common Pitfalls

These are the mistakes most likely to survive a happy-path example and fail a boundary case.

Applying the algorithm without its precondition

Verify algorithm preconditions such as sorted input, nonnegative weights, acyclicity, or admissible heuristics before applying it.

Prevent it: State and verify this precondition before coding: Edge direction and weight constraints match the relaxation and finalization rules of the chosen method.

Avoid

def astar_path_length(grid, start, goal):
    pass

Use instead

def astar_path_length(grid, start, goal):
    import heapq
    rows, cols = len(grid), len(grid[0])
    start, goal = tuple(start), tuple(goal)
    def heuristic(cell):
        return abs(cell[0] - goal[0]) + abs(cell[1] - goal[1])
    distance = {start: 0}
    frontier = [(heuristic(start), 0, start)]
    while frontier:
        _, cost, cell = heapq.heappop(frontier)
        if cost != distance[cell]:
            continue
        if cell == goal:
            return cost
        row, col = cell
        for neighbor in ((row+1,col),(row-1,col),(row,col+1),(row,col-1)):
            r, c = neighbor
            if 0 <= r < rows and 0 <= c < cols and grid[r][c] == 0 and cost + 1 < distance.get(neighbor, float('inf')):
                distance[neighbor] = cost + 1
                heapq.heappush(frontier, (cost + 1 + heuristic(neighbor), cost + 1, neighbor))
    return -1

Where you will hit this: Navigate a Grid with A*(opens in a new tab)

Breaking the state transition

Returns Manhattan distance even when walls require a detour.

Prevent it: Preserve this proof obligation: Every recorded distance is a valid path cost, and the method eventually considers every path that could improve it.

Avoid

def astar_path_length(grid,start,goal):
    return abs(start[0]-goal[0])+abs(start[1]-goal[1])

Use instead

def astar_path_length(grid, start, goal):
    import heapq
    rows, cols = len(grid), len(grid[0])
    start, goal = tuple(start), tuple(goal)
    def heuristic(cell):
        return abs(cell[0] - goal[0]) + abs(cell[1] - goal[1])
    distance = {start: 0}
    frontier = [(heuristic(start), 0, start)]
    while frontier:
        _, cost, cell = heapq.heappop(frontier)
        if cost != distance[cell]:
            continue
        if cell == goal:
            return cost
        row, col = cell
        for neighbor in ((row+1,col),(row-1,col),(row,col+1),(row,col-1)):
            r, c = neighbor
            if 0 <= r < rows and 0 <= c < cols and grid[r][c] == 0 and cost + 1 < distance.get(neighbor, float('inf')):
                distance[neighbor] = cost + 1
                heapq.heappush(frontier, (cost + 1 + heuristic(neighbor), cost + 1, neighbor))
    return -1

Where you will hit this: Navigate a Grid with A*(opens in a new tab)

Hiding Python work in the claimed bound

Include visited state, boundary cases, recursion depth, and hidden copying costs in correctness and complexity analysis.

Prevent it: Count every sort, slice, copy, membership check, heap update, and recursive frame before claiming O(RC log(RC)).

Avoid

def astar_path_length(grid,start,goal):
    return abs(start[0]-goal[0])+abs(start[1]-goal[1])

Use instead

def astar_path_length(grid, start, goal):
    import heapq
    rows, cols = len(grid), len(grid[0])
    start, goal = tuple(start), tuple(goal)
    def heuristic(cell):
        return abs(cell[0] - goal[0]) + abs(cell[1] - goal[1])
    distance = {start: 0}
    frontier = [(heuristic(start), 0, start)]
    while frontier:
        _, cost, cell = heapq.heappop(frontier)
        if cost != distance[cell]:
            continue
        if cell == goal:
            return cost
        row, col = cell
        for neighbor in ((row+1,col),(row-1,col),(row,col+1),(row,col-1)):
            r, c = neighbor
            if 0 <= r < rows and 0 <= c < cols and grid[r][c] == 0 and cost + 1 < distance.get(neighbor, float('inf')):
                distance[neighbor] = cost + 1
                heapq.heappush(frontier, (cost + 1 + heuristic(neighbor), cost + 1, neighbor))
    return -1

Where you will hit this: Lowest Common Ancestor in a BST(opens in a new tab)

Reviewed References

Official Python documentation supports language behavior. Canonical problem pages provide additional practice context.