A* algorithm skeleton

astar.py

def aStarSearch(problem, heuristic=nullHeuristic):
    from sets import Set
    visited = Set()
    start = problem.getStartState()
    from util import PriorityQueue
    frontLine = PriorityQueue()
    startPri = 0 + heuristic(start, problem)
    frontLine.push((start, [], 0), startPri)
    while not frontLine.isEmpty():
        (point, actions, cost) = frontLine.pop()
        visited.add(point)
        if problem.isGoalState(point):
            return actions
        for (p, action, stepCost) in (s for s in problem.getSuccessors(point) if s[0] not in visited):
            newCost = cost + stepCost
            newActions = actions[:]
            newActions.append(action)
            newPri = newCost + heuristic(p, problem)
            frontLine.push((p, newActions, newCost), newPri)