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.

do góry

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

do góry

On Tue, 9 Feb 2016 02:35:31 -0800 (PST), "M.M." <m...@g...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?

do góry

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." <m...@g...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

do góry

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

do góry

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

do góry

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

pzdr
bartekltg


pzdr
bartekltg

do góry

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

do góry

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. Ale ogólnie powinno
działać.

do góry

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

do góry