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

Groups > pl.comp.programming > #28549 > unrolled thread

problem z algorytmiki

Back to article view | Back to pl.comp.programming

Contents

  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

#28549 — problem z algorytmiki

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

[toc] | [next] | [standalone]

#28550

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

[toc] | [prev] | [next] | [standalone]

#28551

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

Dzięki :)

[toc] | [prev] | [next] | [standalone]

#28577

On Wed, 11 May 2016 10:38:43 +0200, bartekltg <bartekltg@gmail.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).

[toc] | [prev] | [next] | [standalone]

#28578

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.

[toc] | [prev] | [next] | [standalone]

#28580

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

[toc] | [prev] | [next] | [standalone]

#28583

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_problem#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

[toc] | [prev] | [next] | [standalone]

#28584

On 15.05.2016 08:02, slawek wrote:
> On Wed, 11 May 2016 10:38:43 +0200, bartekltg <bartekltg@gmail.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

[toc] | [prev] | [next] | [standalone]

#28585

On 15.05.2016 08:02, slawek wrote:
> On Wed, 11 May 2016 10:38:43 +0200, bartekltg <bartekltg@gmail.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

[toc] | [prev] | [standalone]

Back to top | Article view | pl.comp.programming

csiph-web