我目前正在编写一种算法，该算法通过Python的A*搜索算法解决8谜游戏。但是，当我对代码进行计时时，我发现get_manhattan_distance花费的时间非常长。
我用 Python 的cProfile运行了我的代码，结果低于程序打印出来的结果。这是我问题的要点。
我已经通过使用 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。
不幸的是，这种计算需要很长时间，因为有数十万个不同的板。有没有办法加快这个计算速度？
在我看来，你只需要计算一次整个板的完整曼哈顿距离总和——对于第一块板。之后，您将通过交换两个相邻的数字从现有实体创建新的Board实体。新板上的总曼哈顿距离将仅因这两个数字的曼哈顿距离变化之和而有所不同。
如果其中一个数字是空白(0)，则总距离会根据非空白数是靠近其正确位置还是远离其位置而变化减一或一。如果两个数字都不是空的，例如当您制作"双胞胎"时，总距离会以负 2、0 或 2 变化。
这是我要做的：添加一个manhattan_distance = None参数到Board.__init__。如果未给出，请计算板的总曼哈顿距离;否则只需存储给定的距离。创建您的第一个板，没有此参数。从现有板创建新板时，请计算总距离的变化并将结果传递给新板。(cached_manhattan变得无关紧要。
这应该会减少与距离相关的计算总数 - 我希望它会加快几倍，你的电路板尺寸越大。