manhattan Entfernungen

Question

Was die optimale Art und Weise ist manhattan distances der Berechnung

Meine aktuelle Lösung ist:

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

Wie wäre es

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

dies Ihre Lösung durch die Vermeidung der wiederholten Anrufe verbessert, wo (die zu O (n^2) zählen). Stattdessen nutzt es die einfache Struktur von target_state und berechnet für jeden Index den Index in target_state, der denselben Wert enthält. Die Permutation wird in Shuffle gespeichert. Dieser kleine Trick macht den Algorithmus O (n) und erleichtert als Bonus die Vektorisierung.

Diese Lösung ist in dem Sinne optimal, dass man offensichtlich nicht besser ist als O (n).