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

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

Problemik algorytmiczny

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

Contents

  Problemik algorytmiczny slawek <fake@fakeemail.com> - 2016-02-09 10:15 +0100
    Re: Problemik algorytmiczny "M.M." <mmarszik@gmail.com> - 2016-02-09 02:35 -0800
      Re: Problemik algorytmiczny slawek <fake@fakeemail.com> - 2016-02-09 12:00 +0100
        Re: Problemik algorytmiczny "M.M." <mmarszik@gmail.com> - 2016-02-09 03:44 -0800
          Re: Problemik algorytmiczny Adam M <amorawski@magna-power.com> - 2016-02-09 05:42 -0800
            Re: Problemik algorytmiczny "M.M." <mmarszik@gmail.com> - 2016-02-09 05:59 -0800
              Re: Problemik algorytmiczny bartekltg <bartekltg@gmail.com> - 2016-02-09 18:06 +0100
                Re: Problemik algorytmiczny "M.M." <mmarszik@gmail.com> - 2016-02-10 01:46 -0800
                  Re: Problemik algorytmiczny slawek <fake@fakeemail.com> - 2016-02-12 14:49 +0100
                    Re: Problemik algorytmiczny "M.M." <mmarszik@gmail.com> - 2016-02-12 07:31 -0800
                      Re: Problemik algorytmiczny "slawek" <slawek@host.pl> - 2016-02-12 19:47 +0100
                    Re: Problemik algorytmiczny bartekltg <bartekltg@gmail.com> - 2016-02-12 17:56 +0100
                      Re: Problemik algorytmiczny "slawek" <slawek@host.pl> - 2016-02-12 20:05 +0100
                        Re: Problemik algorytmiczny "M.M." <mmarszik@gmail.com> - 2016-02-12 12:03 -0800
                          Re: Problemik algorytmiczny bartekltg <bartekltg@gmail.com> - 2016-02-13 00:04 +0100
                            Re: Problemik algorytmiczny "M.M." <mmarszik@gmail.com> - 2016-02-12 15:40 -0800
                            Re: Problemik algorytmiczny "M.M." <mmarszik@gmail.com> - 2016-02-13 03:07 -0800
                      Re: Problemik algorytmiczny "slawek" <slawek@host.pl> - 2016-02-12 20:12 +0100
                        Re: Problemik algorytmiczny bartekltg <bartekltg@gmail.com> - 2016-02-12 23:12 +0100

#28290 — Problemik algorytmiczny

Jest n punktów przestrzeni Banacha... Albo jak ktoś woli to zwykłych 
punktów zwykłej płaszczyzny. Punkty są rozmieszczone losowo, czyli 
jakoś gdzieś. Chcemy umieścić punkt n+1 w takim miejscu (czyli 
znaleźć współrzędne x, y), aby uzyskać jak najmniejsze d. Owo d jest 
zdefiniowane jako najmniejszy promień koła w którym mieści się n/2 z 
zadanych punktów.

Innymi słowy: szukamy miejsca możliwie bliskiego  połowie lokalizacji 
już znanych. Np. chcemy umieścić hurtownię tak, aby mieć 50% 
odbiorców blisko, pozostałych 50% nie będziemy i tak zaopatrywać.

Oczywiście można eliminować 50% punktów najbardziej odległych od 
"środka" (w sensie mediany czy średniej) i mamy wtedy 50% do których 
staramy się dopasować. Jednak gdy będą dwa odległe równoliczne 
skupiska to zawiedzie.

Problem nie jest ważny, nie ma (chyba) praktycznego znaczenia. Ale 
jest ciekawy sam w sobie.

[toc] | [next] | [standalone]

#28291

