Witam serdecznie,
Mam pytanie trochę algorytmiczne. Nie mam się kogo poradzić i postanowiłem poszukać pomocy tutaj.
Mam pewne zagadnienie: Mamy trzy zbiory \(\displaystyle{ A, B}\) i \(\displaystyle{ C}\) i szukamy czy w zbiorze \(\displaystyle{ C}\) występuje przynajmniej jedna suma dwóch elementów ze zbioru \(\displaystyle{ A}\) i \(\displaystyle{ 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 \(\displaystyle{ A}\) i \(\displaystyle{ B}\), a ostatnią tablicę (zbiór \(\displaystyle{ C}\)) sortuję i jak już mam jakąś sumę to w \(\displaystyle{ 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 \(\displaystyle{ A}\) i \(\displaystyle{ B}\).
Czy da się to jakoś optymalniej rozwiązać?
Przepraszam jeżeli zły dział (oj pewnie zły).
Pytanie trochę algorytmiczne - suma elementów
-
Morfeo
- Użytkownik
- Posty: 32
- Rejestracja: 8 wrz 2015, o 19:21
- Płeć: Mężczyzna
- Lokalizacja: z daleka
- Podziękował: 1 raz
Pytanie trochę algorytmiczne - suma elementów
Ostatnio zmieniony 8 wrz 2015, o 20:27 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
-
Adifek
- Użytkownik
- Posty: 1567
- Rejestracja: 15 gru 2008, o 16:38
- Płeć: Mężczyzna
- Lokalizacja: Ostrzeszów/Wrocław
- Podziękował: 8 razy
- Pomógł: 398 razy
Pytanie trochę algorytmiczne - suma elementów
Zakładam, że mamy tablice \(\displaystyle{ A = (a[1],..,a[n]), \ B= (b[1],..,b[m]), \ C = (c[1],..,c[k])}\).
1. Znajdujemy \(\displaystyle{ A_{\min },\ A_{\max },\ B_{\min }, \B_{\max },\ C_{\min }, \ C_{\max }}\).
2. \(\displaystyle{ A_{\min }+B_{\min }}\) jest najmniejszym elementem tablicy sum, a \(\displaystyle{ A_{\max }+B_{\max }}\) największym. Stąd jeśli przedziały \(\displaystyle{ [A_{\min }+B_{\min },A_{\max }+B_{\max }]}\) i \(\displaystyle{ [C_{\min }, C_{\max }]}\) są rozłączne, to nic nie znajdziemy i koniec.
3. Załóżmy, że nie jest tak fajnie. Posortujmy wtedy \(\displaystyle{ A}\) i \(\displaystyle{ B}\). Koszt to \(\displaystyle{ 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ę \(\displaystyle{ S[i,j] = a + b[j]}\), to, ponieważ posortowaliśmy tablice, element \(\displaystyle{ S[\lfloor n\slash 2\rfloor , \lfloor m\slash 2\rfloor ]}\)dzieliłby ją na 4 ćwiartki.
Mielibyśmy więc coś w stylu
\(\displaystyle{ 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. \(\displaystyle{ S[\lfloor n\slash 2\rfloor , \lfloor m\slash 2\rfloor ]}\). Podobnie każdy element czwartej ćwiartki jest większy równy od \(\displaystyle{ S[\lfloor n\slash 2\rfloor +1 , \lfloor m\slash 2\rfloor +1]}\). Oznaczmy więc teraz:
\(\displaystyle{ s_1 = A_{\min }+B_{\min }}\),
\(\displaystyle{ s_2 = S[\lfloor n\slash 2\rfloor , \lfloor m\slash 2\rfloor ]}\),
\(\displaystyle{ s_3 = S[\lfloor n\slash 2\rfloor +1 , \lfloor m\slash 2\rfloor +1]}\),
\(\displaystyle{ s_4 = A_{\max }+B_{\max }}\).
Zauważ, że do tej pory nie stworzyliśmy tablicy \(\displaystyle{ S}\). Policzyliśmy tylko cztery elementy.
5. Rozpatrujemy przypadki.
a) Jeśli \(\displaystyle{ [s_1,s_4] \cap [C_{\min }, C_{\max }] \subseteq [s_1, s_2]}\), to przelatujemy tylko elementy pierwszej ćwiartki.
b) Jeśli \(\displaystyle{ [s_1,s_4] \cap [C_{\min }, C_{\max }] \subseteq [s_3, s_4]}\), to przelatujemy tylko elementy czwartej ćwiartki.
c) Jeśli \(\displaystyle{ [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 \(\displaystyle{ [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 \(\displaystyle{ [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ę \(\displaystyle{ 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.
1. Znajdujemy \(\displaystyle{ A_{\min },\ A_{\max },\ B_{\min }, \B_{\max },\ C_{\min }, \ C_{\max }}\).
2. \(\displaystyle{ A_{\min }+B_{\min }}\) jest najmniejszym elementem tablicy sum, a \(\displaystyle{ A_{\max }+B_{\max }}\) największym. Stąd jeśli przedziały \(\displaystyle{ [A_{\min }+B_{\min },A_{\max }+B_{\max }]}\) i \(\displaystyle{ [C_{\min }, C_{\max }]}\) są rozłączne, to nic nie znajdziemy i koniec.
3. Załóżmy, że nie jest tak fajnie. Posortujmy wtedy \(\displaystyle{ A}\) i \(\displaystyle{ B}\). Koszt to \(\displaystyle{ 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ę \(\displaystyle{ S[i,j] = a + b[j]}\), to, ponieważ posortowaliśmy tablice, element \(\displaystyle{ S[\lfloor n\slash 2\rfloor , \lfloor m\slash 2\rfloor ]}\)dzieliłby ją na 4 ćwiartki.
Mielibyśmy więc coś w stylu
\(\displaystyle{ 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. \(\displaystyle{ S[\lfloor n\slash 2\rfloor , \lfloor m\slash 2\rfloor ]}\). Podobnie każdy element czwartej ćwiartki jest większy równy od \(\displaystyle{ S[\lfloor n\slash 2\rfloor +1 , \lfloor m\slash 2\rfloor +1]}\). Oznaczmy więc teraz:
\(\displaystyle{ s_1 = A_{\min }+B_{\min }}\),
\(\displaystyle{ s_2 = S[\lfloor n\slash 2\rfloor , \lfloor m\slash 2\rfloor ]}\),
\(\displaystyle{ s_3 = S[\lfloor n\slash 2\rfloor +1 , \lfloor m\slash 2\rfloor +1]}\),
\(\displaystyle{ s_4 = A_{\max }+B_{\max }}\).
Zauważ, że do tej pory nie stworzyliśmy tablicy \(\displaystyle{ S}\). Policzyliśmy tylko cztery elementy.
5. Rozpatrujemy przypadki.
a) Jeśli \(\displaystyle{ [s_1,s_4] \cap [C_{\min }, C_{\max }] \subseteq [s_1, s_2]}\), to przelatujemy tylko elementy pierwszej ćwiartki.
b) Jeśli \(\displaystyle{ [s_1,s_4] \cap [C_{\min }, C_{\max }] \subseteq [s_3, s_4]}\), to przelatujemy tylko elementy czwartej ćwiartki.
c) Jeśli \(\displaystyle{ [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 \(\displaystyle{ [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 \(\displaystyle{ [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ę \(\displaystyle{ 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.
Ostatnio zmieniony 9 wrz 2015, o 00:11 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
-
Morfeo
- Użytkownik
- Posty: 32
- Rejestracja: 8 wrz 2015, o 19:21
- Płeć: Mężczyzna
- Lokalizacja: z daleka
- Podziękował: 1 raz
Pytanie trochę algorytmiczne - suma elementów
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ę...
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ę...
-
Medea 2
- Użytkownik
- Posty: 2491
- Rejestracja: 30 lis 2014, o 11:03
- Płeć: Kobieta
- Podziękował: 23 razy
- Pomógł: 479 razy
Pytanie trochę algorytmiczne - suma elementów
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ć