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