n_puzzle问题曼哈顿距离计算咨询，现有错位数统计代码求改进建议

实现思路 #

你要计算的曼哈顿距离，是每个非0数字的当前坐标到目标坐标的横向差绝对值加纵向差绝对值的总和，具体修改逻辑如下：

• 第一步：预先生成目标状态的数字坐标映射表，避免每次计算都重复遍历目标状态
• 第二步：遍历当前拼图的每个格子，对非0的数字，查表拿到目标坐标，计算曼哈顿距离累加即可
• 注意：空白块0不需要计入距离总和

def GetDist(self):
    if self.value == self.goal:
        return 0
    # 构建目标状态的数字-坐标映射
    goal_pos = {}
    for i, row in enumerate(self.goal[2:]):
        for j, num in enumerate(row):
            goal_pos[num] = (i, j)
    dist = 0
    # 遍历当前状态计算每个非空方块的曼哈顿距离
    for i, row in enumerate(self.value[2:]):
        for j, num in enumerate(row):
            if num != 0:
                target_i, target_j = goal_pos[num]
                dist += abs(i - target_i) + abs(j - target_j)
    return dist

优化建议 #

• 如果你的目标状态是固定不变的，可以把goal_pos的构建放到类的初始化方法里，不用每次计算距离都重复生成，能显著提升运行效率
• 如果需要更优的启发式函数，可以在曼哈顿距离基础上加上线性冲突的惩罚，能有效减少A*算法的搜索节点数

内容的提问来源于stack exchange，提问作者user13413898