在8难题游戏中使用Python计算曼哈顿距离

Question

我正在尝试用Python编写一个简单的A *求解器，以编写一个简单的8-Puzzle游戏。我以这种方式表示了我的游戏目标：

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'变量吗？

谢谢

Answer 1

曼哈顿距离是类似于曼哈顿的道路上的出租车距离。你的公式是对的

distance += abs(x_value - x_goal) + abs(y_value - y_goal)

wherex_value, y_value是你所在的地方，x_goal, y_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

还没试过。也许链接有一些帮助。