A*

Idea: UCS + heuristic estimate of remaining distance: f(s) = g(s) + h(s)

Priority = g(s) + h(s) where

• g(s) is the actual cost from start to s
• h(s) is the estimated cost from s to goal

A_STAR(start, goal, h):
    
    frontier = PriorityQueue()
    push (start, priority=h(start)) into frontier

    best_cost[start] = 0

    while frontier is not empty:

        state = pop state with smallest priority

        if state is goal:
            return path to state

        for each successor next of state:
            
            new_cost = best_cost[state] + edge_cost(state, next)
            if next not seen or new_cost < best_cost[next]:

                best_cost[next] = new_cost
                parent[next] = state
                priority = new_cost + h(next)
                push (next, priority) into frontier

    return failure