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)
"*** YOUR CODE HERE ***"
def euclid(x, y):
return ((x[0]-y[0])**2 + (x[1]-y[1])**2)**0.5
def manhattan(x, y):
return (abs(x[0]-y[0]) + abs(x[1]-y[1]))
current_position = state[:2]
corners_state = state[2:]
corners_not_seen = [corners[i] for i in range(4) if corners_state[i]==0]
#print('start', state[:2])
#print('corners not seen', corners_not_seen)
val = 0 # heuristic value to return
for i in range(len(corners_not_seen)):
d_euclid = [[c, manhattan(current_position, c)] for c in corners_not_seen]
d_euclid.sort(key=lambda x: x[1])
#print d_euclid[0][1]
val += d_euclid[0][1] # move to the closest corner
current_position = d_euclid[0][0] # update the current position to the new corner position
corners_not_seen.remove(d_euclid[0][0]) # we have seen this corner now
#print('corners not seen at end', corners_not_seen)
#print('dist to goal', val)
return val
评论列表
文章目录
