计算八个难题中的曼哈顿距离

Question

我正在研究一个程序,使用带有启发式的知情搜索来解决Python中的Eight Puzzle.我们应该使用的启发式是曼哈顿距离.所以对于像这样的董事会:

 State            Goal        Different Goal
7  2  4         1  2  3           1  2  3
5     6         8     4           4  5  6
8  3  1         7  6  5           7  8

曼哈顿距离将是 4 + 0 + 3 + 3 + 1 + 0 + 2 + 1 = 14

在视觉上,很容易计算出一定数量的空格数,但在Python中我将一个板表示为一个列表,因此上面的板将是[7, 2, 4, 5, 0, 6, 8, 3, 1]目标状态[1, 2, 3, 4, 5, 6, 7, 8, 9, 0].我一直在努力尝试使用mod工作,但似乎无法让它正常工作.我的老师说使用mod会有助于弄清楚如何做到这一点.我看到的一些例子使用了2d数组,abs(x_val - x_goal) + abs(y_val - y_goal)这是有意义的,但由于我使用的是列表,我不知道如何实现它.我到目前为止的代码是:

distance = 0
xVal = 0
yVal = 0
for i in range(len(self.layoutList)):
    pos = self.layoutList.index(i)
    if pos i == 0 or pos i == 1 or pos i == 2:
        xVal = pos
        yVal = 0
    if pos i == 3 or pos i == 4 or pos i == 5:
        xVal = pos - 3
        yVal = 1
    if pos i == 6 or pos i == 7 or pos i == 8:
        xVal = pos - 6
        yVal = 2

这将为每个图块生成x,y值.所以上述表示的状态[7, 2, 4, 5, 0, 6, 8, 3, 1]将产生(0, 0)7,(2, 0)4,等我会实现这个为goalstate得到X同样的方式,y坐标为.然后我会取x-val的绝对值 - x_goal和诸如此类的东西.但是有没有更好/更有效的方法直接从列表中执行此操作而不是使用2 for循环来迭代这两个列表？

Answer 1

总结每个数字的曼哈顿距离:

>>> board = [7, 2, 4, 5, 0, 6, 8, 3, 1]
>>> sum(abs((val-1)%3 - i%3) + abs((val-1)//3 - i//3)
        for i, val in enumerate(board) if val)
14

例如,7属于(从零开始)坐标(0,2)=((7-1)%3,(7-1)//3)但是在坐标(0,0)处,因此abs(0 - 0) + abs(2 - 0)为它添加.

对于非标准目标:

>>> goal = [1, 2, 3, 8, 0, 4, 7, 6, 5]
>>> sum(abs(b%3 - g%3) + abs(b//3 - g//3)
        for b, g in ((board.index(i), goal.index(i)) for i in range(1, 9)))
16