eGospodarka.pl
eGospodarka.pl poleca

eGospodarka.plGrupypl.comp.programmingProblemik algorytmiczny
Ilość wypowiedzi w tym wątku: 19

  • 1. Data: 2016-02-09 10:15:10
    Temat: Problemik algorytmiczny
    Od: slawek <f...@f...com>

    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.


  • 2. Data: 2016-02-09 11:35:31
    Temat: Re: Problemik algorytmiczny
    Od: "M.M." <m...@g...com>

    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


  • 3. Data: 2016-02-09 12:00:56
    Temat: Re: Problemik algorytmiczny
    Od: slawek <f...@f...com>

    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?


  • 4. Data: 2016-02-09 12:44:24
    Temat: Re: Problemik algorytmiczny
    Od: "M.M." <m...@g...com>

    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


  • 5. Data: 2016-02-09 14:42:55
    Temat: Re: Problemik algorytmiczny
    Od: Adam M <a...@m...com>

    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


  • 6. Data: 2016-02-09 14:59:57
    Temat: Re: Problemik algorytmiczny
    Od: "M.M." <m...@g...com>

    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


  • 7. Data: 2016-02-09 18:06:01
    Temat: Re: Problemik algorytmiczny
    Od: bartekltg <b...@g...com>

    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


  • 8. Data: 2016-02-10 10:46:57
    Temat: Re: Problemik algorytmiczny
    Od: "M.M." <m...@g...com>

    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



  • 9. Data: 2016-02-12 14:49:52
    Temat: Re: Problemik algorytmiczny
    Od: slawek <f...@f...com>

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


  • 10. Data: 2016-02-12 16:31:54
    Temat: Re: Problemik algorytmiczny
    Od: "M.M." <m...@g...com>

    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

strony : [ 1 ] . 2


Szukaj w grupach

Szukaj w grupach

Eksperci egospodarka.pl

1 1 1

Wpisz nazwę miasta, dla którego chcesz znaleźć jednostkę ZUS.

Wzory dokumentów

Bezpłatne wzory dokumentów i formularzy.
Wyszukaj i pobierz za darmo: