search.py 文件源码

def breadthFirstSearch(problem):
    """Search the shallowest nodes in the search tree first."""
    "*** YOUR CODE HERE ***"
    startState = problem.getStartState()
    visited = set()
    fringe = util.Queue()
    fringe.push((startState, ()))

    while not fringe.isEmpty():
        currNode = fringe.pop()
        currState = currNode[0]
        currPlan = currNode[1]
        if problem.isGoalState(currState):
            return list(currPlan)
        if not currState in visited:
            visited.add(currState)
            paths = problem.getSuccessors(currState)
            for path in paths:
                newPlan = list(currPlan)
                newPlan.append(path[1])
                nextNode = (path[0], tuple(newPlan))
                if not path[0] in visited:
                    fringe.push(nextNode)