On 11.05.2016 10:01, M.M. wrote:
> Mamy dwa równoliczne zbiory punktów 2D. Każdemu punktowi z
> jednego zbioru trzeba przyporządkować jeden punkt z drugiego
> zbioru. Innymi słowy, trzeba punkty połączyć w pary, w każdej
> parze jeden punkt musi być z pierwszego zbioru, drugi z drugiego.
> Suma odległości pomiędzy punktami z pary musi być najmniejsza.
>
> Można to szybko policzyć, czy nie?

To jest maksymalny przepływ o minimalnym koscie w grafie
dwudzielnym ("Assignment problem"). Algorytm węgeirski
i masz rozwiązanie w O(n^3),
Czy to "szybko", trudno powiedzieć ;-)


Wykorzystując to, że sa one na płaszczyźnie są różne heurystyki,
googlaj pod Euclidean Bipartite Matching
np to:
http://homepage.cs.uiowa.edu/~kvaradar/paps/p079-aga
rwal.pdf

Problem ten można rozwiązywać algorytmem simplex... niby wykłądniczy,
ale dla rzeczywistych danych możę zadziaąłć w miarę szybko;-)


Uwaga. Rozwiązania są dla problemu ciut bardziej skomplikowanego,
więc być mozę da się prościej. Na szybko nie widzę.

pzdr
bartekltg