曼哈顿距离

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() 

这通过避免重复调用到提高您的解决方案（合计为O（n^2））。相反，利用target_state的简单结构，它会针对每个索引计算进入具有相同值的target_state的索引状态;置换被存储在洗牌中。这个小窍门使算法O（n）和作为奖励使得它易于矢量化。

从某种意义上来说，这个解决方案是最优的，因为它显然不能比O（n）做得更好。