On Tuesday, February 9, 2016 at 10:15:14 AM UTC+1, slawek wrote:
> Jest n punktów przestrzeni Banacha... Albo jak ktoś woli to zwykłych 
> punktów zwykłej płaszczyzny. Punkty są rozmieszczone losowo, czyli 
> jakoś gdzieś. Chcemy umieścić punkt n+1 w takim miejscu (czyli 
> znaleźć współrzędne x, y), aby uzyskać jak najmniejsze d. Owo d jest 
> zdefiniowane jako najmniejszy promień koła w którym mieści się n/2 z 
> zadanych punktów.
> 
> Innymi słowy: szukamy miejsca możliwie bliskiego  połowie lokalizacji 
> już znanych. Np. chcemy umieścić hurtownię tak, aby mieć 50% 
> odbiorców blisko, pozostałych 50% nie będziemy i tak zaopatrywać.
> 
> Oczywiście można eliminować 50% punktów najbardziej odległych od 
> "środka" (w sensie mediany czy średniej) i mamy wtedy 50% do których 
> staramy się dopasować. Jednak gdy będą dwa odległe równoliczne 
> skupiska to zawiedzie.
> 

Przez tę chwilę w której czytałem Twojego posta, nie przyszło mi do
głowy nic poza jakimś bruteforce. 

1) Liczymy taki promień dla środka w każdym z danych punktów. Potem wybieramy
   kilka najlepszych punktów i losowo szukamy w pobliżu tych wybranych.

2) Metodą MC rzucamy na płaszczyznę N losowych okręgów. W końcu uzyskamy 
   rozkład gęstości. Statystycznie rzucamy częściej, tam gdzie gęstość 
   jest największa. 


> Problem nie jest ważny, nie ma (chyba) praktycznego znaczenia. Ale 
> jest ciekawy sam w sobie.
No nie wiem... po lekkich modyfikacjach by się znalazły zastosowania.


Pozdrawiam

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

#28292

On Tue, 9 Feb 2016 02:35:31 -0800 (PST), "M.M." <mmarszik@gmail.com> 
wrote:
> No nie wiem... po lekkich modyfikacjach by się znalazły 
zastosowania.

Mnie zaciekawiło w tym to, że mogę (widząc takie punkty narysowane na 
kartce papieru) łatwo wskazać gdzie to mniej więcej jest. Więc jak to 
robi mózg? I czy mózg naprawdę robi to dobrze, czy tylko mu się 
wydaje że robi to dobrze? Czy to jest problem łatwy dla AI lub dla I 
bez A...  ale trudny do zalgorytmizowania? Czy też algorytm/teoria 
już są i tylko ja o tym nie wiem?

Co do możliwych danych: dwa niezbyt odległe od siebie skupiska i 
trzecie daleko od tamtych dwóch. Różne warianty co do liczby punktów 
w każdym z nich.

A i jeszcze coś: gdzie będą punkty n+2, n+3,...  Będzie jakiś punkt 
stały, tj co z przejściem do nieskończoności?

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

#28293

On Tuesday, February 9, 2016 at 12:00:58 PM UTC+1, slawek wrote:
> On Tue, 9 Feb 2016 02:35:31 -0800 (PST), "M.M." <mmarszik@gmail.com> 
> wrote:
> > No nie wiem... po lekkich modyfikacjach by się znalazły 
> zastosowania.
> 
> Mnie zaciekawiło w tym to, że mogę (widząc takie punkty narysowane na 
> kartce papieru) łatwo wskazać gdzie to mniej więcej jest. 
Jakkolwiek działa mózg, to na pewno bardzo szybko przetwarza
obrazy. Mózg po ułamku sekundy wie gdzie jest gęsto i gdzie 
jest przybliżony środek gęstości.

> Więc jak to robi mózg? 
Nie wiem jak to robi mózg, może liczy równolegle odległość pomiędzy
najbliższą parą odcinków?


> I czy mózg naprawdę robi to dobrze, czy tylko mu się 
> wydaje że robi to dobrze? 
By trzeba poszukać jakiś badań. Jak to robi 100 przypadkowych osób i 
jak to robią najlepsze znane algorytmy.


