用8位数计算Python中的曼哈顿距离
我正在尝试在Python中为一个简单的8-Puzzle游戏编写一个简单的A *求解器。 我用这种方式代表了我的比赛的目标：
goal = [[1, 2, 3],
[8, 0, 4],
[7, 6, 5]]
我的问题是，我不知道如何为我的目标写一个简单的曼哈顿距离启发式。 我知道它应该被定义为一个通用状态和我的目标状态之间的距离的总和。 我想我应该编写如下代码：
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
我的问题是，我没有在目标国家的作品的坐标明确的表示，所以我不知道如何定义“x_goal”和“y_goal”为板的“价值”一片。 我正在尝试使用分区和模块操作来实现，但这很困难。
你能给我一些提示来定义我的'x_goal'和'y_goal'变量吗？
谢谢
曼哈顿距离是类似于曼哈顿的道路的出租车距离。 你的公式是正确的
distance += abs(x_value - x_goal) + abs(y_value - y_goal)
其中x_value, y_value是你所在的位置， x_goal, y_goal是你想去的地方。
这个使用mhd的实现使用了这种启发式：mhd在由当前位置的'12346578'中的每一个的索引定义的点与由goal的'12346578'中的每一个的索引定义的点之间
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
还没有尝试。 也许链接是一些帮助。
我有和你一样的问题，我通过编写一个不同的函数来解决这个问题，该函数接受你有的表示并将它转换成你所定义的表示（值/字符对的字典）。
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
那样，你可以得到两全其美的好处。 无论何时您想将网格视为网格，您都可以使用原始列表形式，但如果您只需要快速查找曼哈顿距离函数的值，那么您可以使用新的字典已经创建。
你可以使用它
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
上一篇: Calculating Manhattan Distance in Python in an 8
下一篇: puzzle has a solution in prolog using manhattan distance