是否有更有效的算法来计算8-puzzle游戏的曼哈顿距离？

Question

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

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

通过使用Numpy Arrays而不是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），则总距离会减去一或一，这取决于非空白数字是否移近其正确位置或距离它更远。如果两个数字都是非空白的，就像你制作“双胞胎”一样，总距离会减去两，零或两。

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

这应该会减少与距离有关的计算总数 - 我希望它可以将速度提高几倍，更多的是你的电路板尺寸。