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

Groups > pl.comp.programming > #28296

Re: Problemik algorytmiczny

Show all headers | View raw

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

Back to pl.comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

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

csiph-web