> Czy to jest problem łatwy dla AI lub dla I 
> bez A...  ale trudny do zalgorytmizowania? Czy też algorytm/teoria 
> już są i tylko ja o tym nie wiem?
Nigdy nie czytałem o algorytmie który daje optymalne rozwiązanie. Po
chwili zastanowienia, to by trzeba jakoś sprytnie przesuwać ten okrąg 
po powierzchni 2D i dostosowywać jego rozmiar. Może da się to zrobić w
czasie N?

A jakby zastosować 'metodę zegarkową'? Wychodzę z założenia, że optymalne
rozwiązanie powinno zawierać punkty na swoim obwodzie.
1) Dla każdego punktu
 a) rysujemy okrąg tak aby ten punkt leżał na jego obwodzie;
 b) zwiększamy okrąg rozciągając go w kierunku godziny 12tej, aż
    obejmie zadaną ilość punktów;
 c) potem obracamy nim w kierunku godziny 1szej, aż zmieni się ilość
    punktów jeśli zmalała ilość punktów, to okrąg zwiększamy, jeśli
    wzrosła, to zmniejszamy

Powyższy algorytm raczej nie da optymalnego rozwiązania, ale powinien dać
całkiem dobre. Będzie działał w czasie N^2.

Inne założenie: optymalny okrąg musi mieć na swoim obwodzie 3 punkty. Czyli
rysujemy minimalny okrąg dla każdej pary punktów. Jeśli zawiera za dużo
punktów, to przerywamy. Jeśli zawiera za mało, to zwiększamy tak, aby
po kolei dotykał trzeciego punktu. W ten sposób przeiterujemy wszystkie
potencjalnie optymalne okręgi. Wybieramy najmniejszy. Złożoność N^3 - nie
taka zła, a intuicja podpowiada mi, że to będzie optymalny algorytm.


> Co do możliwych danych: dwa niezbyt odległe od siebie skupiska i 
> trzecie daleko od tamtych dwóch. Różne warianty co do liczby punktów 
> w każdym z nich.
Myślę że ten algorytm N^3 poradzi sobie.


> A i jeszcze coś: gdzie będą punkty n+2, n+3,...  Będzie jakiś punkt 
> stały, tj co z przejściem do nieskończoności?
Czyli punkty dane wzorem matematycznym, a nie tabelką? Hmmmm... jak
się ułożą w ciąg rosnący szybciej niż liniowo (po x i y), to będzie 
stały punkt. Poza tym przypadkiem może być trudne w analizie.


Pozdrawiam

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

#28294

Problem jest ciekawy i metoda rozwiazania zelzy do ilosci punktow:
- przy malej ilosci punkow metoda brut-froce lub kazda z wyzej wymienionych metod poradzi sobie calkiem niezle
- przy duzej ilosci punktow lepsze jest podejscie graficzno-matematyczne.
tworzymy graficzna reprezentacje rozlozenia punktow i lagorytmy analizy obrazu pozwalaja wybrac nam wrunki graniczne do przeszukiwania (miejsca gdzie jest najwieksze zageszczenie punktow - najbardziej ciemne miejsca). Metoda ta jednak ma jedna podstawowa wade - gdy rozmieszczenie punktow jest losowo rownomierne (bialy szum) graficzna metoda wyznaczenia warunkow brzegowych wyszukiwania padnie na twarz - ale w tym przypadku chyba kazda metoda padnie na twarz i losowe wybranie punktu bedzie najlepsze/najtansze obliczeniowo (bo i tak punkty sa rozlozone losowo ale rownomiernie ;-) )

