有没有更有效的算法来计算 8 拼图游戏的曼哈顿距离？

Question

我目前正在编写一个算法，通过 Python 的 A* 搜索算法解决 8 拼图游戏。但是，当我对我的代码计时时，我发现 get_manhattan_distance 需要很长时间。

我运行我的代码 cProfile for Python，结果低于程序打印的结果。 Here is a gist 我的问题。

我已经通过使用 Numpy 数组而不是 Python 的列表进行复制来提高我的程序的效率。我不太清楚如何使这一步更有效率。我当前 get_manhattan_distance 的代码是

def get_manhattan(self):
    """Returns the Manhattan heuristic for this board

    Will attempt to use the cached Manhattan value for speed, but if it hasn't 
    already been calculated, then it will need to calculate it (which is 
    extremely costly!).
    """
    if self.cached_manhattan != -1:
      return self.cached_manhattan

    # Set the value to zero, so we can add elements based off them being out of
    # place.
    self.cached_manhattan = 0

    for r in range(self.get_dimension()):
      for c in range(self.get_dimension()):
        if self.board[r][c] != 0:
          num = self.board[r][c]

          # Solves for what row and column this number should be in.
          correct_row, correct_col = np.divmod(num - 1, self.get_dimension())

          # Adds the Manhattan distance from its current position to its correct
          # position.
          manhattan_dist = abs(correct_col - c) + abs(correct_row - r)
          self.cached_manhattan += manhattan_dist

    return self.cached_manhattan

这背后的想法是，3x3 网格的目标拼图如下：

 1  2  3
 4  5  6
 7  8

其中有一个空白图块（空白图块在 int 数组中由 0 表示）。所以，如果我们有这个谜题：

 3  2  1
 4  6  5
 7  8

它的曼哈顿距离应该是 6。这是因为，3 距离它应该在的地方有两个地方。 1 离它应该在的地方有两个地方。 5 离应该的地方差一位，6 离应该的地方差一位。因此，2 + 2 + 1 + 1 = 6.

不幸的是，这个计算需要很长时间，因为有数十万个不同的板。有什么方法可以加快计算速度吗？

Answer 1

在我看来，您应该只需要为第一块板计算一次整个板的完整曼哈顿距离总和。之后，您将通过交换两个相邻数字从现有实体创建新的 Board 实体。新板上的曼哈顿总距离仅与这两个数字的曼哈顿距离变化之和不同。

如果其中一个数字是空白 (0)，则总距离会根据非空白数字是靠近还是远离它的正确位置而变化负一或一。如果两个数字都不为空，就像您制作 "twins" 时一样，总距离会变化负二、零或负二。

我会这样做：向 Board.__init__ 添加一个 manhattan_distance = None 参数。如果没有给出，计算板的总曼哈顿距离；否则只需存储给定的距离。在没有这个参数的情况下创建你的第一个板。当您从现有板创建新板时，计算总距离的变化并将结果传递给新板。（cached_manhattan 变得无关紧要。）

这应该会大大减少涉及距离的计算总数 - 我希望它能将速度提高几倍，电路板尺寸越大速度越快。

有没有更有效的算法来计算 8 拼图游戏的曼哈顿距离？

Is there a more efficient algorithm to calculate the Manhattan distance of a 8-puzzle game?

python

performance

heuristics