Re: problem z algorytmiki

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

Show all headers | View raw

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

Back to pl.comp.programming | Previous | Next — Previous 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