On 12.02.2016 14:49, slawek wrote:
> On Wed, 10 Feb 2016 01:46:57 -0800 (PST), "M.M." <m...@g...com>
> wrote:
>> Ma ktoś ochotę zaimplementować ten algorytm?
>
> Miałbym, ale mam teraz dużo innych pilnych spraw.
>
> Wydaje mi się że można zrobić algorytm O(N log N) i to dość prosty:
>
> 1. Rzutujemy na przestrzenie jednowymiarowe.
> 2. Sortujemy.
> 3. Rozwiązujemy te problemy 1D.
> 4. Odrzucamy z wielowymiarowego problemu punkty niezgodne z
> rozwiązaniami 1D.
> 5. Wykorzystujemy inteligentnie pomysł z konstrukcją okręgu przez trzy
> punkty. Sprawdzamy tylko te które są skrajne w 1D.
>
> Najdłużej będzie trwało sortowanie. Kwestia otwarta: czy istnieje jakiś
> patologiczny przypadek, że się nie uda.

A B

C

Odległość AB = 1
odległosc BC = 1.4...1.42

Rzut na odrzucił A. Rozwiązaniem jest {B,C}
rzut na y odrzucił C, Rozwiązaniem jest {A,B}

Nie widzę, jak ten alborytm teraz zszywa rozwiązanie.

> Ale ogólnie powinno działać.

To szukasz algorytmu, czy heurystyki?

pzdr
bartekltg

do góry

Użytkownik "M.M." <m...@g...com> napisał w wiadomości grup
dyskusyjnych:96d06122-0b5d-4ab1-927f-f740a2ecf74e@go
oglegroups.com...
> Gdy będziesz rzutował na oś X, to grupa z lewej będzie miała mniejszy
> promień, a bez rzutowania większy.

Może to jakoś prościej wyjaśnia ideę algorytmu: jeżeli rozwiązanie jest
optymalne w n wymiarowej przestrzeniu,
to jest też optymalne w 1 wymiarowym rzucie. Oczywiście opieranie się na
jednym rzucie nie wystarczy, ale z kilku da
się wyciągnąć jakieś wnioski. Istotne, bardzo, jest że w 1 wymiarowym rzucie
da się punkty posortować. Czyli już
samo to zamiast n**2 / 2 wyborów dwóch punktów daje zaledwie n/2 wyborów, bo
wybieramy kolejno: pierwszy
punkt i n/2 ty; drugi i n/2+1 itd. Oczywiście najpierw je sortujemy.

do góry

Użytkownik "bartekltg" <b...@g...com> napisał w wiadomości grup
dyskusyjnych:n9l2s2$s8s$...@n...news.atman.pl...
> To szukasz algorytmu, czy heurystyki?

Jak zwał tak zwał.

Po prostu /być/ /może/ da się (?) skonstruować patologiczny rozkład, dla
którego algorytm z rzutowaniem będzie O(N**4) czy jakiś taki.

Na przykład dla bardzo dużej ilości punktów rozmieszczonych równomiernie na
okręgu nie ma
koła o wyraźnie mniejszym promieniu (niż promień tego okręgu) które
zawierałoby co najmniej połowę zadanych punktów.

Ale przewiduję, że dla niezłośliwych rozkładów będzie O(N log N), czyli tyle
co sortowanie.

Jeszcze raz - wyobraź sobie że już masz rozwiązanie - i że rzutujesz i
punkty, i to rozwiązanie, na przestrzenie jednowymiarowe.

do góry

Użytkownik "bartekltg" <b...@g...com> napisał w wiadomości grup
dyskusyjnych:n9l2s2$s8s$...@n...news.atman.pl...
> A B
>
> C
>
> Odległość AB = 1
> odległosc BC = 1.4...1.42
>
> Rzut na odrzucił A. Rozwiązaniem jest {B,C}
> rzut na y odrzucił C, Rozwiązaniem jest {A,B}
>
> Nie widzę, jak ten alborytm teraz zszywa rozwiązanie.

Inteligentnie ;)

Są tylko trzy punkty, więc sprawdzane są małe okręgi o średnicach AB, BC i
AC.

Ale wic w tym że te rzuty, o jakich piszesz, wytypowały punkty A, B, C jako
ważne. Gdyby było więcej punktów,
to większość z nich byłaby odrzucona. I to na etapie kosztującym O(N) po
sortowaniu O(N log N).
Czyli wychodzi O(N log N) na każdą selekcję, selekcje są 2 dla 2D. Dalej
jest O(N log N).

do góry

On Friday, February 12, 2016 at 8:03:05 PM UTC+1, slawek wrote:
> Użytkownik "bartekltg" <b...@g...com> napisał w wiadomości grup
> dyskusyjnych:n9l2s2$s8s$...@n...news.atman.pl...
> > To szukasz algorytmu, czy heurystyki?
>
> Jak zwał tak zwał.

Apropo heurystyk. Co by bylo, gdyby N razy wyrzucić M losowo wybranych
punktów i odpalić dokładny algorytm po każdym wyrzuceniu? Algorytm
dla 50 punktów zadziała bardzo szybko. Ostatecznie można wyrzucić K
punktów które najrzadziej były w rozwiązaniu i znowu odpalić algorytm
dokładny.

Pozdrawiam

do góry

On 12.02.2016 20:12, slawek wrote:
>
> Użytkownik "bartekltg" <b...@g...com> napisał w wiadomości grup
> dyskusyjnych:n9l2s2$s8s$...@n...news.atman.pl...
>> A B
>>
>> C
>>
>> Odległość AB = 1
>> odległosc BC = 1.4...1.42
>>
>> Rzut na odrzucił A. Rozwiązaniem jest {B,C}
>> rzut na y odrzucił C, Rozwiązaniem jest {A,B}
>>
>> Nie widzę, jak ten alborytm teraz zszywa rozwiązanie.
>
> Inteligentnie ;)

