search.py 文件源码

def breadthFirstSearch(problem):
    """Search the shallowest nodes in the search tree first."""
    "*** YOUR CODE HERE ***"

    "the only change here is that queue structure, so we can search from 1 layer to another layer"
    "not like Stack, we pop and search all the way to the goal node, but we need to expand more to find"
    "the goal node"
    "use queue to store all the same layer node,and always pop first node in the layer"
    nodeQueue = util.Queue()
    visited = []
    path = []
    startNode = (problem.getStartState(),path)
    nodeQueue.push(startNode)

    "start while loop to find the path"

    while  nodeQueue.isEmpty() is False:
        node, path = nodeQueue.pop()

        if problem.isGoalState(node):
            return path
        visited.append(node)
        for successor, direction, cost in problem.getSuccessors(node) :
            if successor not in visited:
                visited.append(successor)
                newNode = (successor,path+[direction])
                nodeQueue.push(newNode)

    return None
    util.raiseNotDefined()