On Wednesday, May 11, 2016 at 10:38:44 AM UTC+2, bartekltg wrote:
> 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

Dzięki :)