Stima approssimativa di distanza Matrici

Question

Ho un insieme di N oggetti, e mi piacerebbe per calcolare una matrice di distanza NxN. A volte il mio insieme di N oggetti è molto grande, e mi piacerebbe per calcolare un'approssimazione alla matrice NxN distanza da solo calcolando un sottoinsieme dei confronti a distanza.

Qualcuno può punto me nella direzione di qualcosa che calcola approssimazioni a una matrice completa a distanza? Ho alcune idee in mente, ma vorrei evitare di re-inventare la ruota.

Edit: Un esempio del tipo di algoritmo potrebbe sfruttare il fatto che se c'è una piccolissima distanza tra l'oggetto A e l'oggetto B, e c'è una piccolissima distanza tra l'oggetto B e oggetto C, non deve essere un po breve distanza tra gli oggetti a e C.

Answer 1

Onestamente, penso che dipende quanto vicino si desidera che l'approssimazione di essere e quanto è grande il vostro sottoinsieme è. Se si desidera solo un po 'sensazione generale di ciò che la matrice sarà simile, si può fare semplice interpolazione lineare su un sottoinsieme casuale (tra cui il massimale e minimale nodi) ottenendo (tm) risultati abbastanza precisi.

Credo che il vero trucco è capire l'euristica (lineare, quadratica, ecc interpolazione) e la dimensione sottoinsieme. Si potrebbe anche capire le matrici a distanza di diversi sottoinsiemi e quindi interpolare tali matrici con qualche metodo (lineare, lineare sferico, cubico).

A seconda del campione iniziale, è più o meno un processo euristico ed errori fino a quando si va "Oh, è abbastanza buono per quello che mi serve".

Answer 2

Sono i tuoi "oggetti" su una rete? Se gli oggetti sono in una rete, è possibile utilizzare questo o questo che produce il tutti coppie percorsi più brevi. In caso contrario, sei praticamente bloccato con calcolato tutte le n x n distanze, credo.

Answer 3

La soluzione si richiede è simile a ciò che comunemente vediamo in un grafico, è possibile utilizzare Tutti coppia più corta percorso per trovare la distanza, si può anche guardare al Johnson algoritmo

Answer 4

Ho avuto questa stessa domanda e ha finito per scrivere codice Python per esso:

https://github.com/jpeterbaker/lazyDistance

README.md spiega come la disuguaglianza triangolare può essere utilizzato per aggiornare estremi superiore ed inferiore per ogni distanza.

Basta eseguire il file Python come uno script per un esempio nello spazio a 2 dimensioni. Le linee tracciate sono le uniche distanze che sono stati effettivamente calcolati.

Nella mia versione, il risparmio di tempo non sono di avere un gran numero di oggetti. Come ho scritto, è un O (n ^ 4) algoritmo, quindi in realtà è peggio di un semplice calcolo di tutte le distanze, se il numero di oggetti è di grandi dimensioni. Ma il mio metodo farà risparmiare tempo quando si dispone di un modesto numero di oggetti e la funzione di distanza è molto costoso da calcolare. Si presuppone che è più veloce fare vari O (n ^ 2) operazioni piuttosto che una singola misura della distanza.

Se n è grande, si potrebbe cercare metodi meno costosi per decidere quale distanza per calcolare il prossimo (che non coinvolgono l'aritmetica con n ^ 2 ingressi of Bounds distanza matrici). Inoltre, non potrebbe essere necessario aggiornare tutti i 2 * n ^ 2 limiti ogni volta che questo codice fa.