def breadthFirstSearch(problem, heuristic):
    """Search the shallowest nodes in the search tree first."""
    "*** YOUR CODE HERE ***"
    """print "Start:", problem.getStartState()
    print "Is the start a goal?", problem.isGoalState(problem.getStartState())
    print "Start's successors:", problem.getSuccessors(problem.getStartState())    """
    current = (problem.getStartState(), "Stop" , 0xFFF)
    actions = []
    while True:
        cost=0xFFF
        for n in problem.getSuccessors(current[0]):
            if(heuristic(n[0], problem)<cost):
                neighbor = n
                cost=heuristic(n[0], problem)

        if heuristic(neighbor[0], problem) >= heuristic(current[0], problem):
            return actions
        current = neighbor
        actions.append(current[1])

    return []