Pista Ejercicio 1 - Laboratorio Algoritmos de Búsqueda

depthFirstSearch.py

def depthFirstSearch(problem):
    """
    Search the deepest nodes in the search tree first.
    Your search algorithm needs to return a list of actions that reaches the
    goal. Make sure to implement a graph search algorithm.
    To get started, you might want to try some of these simple commands to
    understand the search problem that is being passed in:
    print("Start:", problem.getStartState())
    print("Is the start a goal?", problem.isGoalState(problem.getStartState()))
    print("Start's successors:", problem.getSuccessors(problem.getStartState()))
    """
    closed = set()
    fringe = util.Stack()
    # cada nodo corresponde a una tupla (state, path)
    fringe.push((problem.getStartState(),[]))

    while not fringe.isEmpty():
        node = fringe.pop()
        if problem.isGoalState(node[0]):
            return node[1]
        
        if node[0] not in closed:
            closed.add(node[0])
            for child_state, action, cost in problem.getSuccessors(node[0]):
                fringe.push((child_state, node[1] + [action]))