Ho un problema con l'algoritmo qui. È diverso dal normale Fermat Point problem.per trovare un punto tra n punti nel piano per minimizzare la somma delle distanze
Dato un set di punti n nell'aereo, ho bisogno di trovare quale si può ridurre al minimo la somma delle distanze al resto dei punti n-1.
C'è qualche algoritmo che sai di eseguire meno di O (n^2)?
Grazie.
Una soluzione è assumere che la mediana sia vicina alla media e per un sottogruppo di punti vicino alla media calcoli esaurientemente la somma delle distanze. Puoi scegliere klog (n) punti più vicini alla media, dove k è una costante scelta arbitrariamente (complessità nlog (n)).
Un'altra possibile soluzione è la triangolazione di Delaunay. Questa triangolazione è possibile nel tempo O (nlogn). La triangolazione genera un grafico con un vertice per ogni punto e ogni lato per soddisfare la triangolazione delauney. Una volta ottenuta la triangolazione, è possibile iniziare in qualsiasi punto e confrontare la somma delle distanze di quel punto con i suoi vicini e continuare a muoversi in modo iterativo. È possibile interrompere quando il punto corrente ha la somma di distanza minima rispetto ai suoi vicini. Intuitivamente, questo si fermerà al punto ottimale globale.
Grazie per il pensiero. Cosa intendi esattamente "per un sottoinsieme di punti vicino alla media"? Come definisci "chiudi" qui. Anche nella "Triangolazione di Delaunay" pensavo, come "continuare a muoversi in modo iterativo"? Come dire il criterio di arresto? –
@littleEinstein Vedi la soluzione aggiornata. – ElKamina
Penso che l'ipotesi sottostante sia che si dispone di un set di dati di punti che si possono facilmente associare, poiché molti algoritmi che sarebbero "abbastanza buoni" nella pratica potrebbero non essere abbastanza rigorosi per la teoria e/o potrebbero non adattarsi bene per soluzioni arbitrariamente grandi.
Una soluzione molto semplice che è probabilmente "abbastanza buona" è ordinare le coordinate sull'ordinata Y, quindi eseguire un ordinamento stabile sull'ordinata X.
Prendere il rettangolo definito dai valori min (X, Y) e max (X, Y), complessità O (1) poiché i valori saranno in posizioni note nel set di dati ordinato.
Ora, lavorando dal centro del set di dati ordinato, trova i valori delle coordinate il più vicino possibile a {Xctr = Xmin + (Xmax - Xmin)/2, Yctr = Ymin + (Ymax - Ymin)/2} - complessità O (N) limitata dai criteri di minimizzazione, la distanza è il raggio familiare da {Xctr, Yctr}.
La complessità del caso peggiore sarebbe quella di confrontare il centroide con ogni altro punto, ma una volta che ti allontani dai punti centrali non migliorerai l'optimum globale e dovresti terminare la ricerca.
Vuoi il http://en.wikipedia.org/wiki/Geometric_median –
Hai bisogno dell'algoritmo per lavorare con solo la distanza euclidea o qualsiasi tipo di distanza? – Josay
@ScottHunter Penso che voglia il punto più vicino alla mediana geometrica (che non dovrebbe essere molto più difficile da trovare) ma non ne sono sicuro. – Josay