Punti di ordinamento in modo da massimizzare la minima distanza euclidea tra punti consecutivi

Question

Dato un insieme di punti in uno spazio cartesiano 3D, sto cercando un algoritmo che classificherà questi punti, in modo tale che la distanza euclidea i punti consecutivi sarebbero massimizzati.

Sarebbe inoltre vantaggioso se l'algoritmo tende a massimizzare la distanza di euclidea tra i punti consecutivi.

Edit:

ho Crosspost su https://cstheory.stackexchange.com/ e ottenuto una buona risposta. Vedi https://cstheory.stackexchange.com/questions/8609/sorting-points-such-that-the-minimal-euclidean-distance-between-consecutive-poin.

Answer 1

Puoi modellare il tuo problema in base al grafico, tracciare una linea tra i tuoi punti, ora hai un grafico completo, ora il tuo problema è trovare il percorso più lungo in questo grafico che è NP-Hard, vedi wiki per longest path.

Infatti ho risposto a una seconda parte del problema, massimizzare la media, che significa massimizzare il percorso che va da ogni nodo del grafico, se li pesi come 1/distanza sarà un problema di commesso viaggiatore (minimizzare la lunghezza del percorso) ed è NP-Hard. e per questo caso potrebbe essere utile vedere Metric TSP approximation.

Answer 2

Ecco un limite inferiore per il costo della soluzione, che potrebbe servire come un blocco di costruzione per branch and bound o un più inaffidabile algoritmo di ricerca incompleta:

Ordina le distanze tra i punti e li considerano a non -aumento crescente Utilizzare http://en.wikipedia.org/wiki/Disjoint-set_data_structure per tenere traccia di insiemi di punti, unendo due set quando collegati da un collegamento tra due punti. La lunghezza della distanza più breve che incontri fino al punto in cui unisci tutti i punti in un set è un limite superiore alla distanza minima in una soluzione perfetta, perché una soluzione perfetta unisce anche tutti i punti in uno. Comunque il tuo limite superiore può essere più lungo della distanza minima per una soluzione perfetta, perché i collegamenti che stai unendo probabilmente formeranno un albero, non un percorso.