On Tuesday, February 9, 2016 at 6:44:25 AM UTC-5, M.M. wrote:
> On Tuesday, February 9, 2016 at 12:00:58 PM UTC+1, slawek wrote:
> > On Tue, 9 Feb 2016 02:35:31 -0800 (PST), "M.M." 
> > > No nie wiem... po lekkich modyfikacjach by się znalazły 
> > zastosowania.
> > 
> > Mnie zaciekawiło w tym to, że mogę (widząc takie punkty narysowane na 
> > kartce papieru) łatwo wskazać gdzie to mniej więcej jest. 
> Jakkolwiek działa mózg, to na pewno bardzo szybko przetwarza
> obrazy. Mózg po ułamku sekundy wie gdzie jest gęsto i gdzie 
> jest przybliżony środek gęstości.
> 
> > Więc jak to robi mózg? 
> Nie wiem jak to robi mózg, może liczy równolegle odległość pomiędzy
> najbliższą parą odcinków?
> 
> 
> > I czy mózg naprawdę robi to dobrze, czy tylko mu się 
> > wydaje że robi to dobrze? 
> By trzeba poszukać jakiś badań. Jak to robi 100 przypadkowych osób i 
> jak to robią najlepsze znane algorytmy.
> 
> 
> > Czy to jest problem łatwy dla AI lub dla I 
> > bez A...  ale trudny do zalgorytmizowania? Czy też algorytm/teoria 
> > już są i tylko ja o tym nie wiem?
> Nigdy nie czytałem o algorytmie który daje optymalne rozwiązanie. Po
> chwili zastanowienia, to by trzeba jakoś sprytnie przesuwać ten okrąg 
> po powierzchni 2D i dostosowywać jego rozmiar. Może da się to zrobić w
> czasie N?
> 
> A jakby zastosować 'metodę zegarkową'? Wychodzę z założenia, że optymalne
> rozwiązanie powinno zawierać punkty na swoim obwodzie.
> 1) Dla każdego punktu
>  a) rysujemy okrąg tak aby ten punkt leżał na jego obwodzie;
>  b) zwiększamy okrąg rozciągając go w kierunku godziny 12tej, aż
>     obejmie zadaną ilość punktów;
>  c) potem obracamy nim w kierunku godziny 1szej, aż zmieni się ilość
>     punktów jeśli zmalała ilość punktów, to okrąg zwiększamy, jeśli
>     wzrosła, to zmniejszamy
> 
> Powyższy algorytm raczej nie da optymalnego rozwiązania, ale powinien dać
> całkiem dobre. Będzie działał w czasie N^2.
> 
> Inne założenie: optymalny okrąg musi mieć na swoim obwodzie 3 punkty. Czyli
> rysujemy minimalny okrąg dla każdej pary punktów. Jeśli zawiera za dużo
> punktów, to przerywamy. Jeśli zawiera za mało, to zwiększamy tak, aby
> po kolei dotykał trzeciego punktu. W ten sposób przeiterujemy wszystkie
> potencjalnie optymalne okręgi. Wybieramy najmniejszy. Złożoność N^3 - nie
> taka zła, a intuicja podpowiada mi, że to będzie optymalny algorytm.
> 
> 
> > Co do możliwych danych: dwa niezbyt odległe od siebie skupiska i 
> > trzecie daleko od tamtych dwóch. Różne warianty co do liczby punktów 
> > w każdym z nich.
> Myślę że ten algorytm N^3 poradzi sobie.
> 
> 
> > A i jeszcze coś: gdzie będą punkty n+2, n+3,...  Będzie jakiś punkt 
> > stały, tj co z przejściem do nieskończoności?
> Czyli punkty dane wzorem matematycznym, a nie tabelką? Hmmmm... jak
> się ułożą w ciąg rosnący szybciej niż liniowo (po x i y), to będzie 
> stały punkt. Poza tym przypadkiem może być trudne w analizie.
> 
> 
> Pozdrawiam

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

#28295

