search.py 文件源码

def aStarSearch(problem, heuristic=nullHeuristic):
  "Search the node that has the lowest combined cost and heuristic first."
  "*** YOUR CODE HERE ***"
  frontier = util.PriorityQueue()
  visited = []
  h = heuristic(problem.getStartState(), problem)
  g = 0
  f = g + h
  startingNode = (problem.getStartState(), None, g, []);
  frontier.push(startingNode, f)
  while not frontier.isEmpty():
    curr = frontier.pop()
    currLoc = curr[0]
    currDir = curr[1]
    currCost = curr[2]
    if currLoc not in visited:
      currPath = curr[3]
      visited.append(currLoc)
      successors = problem.getSuccessors(currLoc)
      successorsList = list(successors)
      for i in successorsList:
        if i[0] not in visited:
          if(problem.isGoalState(i[0])):
            return currPath + [i[1]]
          h = heuristic(i[0], problem)
          g = currCost + i[2]
          f = g + h
          newNode = (i[0], i[1], g, currPath+[i[1]])
          frontier.push(newNode, f)
  return []

# Abbreviations