曼哈頓距離

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）做得更好。