On Tuesday, February 9, 2016 at 2:42:57 PM UTC+1, Adam M wrote:
> Problem jest ciekawy i metoda rozwiazania zelzy do ilosci punktow:
> - przy malej ilosci punkow metoda brut-froce lub kazda z wyzej wymienionych metod poradzi sobie calkiem niezle
> - przy duzej ilosci punktow lepsze jest podejscie graficzno-matematyczne.
> tworzymy graficzna reprezentacje rozlozenia punktow i lagorytmy analizy obrazu pozwalaja wybrac nam wrunki graniczne do przeszukiwania (miejsca gdzie jest najwieksze zageszczenie punktow - najbardziej ciemne miejsca). Metoda ta jednak ma jedna podstawowa wade - gdy rozmieszczenie punktow jest losowo rownomierne (bialy szum) graficzna metoda wyznaczenia warunkow brzegowych wyszukiwania padnie na twarz - ale w tym przypadku chyba kazda metoda padnie na twarz i losowe wybranie punktu bedzie najlepsze/najtansze obliczeniowo (bo i tak punkty sa rozlozone losowo ale rownomiernie ;-) )


Czy moje założenie, że optymalne rozwiązanie musi mieć na obwodzie okręgu 3
punkty, jest prawdziwe?

Pozdrawiam

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

#28296

On 09.02.2016 14:59, M.M. wrote:
> On Tuesday, February 9, 2016 at 2:42:57 PM UTC+1, Adam M wrote:
>> Problem jest ciekawy i metoda rozwiazania zelzy do ilosci punktow:
>> - przy malej ilosci punkow metoda brut-froce lub kazda z wyzej wymienionych metod poradzi sobie calkiem niezle
>> - przy duzej ilosci punktow lepsze jest podejscie graficzno-matematyczne.
>> tworzymy graficzna reprezentacje rozlozenia punktow i lagorytmy analizy obrazu pozwalaja wybrac nam wrunki graniczne do przeszukiwania (miejsca gdzie jest najwieksze zageszczenie punktow - najbardziej ciemne miejsca). Metoda ta jednak ma jedna podstawowa wade - gdy rozmieszczenie punktow jest losowo rownomierne (bialy szum) graficzna metoda wyznaczenia warunkow brzegowych wyszukiwania padnie na twarz - ale w tym przypadku chyba kazda metoda padnie na twarz i losowe wybranie punktu bedzie najlepsze/najtansze obliczeniowo (bo i tak punkty sa rozlozone losowo ale rownomiernie ;-) )
>
>
> Czy moje założenie, że optymalne rozwiązanie musi mieć na obwodzie okręgu 3
> punkty, jest prawdziwe?

Tak.
Na płaszczyźnie;-)

I to daje rozwiązanie n^4, przy jakimś sprytnym sposobie zliczania
punktów w okręgu nieco mniej.

Jeśli zaczepisz się o dwa punkty i zwiększasz promień,
wygląda na to, ze da się w n^3 log(n)

W metryce miejskiej to ładniej widać. Zaczepiasz się górnym
i lewym bokiem o dowolną parę, dodajesz tyle punktów,
ile potrzeba, dostajesz w wyniku rozmiar kwadratu.


Przy okręgach pewnym ułatwieniem będzie zauważanie, że
dwa sposród obowiązkowych 3 punktów na promieniu są
oddalone o co najmniej 120deg.

Ostatecznie:
wybieram dwa punkty. A i B. Są one na okręgu.

Dla każdego innego punktu C wyznaczam promień okręgu,
w którym się on jeszcze mieści. Tu trzeba się skupić.

Najmniejszy promień jest jak odległość |AB|
i może rosnać w obie strony. Okręgi można to sobie
parametryzować kątem, odległosćią od |AB|, co tak kto lubi,
byleby łatwo zyanczać środek takiego okręgu i jego promień.

niech będzie to d, odelgłość ś©odka okręgu od AB.
R = sqrt(d^2 + (|AB|/2)^2), środek też łatwo wyznaczyć.

Co istotne, d ma znak, dla dodatnich niech okrąg puchnie w prawo,
dla ujemnych - w lewo.

Każdy punkt C ma wartość _jedną_ (*) krytyczną d. Po jednej jej stronie
jest w okręgu, po drugiej jest poza.

