searchAgents.py 文件源码

def cornersHeuristic(state, problem):
  """
  A heuristic for the CornersProblem that you defined.

    state:   The current search state
             (a data structure you chose in your search problem)

    problem: The CornersProblem instance for this layout.

  This function should always return a number that is a lower bound
  on the shortest path from the state to a goal of the problem; i.e.
  it should be admissible (as well as consistent).
  """
  corners = problem.corners # These are the corner coordinates
  walls = problem.walls # These are the walls of the maze, as a Grid (game.py)
  currentState = state[0]
  score = 0

  #find unvisited corners
  unvistedList = list()
  for corner in corners:
      unvistedList.append(corner)
      if corner in state[1]:
          unvistedList.remove(corner)

  #repeats for all unvisited corners
  for r in range(len(unvistedList)):
      smallestManhattan = 99999

      #calculate distance to nearest corner
      for unvistedCorner in unvistedList:
          dist = manhattanHeuristic(currentState, unvistedCorner)
          if dist < smallestManhattan:
              smallestManhattan = dist #set distance to nearest corner
              nearestCorner = unvistedCorner

      score += smallestManhattan #add distance to score
      unvistedList.remove(nearestCorner) #removes corner from unvisited list
      currentState = nearestCorner #updates position to the nearest corner

  return score