search.py 文件源码

def aStarSearch(problem, heuristic=nullHeuristic):

    """Search the node that has the lowest combined cost and heuristic first."""
    "*** YOUR CODE HERE ***"
    "it is very similar to UCS, just change the totalcost to the heuristic + cost  "
    nodePriorityQueue = util.PriorityQueue()
    visited = []
    path = []
    totalCost = heuristic(problem.getStartState(),problem)
    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])
                totalCost = problem.getCostOfActions(path + [direction]) + heuristic(successor,problem)
                nodePriorityQueue.push(newNode,totalCost)
            if problem.isGoalState(successor):
                newNode =(successor,path + [direction])
                totalCost = problem.getCostOfActions(path + [direction]) + heuristic(successor,problem)
                nodePriorityQueue.push(newNode,totalCost)


    return None


    util.raiseNotDefined()


# Abbreviations