Jeszcze raz: nie napisałeś jak ten algorytm ma składać
wynik z wyników pośrednich, więc ciężko go ocenić.

> Są tylko trzy punkty, więc sprawdzane są małe okręgi o średnicach AB, BC
> i AC.



>
> Ale wic w tym że te rzuty, o jakich piszesz, wytypowały punkty A, B, C
> jako ważne. Gdyby było więcej punktów,
> to większość z nich byłaby odrzucona. I to na etapie kosztującym O(N) po
> sortowaniu O(N log N).
> Czyli wychodzi O(N log N) na każdą selekcję, selekcje są 2 dla 2D. Dalej
> jest O(N log N).

No to po osi x został zbiór X.
Po osi y, zbiór Y.
Oba mają N/2 punktów, niepuste przecięcie, ale i nie są takie same.

Jak konstruujesz przybliżoen rozwiązanie pełnego zagadnienia.

pzdr
bartekltg

do góry

On 12.02.2016 21:03, M.M. wrote:
> On Friday, February 12, 2016 at 8:03:05 PM UTC+1, slawek wrote:
>> Użytkownik "bartekltg" <b...@g...com> napisał w wiadomości grup
>> dyskusyjnych:n9l2s2$s8s$...@n...news.atman.pl...
>>> To szukasz algorytmu, czy heurystyki?
>>
>> Jak zwał tak zwał.
>
> Apropo heurystyk. Co by bylo, gdyby N razy wyrzucić M losowo wybranych
> punktów i odpalić dokładny algorytm po każdym wyrzuceniu? Algorytm
> dla 50 punktów zadziała bardzo szybko. Ostatecznie można wyrzucić K
> punktów które najrzadziej były w rozwiązaniu i znowu odpalić algorytm
> dokładny.

Dla 50 (czy 2000) punktów podany ścisły algorytm O(n^3 +)
jest całkowicie wysatrczający.
Pytanie, co zrobić jak jest ich 500 000 albo 10^9;-)

pzdr
bartekltg

do góry

On Saturday, February 13, 2016 at 12:04:32 AM UTC+1, bartekltg wrote:
> On 12.02.2016 21:03, M.M. wrote:
> > On Friday, February 12, 2016 at 8:03:05 PM UTC+1, slawek wrote:
> >> Użytkownik "bartekltg" <b...@g...com> napisał w wiadomości grup
> >> dyskusyjnych:n9l2s2$s8s$...@n...news.atman.pl...
> >>> To szukasz algorytmu, czy heurystyki?
> >>
> >> Jak zwał tak zwał.
> >
> > Apropo heurystyk. Co by bylo, gdyby N razy wyrzucić M losowo wybranych
> > punktów i odpalić dokładny algorytm po każdym wyrzuceniu? Algorytm
> > dla 50 punktów zadziała bardzo szybko. Ostatecznie można wyrzucić K
> > punktów które najrzadziej były w rozwiązaniu i znowu odpalić algorytm
> > dokładny.
>
> Dla 50 (czy 2000) punktów podany ścisły algorytm O(n^3 +)
> jest całkowicie wysatrczający.
> Pytanie, co zrobić jak jest ich 500 000 albo 10^9;-)
>

Jeśli jest 500000, to wyrzucamy 499000 losowo
wybranych punktów. Liczymy dokładnie dla pozostałego
tysiąca. Potem odrzucamy inne losowo wybranie 499000 i
znowu. Po 100 takich rozwiązaniach otrzymamy 100
środków w potencjalnie największej gęstości. Potem
jakoś spożytkować tę informację.... nie wiem jeszcze
jak :)


Pozdrawiam

do góry

On Saturday, February 13, 2016 at 12:04:32 AM UTC+1, bartekltg wrote:
> On 12.02.2016 21:03, M.M. wrote:
> > On Friday, February 12, 2016 at 8:03:05 PM UTC+1, slawek wrote:
> >> Użytkownik "bartekltg" <b...@g...com> napisał w wiadomości grup
> >> dyskusyjnych:n9l2s2$s8s$...@n...news.atman.pl...
> >>> To szukasz algorytmu, czy heurystyki?
> >>
> >> Jak zwał tak zwał.
> >
> > Apropo heurystyk. Co by bylo, gdyby N razy wyrzucić M losowo wybranych
> > punktów i odpalić dokładny algorytm po każdym wyrzuceniu? Algorytm
> > dla 50 punktów zadziała bardzo szybko. Ostatecznie można wyrzucić K
> > punktów które najrzadziej były w rozwiązaniu i znowu odpalić algorytm
> > dokładny.
>
> Dla 50 (czy 2000) punktów podany ścisły algorytm O(n^3 +)
> jest całkowicie wysatrczający.
> Pytanie, co zrobić jak jest ich 500 000 albo 10^9;-)
>
> pzdr
> bartekltg

Inny pomysł.

Szukamy min i max dla points[i].x i points[i].y .

Mamy prostokąt (min.x,min.y) (max.x,max.y). Wewnątrz prostokąta
robimy siatkę MxM prostokątów. Każdy prostokąt traktujemy jako
punkt, tyle że ważony, jego waga jest równa ilości punktów wewnątrz, a
środek to średnia arytmetyczna punktów (zawartych w nim, rzecz jasna).

Gdy M damy 30, to mamy tylko 900 punktów. Liczymy algorytmem dokładnym.
Potem na wszystkich punktach szorujemy okręgiem w okolicach pierwszego
rozwiązania.

Ciekawe jakby to działało w praktyce na różnych danych.

Pozdrawiam

do góry