search.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())
    """
    "*** YOUR CODE HERE ***"

    nodeStack = util.Stack()
    visited = []
    path = []
    startNode = (problem.getStartState(),visited,path)
    nodeStack.push(startNode)

    "start while loop to find the path"

    while  nodeStack.isEmpty() is False:
        (node, visited, path) = nodeStack.pop()
        "check results before go to successors"
        if problem.isGoalState(node):
            return path
        for successor, direction, cost in problem.getSuccessors(node) :
            if successor not in visited:
                newNode = (successor,visited+[successor],path+[direction])
                nodeStack.push(newNode)


    return None
    util.raiseNotDefined()