search.py 文件源码

def constrainedBreadthFirstSearch(problem, legalStates):
    """
    A breadth-first search that finds a shortest path to a 
    state going only through given states.
    """
    # we need a set to remember all visited states
    visitedStates = set()

    # DFS works in LIFO fashion
    searchQueue = Queue()

    # add an initial state so the stack is not empty
    startState = problem.getStartState()
    startNode = SearchNode(startState)
    searchQueue.push(startNode)

    # iterate until completion
    while not searchQueue.isEmpty():
        currentNode = searchQueue.pop()
        currentState = currentNode.position

        # check for end
        if problem.isGoalState(currentState):
            return currentNode.backtrack()

        if currentState in visitedStates: 
            continue

        visitedStates.add(currentState)

        for futureState, move, _ in problem.getSuccessors(currentState):
            if futureState not in visitedStates and futureState in legalStates: 
                futureNode = SearchNode(futureState, parent=currentNode, transition=move)
                searchQueue.push(futureNode)

    print "Search finished, final state not found!"
    return