Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > pl.comp.programming > #28550

Re: problem z algorytmiki

From bartekltg <bartekltg@gmail.com>
Newsgroups pl.comp.programming
Subject Re: problem z algorytmiki
Date 2016-05-11 10:38 +0200
Organization ATMAN - ATM S.A.
Message-ID <ngur2j$kqd$1@node2.news.atman.pl> (permalink)
References <85100148-6951-483f-965c-8ba566f34162@googlegroups.com>

Show all headers | View raw

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-agarwal.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

Back to pl.comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

problem z algorytmiki "M.M." <mmarszik@gmail.com> - 2016-05-11 01:01 -0700
  Re: problem z algorytmiki bartekltg <bartekltg@gmail.com> - 2016-05-11 10:38 +0200
    Re: problem z algorytmiki "M.M." <mmarszik@gmail.com> - 2016-05-11 01:46 -0700
    Re: problem z algorytmiki slawek <fake@fakeemail.com> - 2016-05-15 08:02 +0200
      Re: problem z algorytmiki Wojciech Muła <wojtek.mula@gmail.com> - 2016-05-14 23:33 -0700
        Re: problem z algorytmiki "M.M." <mmarszik@gmail.com> - 2016-05-15 05:07 -0700
          Re: problem z algorytmiki bartekltg <bartekltg@gmail.com> - 2016-05-15 19:35 +0200
      Re: problem z algorytmiki bartekltg <bartekltg@gmail.com> - 2016-05-15 19:44 +0200
      Re: problem z algorytmiki bartekltg <bartekltg@gmail.com> - 2016-05-15 20:24 +0200

csiph-web