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?

Pozdrawiam

do góry

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

do góry

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 :)

do góry

On Wed, 11 May 2016 10:38:43 +0200, bartekltg <b...@g...com>
wrote:
> więc być mozę da się prościej. Na szybko nie widzę.

Na szybko: posortuj po x, posortuj po y; dla danego punktu znajdź mu
najbliższy (dzięki sortowaniu masz czterech kandydatów lub mniej);
usuń parę. Powtarzaj aż do skutku. Rób to kolejno od najbliższej
pary. Odległości par możesz obliczyć i posortować, a potem usuwać już
nieobecne. Całość celuje w O(N log N).

do góry

On Sunday, May 15, 2016 at 8:03:02 AM UTC+2, slawek wrote:
> Na szybko: posortuj po x, posortuj po y; dla danego punktu znajdź mu
> najbliższy (dzięki sortowaniu masz czterech kandydatów lub mniej);

To raczej nie zadziała, jak myślisz.

w.

do góry

On Sunday, May 15, 2016 at 8:33:24 AM UTC+2, Wojciech Muła wrote:
> On Sunday, May 15, 2016 at 8:03:02 AM UTC+2, slawek wrote:
> > Na szybko: posortuj po x, posortuj po y; dla danego punktu znajdź mu
> > najbliższy (dzięki sortowaniu masz czterech kandydatów lub mniej);
>
> To raczej nie zadziała, jak myślisz.
>
> w.

Propozycja Sławka mnie się skojarzyła z problemem stabilnych małżeństw.
Problem 'sparowania po najmniejszej odległości' wydaje się nawet
łatwiejszy, bo jeśli facet y najbardziej preferuję kobietę x, to także
kobieta x najbardziej preferuje faceta y. Jednak w tym wątku chodzi o
najmniejszą sumę, a nie o stabilność par - stabilność chyba nie
gwarantuje najmniejszej sumy?


Pozdrawiam

do góry

On 15.05.2016 14:07, M.M. wrote:
> On Sunday, May 15, 2016 at 8:33:24 AM UTC+2, Wojciech Muła wrote:
>> On Sunday, May 15, 2016 at 8:03:02 AM UTC+2, slawek wrote:
>>> Na szybko: posortuj po x, posortuj po y; dla danego punktu znajdź mu
>>> najbliższy (dzięki sortowaniu masz czterech kandydatów lub mniej);
>>
>> To raczej nie zadziała, jak myślisz.
>>
>> w.
>
> Propozycja Sławka mnie się skojarzyła z problemem stabilnych małżeństw.
> Problem 'sparowania po najmniejszej odległości' wydaje się nawet
> łatwiejszy, bo jeśli facet y najbardziej preferuję kobietę x, to także
> kobieta x najbardziej preferuje faceta y. Jednak w tym wątku chodzi o
> najmniejszą sumę, a nie o stabilność par - stabilność chyba nie
> gwarantuje najmniejszej sumy?

https://en.wikipedia.org/wiki/Stable_marriage_proble
m#Similar_problems

The assignment problem seeks to find a matching in a weighted bipartite
graph that has maximum weight. Maximum weighted matchings do not have to
be stable, but in some applications a maximum weighted matching is
better than a stable one.

A o assigment problem rozmawialiśmy parę dni temu;-)

pzdr
bartekltg

do góry

On 15.05.2016 08:02, slawek wrote:
> On Wed, 11 May 2016 10:38:43 +0200, bartekltg <b...@g...com> wrote:
>> więc być mozę da się prościej. Na szybko nie widzę.
>
> Na szybko: posortuj po x, posortuj po y; dla danego punktu znajdź mu
> najbliższy (dzięki sortowaniu masz czterech kandydatów lub mniej); usuń
> parę. Powtarzaj aż do skutku. Rób to kolejno od najbliższej pary.
> Odległości par możesz obliczyć i posortować, a potem usuwać już
> nieobecne. Całość celuje w O(N log N).

Kontrprzykład:

A1 <-2m-> B1 <-1m-> A2 <-2m-> B2

Optymalne rozwiązanie wiąże A1-B1 B2-A2 na kwotę 4m.

Rozwianie zachłanne daje A1-B2 B1-A2 na kwotę 6m.

pzdr
bartekltg

do góry

On 15.05.2016 08:02, slawek wrote:
> On Wed, 11 May 2016 10:38:43 +0200, bartekltg <b...@g...com> wrote:
>> więc być mozę da się prościej. Na szybko nie widzę.
>
> Na szybko: posortuj po x, posortuj po y; dla danego punktu znajdź mu
> najbliższy (dzięki sortowaniu masz czterech kandydatów lub mniej); usuń
> parę. Powtarzaj aż do skutku. Rób to kolejno od najbliższej pary.
> Odległości par możesz obliczyć i posortować, a potem usuwać już
> nieobecne. Całość celuje w O(N log N).


Był bardzo podobny, słabszy*) problem:
Też dwa zbiory A,B punktów na płaszczyźnie,
chcemy je sparować tak, aby linie łączące je nie przecinały się.

Kołacze mi się po głowie, że rozwiązaniem było znajdowanie
przecięcia i likwidowaniem go, poprzez zamianę sparowania.

Nie pamiętam jednak szczegółowy, a jest tam taki problem,
więc nie potrafię odtworzyć złożoności.
Problem w tym, że relaksacja może spowodować zwiększenie się
liczby przecięć (to nie przeszkadza w poprawności, rozwiązanie znajdzie**).


*) sparowanie o minimalnej sumie długości nie ma przecięć,
ale rozwiązanie bez przecięć nie musi być minimalne:
A B
| |
| |
| |
| |
B A

**) Zbiór możliwych wartości sumy jest skończony,
każda operacja prostowania kolizji zmniejsza tę odległość.
Jeśli nie mamy rozwiąznia=> jest kolizja=> mozemy poprawić.
Ale nie zrobimy więcej niż ileśtam kroków.

pzdr
bartekltg

do góry