szukanie zaawansowane
 [ Posty: 5 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 8 wrz 2015, o 19:35 
Użytkownik

Posty: 33
Lokalizacja: z daleka
Witam serdecznie,

Mam pytanie trochę algorytmiczne. Nie mam się kogo poradzić i postanowiłem poszukać pomocy tutaj.

Mam pewne zagadnienie: Mamy trzy zbiory A, B i C i szukamy czy w zbiorze C występuje przynajmniej jedna suma dwóch elementów ze zbioru A i B.

Można to zrealizować trywialnie sprawdzając wszystkie kombinacje. Takie rozwiązanie jednak kompletnie mi się nie podoba - jest zbyt wolne.

Rozwiązałem to na chwilę obecną tak, że jadę po wszystkich kombinacjach sum w zbiorach A i B, a ostatnią tablicę (zbiór C) sortuję i jak już mam jakąś sumę to w C wyszukuję ją wykorzystując wyszukiwanie binarne. Same wyszukiwanie jest błyskawiczne (złożoność logarytmiczna) ale to i tak nic nie daje jeżeli mam multum elementów w A i B.

Czy da się to jakoś optymalniej rozwiązać?

Przepraszam jeżeli zły dział (oj pewnie zły).
Góra
Mężczyzna Offline
PostNapisane: 8 wrz 2015, o 22:45 
Moderator

Posty: 4299
Lokalizacja: Kraków PL
Nie napisałeś czym są elementy tych zbiorów. Liczbami?
Góra
Mężczyzna Offline
PostNapisane: 8 wrz 2015, o 23:48 
Użytkownik

Posty: 1568
Lokalizacja: Ostrzeszów/Wrocław
Zakładam, że mamy tablice A = (a[1],..,a[n]), \ B= (b[1],..,b[m]), \ C = (c[1],..,c[k]).

1. Znajdujemy A_{\min },\ A_{\max },\ B_{\min }, \B_{\max },\ C_{\min }, \ C_{\max }.

2. A_{\min }+B_{\min } jest najmniejszym elementem tablicy sum, a A_{\max }+B_{\max } największym. Stąd jeśli przedziały [A_{\min }+B_{\min },A_{\max }+B_{\max }] i [C_{\min }, C_{\max }] są rozłączne, to nic nie znajdziemy i koniec.

3. Załóżmy, że nie jest tak fajnie. Posortujmy wtedy A i B. Koszt to O(m \log m +n\log n). Jeśli w zbiorach jest dużo powtórzeń, to za jednym zamachem i niewielkim kosztem je usuwamy. Wtedy kolejne kroki mocno przyspieszą.

4. Zauważmy, że jeśli byśmy stworzyli dwuwymiarową tablicę S[i,j] = a[i] + b[j], to, ponieważ posortowaliśmy tablice, element S[\lfloor n\slash 2\rfloor , \lfloor m\slash 2\rfloor ]dzieliłby ją na 4 ćwiartki.

Mielibyśmy więc coś w stylu

S = \begin{vmatrix} I&II\\III&IV\end{vmatrix},

gdzie elementy rosną w prawo i w dół. Każdy element pierwszej ćwiartki jest mniejszy równy od tego elementu tej ćwiartki, który jest w jej prawym dolnym rogu, tj. S[\lfloor n\slash 2\rfloor  , \lfloor m\slash 2\rfloor ]. Podobnie każdy element czwartej ćwiartki jest większy równy od S[\lfloor n\slash 2\rfloor +1 , \lfloor m\slash 2\rfloor +1]. Oznaczmy więc teraz:

s_1 = A_{\min }+B_{\min },

s_2 = S[\lfloor n\slash 2\rfloor  , \lfloor m\slash 2\rfloor ],

s_3 = S[\lfloor n\slash 2\rfloor +1 , \lfloor m\slash 2\rfloor +1],

s_4 = A_{\max }+B_{\max }.

Zauważ, że do tej pory nie stworzyliśmy tablicy S. Policzyliśmy tylko cztery elementy.

5. Rozpatrujemy przypadki.

a) Jeśli [s_1,s_4] \cap [C_{\min }, C_{\max }]  \subseteq [s_1, s_2], to przelatujemy tylko elementy pierwszej ćwiartki.

b) Jeśli [s_1,s_4] \cap [C_{\min }, C_{\max }]  \subseteq [s_3, s_4], to przelatujemy tylko elementy czwartej ćwiartki.

c) Jeśli [s_1,s_4] \cap [C_{\min }, C_{\max }]  \subseteq [s_2, s_3], to przelatujemy drugiej i trzeciej ćwiartki.

d) Jeśli żadne z a)-c) oraz jeśli [s_1,s_4] \cap [C_{\min }, C_{\max }]  \subseteq [s_1, s_3], to przelatujemy elementy z pierwszej, drugiej i trzeciej ćwiartki.

e) Jeśli żadne z a)-c) oraz jeśli [s_1,s_4] \cap [C_{\min }, C_{\max }]  \subseteq [s_2, s_4], to przelatujemy elementy z drugiej, trzeciej i czwartej ćwiartki.

f) Jeśli żadne z powyższych, to musimy przelecieć całą tablicę S.


Takie rozwiązanie mi przyszło jako pierwsza myśl. Jestem przekonany, że można zrobić to jeszcze lepiej. Nie wiem niestety jakie masz dane - może masz brzydki przypadek, że prawie zawsze wpadasz w f) - wtedy to nic nie pomoże, a sortowanie jeszcze dołoży pracy. Jeśli jednak regularnie trafiają się wcześniejsze przypadki, to zysk powinien być zauważalny.
Góra
Mężczyzna Offline
PostNapisane: 9 wrz 2015, o 08:18 
Użytkownik

Posty: 33
Lokalizacja: z daleka
Tak. Elementy tych zbiorów są liczbami.

Zapomniałem jednak dodać bardzo istotną rzecz: nie szukamy zwykłej sumy elementów, a sumy modulo dana liczba (nie wiem czy w tym przypadku pomysł Adifek'a zadziała).

Wszystkie liczby w tablicach są de facto także wartościami modulo dana liczba. Jest jednak ich dość dużo, bo i ta wartość modulo w założeniach ma być spora.

Domyślam się, że może to trochę pokićkać sprawę...
Góra
Kobieta Offline
PostNapisane: 9 wrz 2015, o 19:02 
Użytkownik
Avatar użytkownika

Posty: 2505
Nie umiem odpowiedzieć, jakie jest rozwiązanie wersji modularnej, ale w pierwotnym sformułowaniu problem jest piekielnie trudny. Wystarczy zmienić znak elementom trzeciej tablicy i przeczytać https://en.m.wikipedia.org/wiki/3SUM.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 5 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Zadanko z kolokwium, chyba? ciezka suma...  DonPedro  0
 Dowieść, ze suma dwumianów równa się 2 do n.  112  2
 Tablica, liczby, suma  mol_ksiazkowy  1
 Układanie toru kolejki z gotowych elementów  masssa  3
 Suma pewnego szeregu  edward_p  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl