Come trovare il vettore più vicino a un determinato vettore?

Question

Come trovare il vettore più vicino a un determinato vettore?

#1 da (8 voti)

4

Diciamo che ho diversi punti / vettori (in 2D per mantenerlo semplice, ma potrebbe essere di qualsiasi dimensione)

   [x1, y1]
   [x2, y2]
   [x3, y3]
   ....
   [xn, yn]

Se seleziono un punto [x', y'] , come trovo il punto più vicino ad esso?

Per un esempio più concreto / pratico, immagina che queste siano le coordinate delle case. Se ho migliaia di case nel database, mi piacerebbe trovare la casa più vicina a casa mia. O più in generale, mi piacerebbe trovare le case K più vicine a casa mia.

Un modo brute-force per farlo è quello di scorrere ogni punto e trovare la sua distanza dal punto / casa e scegliere solo il più piccolo. Ma con migliaia o addirittura milioni di punti dati non è affatto efficiente.

C'è un algoritmo più veloce? O sono bloccato cercando di controllare ogni punto uno alla volta?

algorithms

posta user2490003 26.02.2016 - 11:58

fonte

1 risposta

Leggi altre domande sui tag algorithms

Come funziona il qsort di K & R? Come sperimentare un graduale miglioramento delle conoscenze mentre un principiante esegue la programmazione di manutenzione .NET? [chiuso]

score 8 · Answer 1

Se hai più query, puoi utilizzare una infrastruttura spaziale per accelerarle. Questo in genere richiede la pre-elaborazione dei tuoi punti target, e in ogni caso ti costerà un po 'di tempo e spazio.

Esistono due classi comuni di strutture di accelerazione: una utilizza le partizioni spaziali e l'altra utilizza regioni sovrapposte. L'albero kD è un esempio del primo, mentre R-tree è un esempio del secondo.

Naturalmente, se si dispone di una sola query, non si può fare meglio in generale che controllare ogni punto una volta. Ma se hai bisogno che la query stessa sia veloce, allora la pre-elaborazione per costruire una struttura di accelerazione può portarti lì.