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)
    #3) manhattan dist to closest + manhattan to the unvisited others , gives: total cost of 106,  nodes expanded: 692
    pos = state[0]
    unvisited = list(state[1])
    ret = 0

    while len(unvisited) > 0:
        nextPos = closestCorner(pos, unvisited)
        ret += manhattanDistance(pos, nextPos)
        pos = nextPos
        unvisited.remove(nextPos)
    return ret