search.py 文件源码

def uniformCostSearch(problem):
    """Search the node of least total cost first."""
    "*** YOUR CODE HERE ***"

    "we use PriorityQueue data structure, 'smart queue' "
    "struture and help us to find the lower cost of action"
    "use PriorityQueue to detect which route is shortest, and pop the shortest route"

    nodePriorityQueue = util.PriorityQueue()
    visited = []
    path = []
    totalCost = 0
    startNode =(problem.getStartState(),path)
    nodePriorityQueue.push((startNode),totalCost)

    "start while loop to find the correct path"

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

        visited.append(node)

        if problem.isGoalState(node):
            return path

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

    return None


    util.raiseNotDefined()