search.py 文件源码

def uniformCostSearch(problem):
    """Search the node of least total cost first."""
    "*** YOUR CODE HERE ***"
    startState = problem.getStartState()
    visited = set()
    actions = []
    fringe = util.PriorityQueue()
    fringe.push((startState, None, None, actions), 0)

    while not fringe.isEmpty():
        currPath = fringe.pop()
        currState = currPath[0]
        action = currPath[1]
        stepCost = currPath[2]
        actions = currPath[3]
        if problem.isGoalState(currState):
            return actions
        if not currState in visited:
            visited.add(currState)
            paths = problem.getSuccessors(currState)
            for path in paths:
                if not path[0] in visited:
                    newActions = list(actions)
                    newActions.append(path[1])
                    fringe.push((path[0],path[1],path[2],newActions), problem.getCostOfActions(newActions))
    util.raiseNotDefined()