我正在尝试使用Python编写简单的A*求解器来解决8数码难题。
我已经用以下方式表示了游戏的目标:
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
我的问题是,我没有关于目标状态中每个方格坐标的明确表示,因此我不知道如何为棋盘上的 'value' 方块定义 'x_goal' 和 'y_goal'。我正在尝试使用除法和模运算来完成它,但很困难。
你能给我一些提示来定义我的 'x_goal' 和 'y_goal' 变量吗?
谢谢