Calculating Manhattan Distance in Python in an 8
I am trying to code a simple A* solver in Python for a simple 8-Puzzle game. I have represented the goal of my game in this way:
goal = [[1, 2, 3],
[8, 0, 4],
[7, 6, 5]]
My problem is that I don't know how to write a simple Manhattan Distance heuristic for my goal. I know it should be defined as the sum of the distances between a generic state and my goal state. I think I should code something like:
def manhattan_distance(state):
distance = 0
for x in xrange(3):
for y in xrange(3):
value = state[x][y]
x_value = x
y_value = y
x_goal = ...?
y_goal = ...?
distance += abs(x_value - x_goal) + abs(y_value - y_goal)
return distance
My problem is that I don't have an explicit representation of the coordinates of the pieces in the goal state, so I don't know how to define 'x_goal' and 'y_goal' for the 'value' piece of the board. I am trying to do it using division and module operations, but it's difficult.
Can you give me some hints to define my 'x_goal' and 'y_goal' variables?
Thank you
Manhattan distance is the taxi distance in road similar to those in Manhattan. You are right with your formula
distance += abs(x_value - x_goal) + abs(y_value - y_goal)
where x_value, y_value is where you are and x_goal, y_goal is where you want to go.
This implementation using mhd uses this heuristic: the mhd between the point defined by the indices of each of '12346578' in current position and the point defined by the indices of each of '12346578' in goal
def h(self, node):
"""Heuristic for 8 puzzle: returns sum for each tile of manhattan
distance between it's position in node's state and goal"""
sum = 0
for c in '12345678':
sum =+ mhd(node.state.index(c), self.goal.index(c))
return sum
Didnt try yet. Maybe link is of some help.
I had the exact same question that you had, and I solved it by writing a different function that takes the representation you have and translates it into the representation you settled on (dictionary of value/coordinate pairs).
def make_dict(state):
coordinate_dict = {}
for x, row in enumerate(state):
for y, value in enumerate(row):
coordinate_dict[value] = (x, y)
return coordinate_dict
That way, you get the best of both worlds. Whenever you want to treat the grid as a grid, you can use the original list-of-lists form, but if all you need is a quick lookup of where the value is for the Manhattan distance function, you can use the new dictionary you've created.
你可以使用它
def manhatan_dist(board,goal_stat):
#Manhattan priority function. The sum of the Manhattan distances
#(sum of the vertical and horizontal distance) from the blocks to their goal positions,
#plus the number of moves made so far to get to the search node.
import math
b = board
g = goal_stat
manh_dist = 0
for i in range (0,3,1):
for j in range (0,3,1):
bij = b[i][j]
i_b = i
j_b = j
i_g, j_g = value_index(g,bij)
manh_dist += (math.fabs(i_g - i_b) + math.fabs(j_g - j_b))
return manh_dist
下一篇: 用8位数计算Python中的曼哈顿距离