在Python中计算8-Puzzle游戏中的曼哈顿距离

Question

我正在尝试使用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' 变量吗？

谢谢

- JohnQ

---

你使用除法和取模运算符是正确的。在编写代码之前，尝试在纸上计算公式。 - Colonel Panic

我看到其他实现使用除法和取模运算，但它们以不同的方式定义目标状态。 我的问题是我找不到第二行和第三行目标状态元素之间的任何共同点... - JohnQ

怎么样：重新标记这些块，使目标变为012345678（更容易思考）。解决（教科书）。恢复原始标签。 - Colonel Panic

我已经将目标状态的表示方式更改为带有坐标的标签字典。我不知道是否有更好的解决方案，但现在它可以工作了。无论如何，谢谢！ - JohnQ

Answer 1

你可以找到最具Python风格的实现。

假设，

0 1 2

3 4 5

6 7 8

是目标状态... 并且，

1 5 3

4 2 6

7 8 9

是最终状态。

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

我不知道该如何解释这个。它只是有效的。享受吧！:D

- bad programmer

Answer 2

曼哈顿距离是指在类似曼哈顿的道路上的出租车距离。你的公式是正确的。

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

x_value, y_value 表示当前位置，x_goal, y_goal 表示目标位置。

此实现使用MHD启发式算法：计算当前位置中“12346578”每个索引号所定义的点与目标位置中“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

尚未尝试。也许链接会有所帮助。

- kiriloff

---

我知道这个方法可以工作，但是像这样的一个方法会比我试图编写的方法更加复杂... - JohnQ

Answer 3

你可能能够使用它

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

- Hila

---

value_index是什么？ - Matt G

Answer 4

我曾经和你一样有同样的问题，但我通过编写一个不同的函数来解决它，该函数将您拥有的表示形式转换为您选择的表示形式（值/坐标对的字典）。

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

这样，你就可以兼顾两全。每当你想把网格视为网格时，你可以使用原始的列表形式，但如果你只需要快速查找曼哈顿距离函数的值所在的位置，你可以使用新创建的字典。

- Scott Handelman