Mappatura di un set di punti 3D su un altro set con una somma minima di distanze

Question

Dati sono due insiemi di punti tridimensionali, una sorgente e una destinazione. Il numero di punti su ogni set è arbitrario (può essere zero). Il compito è assegnare uno o nessun punto di origine a ogni punto di destinazione, in modo che la somma di tutte le distanze sia minima. Se sono presenti più punti sorgente che punti di destinazione, i punti aggiuntivi devono essere ignorati.

Esiste una soluzione a forza bruta a questo problema, ma poiché il numero di punti può essere elevato, non è fattibile. Ho sentito che questo problema è facile in 2D con dimensioni uguali, ma purtroppo queste condizioni preliminari non sono riportate qui.

Sono interessato sia alle approssimazioni che alle soluzioni esatte.

Modifica: Haha, sì, suppongo che suoni come compiti a casa. In realtà non lo è. Sto scrivendo un programma che riceve le posizioni di un gran numero di auto e sto cercando di mapparle sulle rispettive celle di parcheggio. :)

Answer 1

Dall'alto della mia testa, ordinamento spaziale seguito da ricottura simulata.

Grid the space & amp; ordina gli insiemi in celle spaziali.

Risolvi il problema O (NM) all'interno di ogni cella, quindi all'interno dei quartieri delle celle e così via, per ottenere una corrispondenza di prova.

Infine, esegui molti cicli di ricottura simulata, in cui modifichi casualmente le partite, in modo da esplorare lo spazio vicino.

Questo è euristico, ti dà una buona risposta anche se non necessariamente la migliore, e dovrebbe essere abbastanza efficiente a causa dell'ordinamento della griglia iniziale.

Answer 2

Un modo per affrontare questo problema è quello di trattare come il classico problema di assegnazione: http: // en.wikipedia.org/wiki/Assignment_problem

I punti vengono trattati come i vertici del grafico e i pesi dei bordi sono la distanza tra i punti. Poiché gli algoritmi più veloci presuppongono che tu stia cercando la corrispondenza massima (e non minima come nel tuo caso) e che i pesi non siano negativi, puoi ridefinire i pesi in modo da es .:

weight(A, B) = bigNumber- distance(A,B)

dove bigNumber è più grande della distanza più lunga.

Ovviamente si finisce con un grafico bipartito. Quindi si utilizza uno degli algoritmi standard per la corrispondenza bipartita massima ponderata (molte risorse sul Web, ad es. http://valis.cs.uiuc.edu/~sariel/teach/courses/473/notes/27_matchings_notes.pdf o Wikipedia per panoramica: http://en.wikipedia.org/wiki/Perfect_matching#Maximum_bipartite_matchings ) In questo modo finirai- con un algoritmo O (NM max (N, M)), dove N e M sono le dimensioni delle tue serie di punti.

Answer 3

Anche se in realtà non ho una risposta alla tua domanda, posso suggerire di esaminare i seguenti argomenti. (Ne so ben poco, ma l'ho incontrato in precedenza su Stack Overflow.)

• Ricerca vicini più vicini
• k d-tree

Spero che questo aiuti un po '.