W czasie O(n) wyzanczamy d dla każdego c.
W czasie O(n log (n)) sortujemy je.

W czasie O(n) przechodzimy powstałą tabelkę dwoma wskaźnikami,
zmieniając d. Aktualizujemy wartość promienia, jeśli jest mniejszy
i mamy >=50% miast.

Wszystko powtorzyliśmy O(n^2), łącznie mamy więc
O(n^3 log n)

Nie jest źle. A można wprowadzić sporo obcięć,
jak te z warunku o 120deg czy nie przeszukiwać d dla których
R jest większe niż już znalezione, i, co ważniejsze, nie brać
punktów A,B, które są oddalone o więcej niż aktualnie najlepsze R.
To ostatnie sporo poprawi, jeśli szybko znajdziemy przyzwoite
rozwiązanie.


*) uwagal na punkty leżące wewnętrz odcinka AB:)

pzdr
bartekltg


pzdr
bartekltg

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

#28298

On Tuesday, February 9, 2016 at 6:06:03 PM UTC+1, bartekltg wrote:
> On 09.02.2016 14:59, M.M. wrote:
> > On Tuesday, February 9, 2016 at 2:42:57 PM UTC+1, Adam M wrote:
> >> Problem jest ciekawy i metoda rozwiazania zelzy do ilosci punktow:
> >> - przy malej ilosci punkow metoda brut-froce lub kazda z wyzej wymienionych metod poradzi sobie calkiem niezle
> >> - przy duzej ilosci punktow lepsze jest podejscie graficzno-matematyczne.
> >> tworzymy graficzna reprezentacje rozlozenia punktow i lagorytmy analizy obrazu pozwalaja wybrac nam wrunki graniczne do przeszukiwania (miejsca gdzie jest najwieksze zageszczenie punktow - najbardziej ciemne miejsca). Metoda ta jednak ma jedna podstawowa wade - gdy rozmieszczenie punktow jest losowo rownomierne (bialy szum) graficzna metoda wyznaczenia warunkow brzegowych wyszukiwania padnie na twarz - ale w tym przypadku chyba kazda metoda padnie na twarz i losowe wybranie punktu bedzie najlepsze/najtansze obliczeniowo (bo i tak punkty sa rozlozone losowo ale rownomiernie ;-) )
> >
> >
> > Czy moje założenie, że optymalne rozwiązanie musi mieć na obwodzie okręgu 3
> > punkty, jest prawdziwe?
> 
> Tak.
> Na płaszczyźnie;-)
> 
> I to daje rozwiązanie n^4, przy jakimś sprytnym sposobie zliczania
> punktów w okręgu nieco mniej.
> 
> Jeśli zaczepisz się o dwa punkty i zwiększasz promień,
> wygląda na to, ze da się w n^3 log(n)
> 
> W metryce miejskiej to ładniej widać. Zaczepiasz się górnym
> i lewym bokiem o dowolną parę, dodajesz tyle punktów,
> ile potrzeba, dostajesz w wyniku rozmiar kwadratu.
> 
> 
> Przy okręgach pewnym ułatwieniem będzie zauważanie, że
> dwa sposród obowiązkowych 3 punktów na promieniu są
> oddalone o co najmniej 120deg.
> 
> Ostatecznie:
> wybieram dwa punkty. A i B. Są one na okręgu.
> 
> Dla każdego innego punktu C wyznaczam promień okręgu,
> w którym się on jeszcze mieści. Tu trzeba się skupić.
> 
> Najmniejszy promień jest jak odległość |AB|
> i może rosnać w obie strony. Okręgi można to sobie
> parametryzować kątem, odległosćią od |AB|, co tak kto lubi,
> byleby łatwo zyanczać środek takiego okręgu i jego promień.
> 
> niech będzie to d, odelgłość ś(c)odka okręgu od AB.
> R = sqrt(d^2 + (|AB|/2)^2), środek też łatwo wyznaczyć.
> 
> Co istotne, d ma znak, dla dodatnich niech okrąg puchnie w prawo,
> dla ujemnych - w lewo.
> 
> Każdy punkt C ma wartość _jedną_ (*) krytyczną d. Po jednej jej stronie
> jest w okręgu, po drugiej jest poza.
> 
> W czasie O(n) wyzanczamy d dla każdego c.
> W czasie O(n log (n)) sortujemy je.
> 
> W czasie O(n) przechodzimy powstałą tabelkę dwoma wskaźnikami,
> zmieniając d. Aktualizujemy wartość promienia, jeśli jest mniejszy
> i mamy >=50% miast.
> 
> Wszystko powtorzyliśmy O(n^2), łącznie mamy więc
> O(n^3 log n)
> 
> Nie jest źle. A można wprowadzić sporo obcięć,
> jak te z warunku o 120deg czy nie przeszukiwać d dla których
> R jest większe niż już znalezione, i, co ważniejsze, nie brać
> punktów A,B, które są oddalone o więcej niż aktualnie najlepsze R.
> To ostatnie sporo poprawi, jeśli szybko znajdziemy przyzwoite
> rozwiązanie.
> 
> 
> *) uwagal na punkty leżące wewnętrz odcinka AB:)

