在 8 拼图游戏中用 Python 计算曼哈顿距离
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/16318757/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Calculating Manhattan Distance in Python in an 8-Puzzle game
提问by JohnQ
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:
我正在尝试用 Python 为一个简单的 8-Puzzle 游戏编写一个简单的 A* 求解器。我以这种方式表达了我的游戏目标：
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.
我的问题是我没有明确表示目标状态中棋子的坐标，所以我不知道如何为棋盘的“值”部分定义“x_goal”和“y_goal”。我正在尝试使用除法和模块操作来做到这一点，但这很困难。
Can you give me some hints to define my 'x_goal' and 'y_goal' variables?
你能给我一些提示来定义我的“x_goal”和“y_goal”变量吗？
Thank you
谢谢
回答by kiriloff
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_valueis where you are and x_goal, y_goalis where you want to go.
x_value, y_value你在哪里，哪里x_goal, y_goal就是你想去的地方。
This implementation using mhduses 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
这个使用 mhd 的实现使用了这种启发式：当前位置中每个 '12346578' 的索引定义的点与中每个 '12346578' 的索引定义的点之间的 mhdgoal
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.
还没试。也许链接有一些帮助。
回答by Scott Handelman
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.
这样，您就可以两全其美。每当您想将网格视为网格时，您都可以使用原始列表列表形式，但如果您只需要快速查找曼哈顿距离函数的值，您可以使用新的字典已经创建了。
回答by Hila
you may be able to use it
你也许可以使用它
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
回答by bad programmer
Most pythonic implementation you can find.
您可以找到的大多数pythonic实现。
assuming that,
假如说，
0 1 2
3 4 5
6 7 8
0 1 2
3 4 5
6 7 8
is the goal state... AND,
是目标状态......并且，
1 5 3
4 2 6
7 8 9
1 5 3
4 2 6
7 8 9
is the final state.
是最终状态。
initial_state = [1,5,3,4,2,6,7,8,0]
goal_state = [0,1,2,3,4,5,6,7,8]
def calculateManhattan(initial_state):
initial_config = initial_state
manDict = 0
for i,item in enumerate(initial_config):
prev_row,prev_col = int(i/ 3) , i % 3
goal_row,goal_col = int(item /3),item % 3
manDict += abs(prev_row-goal_row) + abs(prev_col - goal_col)
return manDict
I don't know how else to explain this. It just works. Enjoy ! :D
我不知道如何解释这一点。它只是有效。享受 ！:D
