search.py 文件源码

def aStarSearch(problem, heuristic=nullHeuristic):
    """Search the node that has the lowest combined cost and heuristic first."""
    "*** YOUR CODE HERE ***"
    startState = problem.getStartState()
    visited = set()
    fringe = util.PriorityQueue()
    fringe.push((startState, ()), heuristic(startState,problem))

    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, heuristic(path[0],problem) 
                            + problem.getCostOfActions(newPlan)) 

# Abbreviations