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