曼哈顿距离

Question

计算manhattan distances的最佳方法是什么

我目前的解决方案是：

def distance(state):
    target_state = (1,2,3,4,5,6,7,8,0)
    target_matrix = np.reshape(np.asarray(list(target_state)),(-1,3))
    reshaped_matrix = np.reshape(np.asarray(list(state)),(-1,3))
    dist = 0
    for i in range(1,9):
        dist = dist + (abs(np.where(target_matrix == i)[0][0]
                           - np.where(reshaped_matrix == i)[0][0]) +
                       abs(np.where(target_matrix == i)[1][0]
                           - np.where(reshaped_matrix == i)[1][0]))

    return dist

Answer 1

怎么样

import numpy as np

def summed_manhattan(state):
    shuffle = np.reshape((np.array(state)-1) % 9, (3, 3))
    all_dists = np.abs(np.unravel_index(shuffle, (3, 3)) - np.indices((3, 3)))
    all_dists.shape = 2, 9
    gap = np.where(shuffle.ravel() == 8)[0][0]
    return all_dists[:, :gap].sum() + all_dists[:, gap + 1 :].sum()

这通过避免重复调用where（总计为O（n^2））改进了解决方案。相反，它利用target_state的简单结构，为每个index into state计算持有相同值的index into target_state；置换存储在shuffle中。这个小技巧使算法为O（n），作为奖励，它使向量化变得容易。在

这个解决方案是最优的，在这个意义上，人们显然不能做得比O（n）更好。在