Zapomniałem w pośpiechu wymnożyć złożoność przez log(N). 
Ma ktoś ochotę zaimplementować ten algorytm?

Pozdrawiam

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

#28300

On Wed, 10 Feb 2016 01:46:57 -0800 (PST), "M.M." <mmarszik@gmail.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. Ale ogólnie powinno 
działać.

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

#28301

On Friday, February 12, 2016 at 2:50:02 PM UTC+1, slawek wrote:
> On Wed, 10 Feb 2016 01:46:57 -0800 (PST), "M.M." <mmarszik@gmail.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. Ale ogólnie powinno 
> działać.

http://fotowrzut.pl/tmp/upload/ANUHOQ0Z7U/1.jpg

Gdy będziesz rzutował na oś X, to grupa z lewej będzie miała mniejszy
promień, a bez rzutowania większy.

Pozdrawiam

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

#28303

Użytkownik "M.M." <mmarszik@gmail.com> napisał w wiadomości grup 
dyskusyjnych:96d06122-0b5d-4ab1-927f-f740a2ecf74e@googlegroups.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.

 

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

#28302

On 12.02.2016 14:49, slawek wrote:
> On Wed, 10 Feb 2016 01:46:57 -0800 (PST), "M.M." <mmarszik@gmail.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

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

#28304

Użytkownik "bartekltg" <bartekltg@gmail.com> napisał w wiadomości grup 
dyskusyjnych:n9l2s2$s8s$1@node2.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.
 

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

#28306

On Friday, February 12, 2016 at 8:03:05 PM UTC+1, slawek wrote:
> Użytkownik "bartekltg" <bartekltg@gmail.com> napisał w wiadomości grup 
> dyskusyjnych:n9l2s2$s8s$1@node2.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

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

#28308

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" <bartekltg@gmail.com> napisał w wiadomości grup
>> dyskusyjnych:n9l2s2$s8s$1@node2.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

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

#28310

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" <bartekltg@gmail.com> napisał w wiadomości grup
> >> dyskusyjnych:n9l2s2$s8s$1@node2.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

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

#28312

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" <bartekltg@gmail.com> napisał w wiadomości grup
> >> dyskusyjnych:n9l2s2$s8s$1@node2.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

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

#28305

Użytkownik "bartekltg" <bartekltg@gmail.com> napisał w wiadomości grup 
dyskusyjnych:n9l2s2$s8s$1@node2.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). 

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

#28307

On 12.02.2016 20:12, slawek wrote:
>
> Użytkownik "bartekltg" <bartekltg@gmail.com> napisał w wiadomości grup
> dyskusyjnych:n9l2s2$s8s$1@node2.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

[toc] | [prev] | [standalone]

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

csiph-web