Liczby całkowite w C++ można interpretować jako maski bitowe. Mamy do dyspozycji następujące operacje bitowe: & to and (koniunkcja), | to or (alternatywa), ^ to xor (różnica symetryczna), ~ to not (negacja), << to shl (przesunięcie bitowe w lewo o podaną liczbę bitów), >> to shr (przesunięcie bitowe w prawo). Do tego mamy jeszcze operatory traktujące liczby niezerowe jako prawdę, a zero jako fałsz: && to koniunkcja logiczna, || to alternatywa logiczna, ! to negacja logiczna.
Znajomość priorytetów operatorów logicznych nie jest powszechna, a błędy w tym zakresie są bardzo trudne do wychwycenia (np. jaka jest kolejność operacji w a | b + c czy a & b && c?). Dlatego polecam nawiasować wszystko z operatorami bitowymi jak się da, a pomijać nawiasowanie tylko wtedy, kiedy jest się absolutnie pewnym, że tak jest dobrze.
Liczbę całkowitą 32-bitową (int) możemy teraz traktować jako podzbiór zbioru {0, 1, ..., 31}. Oto przykłady operacji na takich zbiorach:
Zadanie: Mamy dany graf nieskierowany G = (V, E), |V| = n. Chcemy podzielić zbiór V na dwie rozłączne części V1 i V2, tak aby liczba krawędzi prowadzących z jednego z tych zbiorów do drugiego była jak największa. Założenie: n ≤ 25.
To jest tzw. problem NP-trudny, czyli nie należy się spodziewać istnienia jakiegoś algorytmu wielomianowego rozwiązującego ten problem. Dzięki maskom bitowym możemy zaimplementować narzucający się algorytm wykładniczy efektywnie. W tym celu musimy poczynić kilka spostrzeżeń:
int wynik = 0;
for (int mask = 0; mask < (1 << n); ++mask) {
int akt = 0;
for (int i = 0; i < n; ++i)
if (mask & (1 << i)) {
akt += zapalone_bity(g[i] & (~mask));
}
wynik = max(wynik, akt);
}
return wynik;
Pozostaje kwestia, jak zliczać zapalone bity w liczbie. Jeśli używamy kompilatora z rodziny GCC, możemy posłużyć się zbudowaną instrukcją __builtin_popcount, która robi dokładnie to, co chcemy (na SIO kompilujemy w GCC). (Przy okazji warto wspomnieć o istnieniu pokrewnej instrukcji __builtin_ctz zliczającej najmniej znaczące zera liczby, czyli podającej indeks pierwszego zapalonego bitu). Jeśli nie mamy GCC, możemy posłużyć się tzw. tablicowaniem. Dla wszystkich liczb, powiedzmy, 16-bitowych wyznaczamy liczby zapalonych bitów, spamiętujemy je w tablicy, a wówczas przy obliczaniu liczby zapalonych bitów dzielimy naszego inta na połówki. Kod tablicowania to:
int zapalone[1 << 16]; // wyzerowane
for (int mask = 0; mask < (1 << 16); ++mask) {
zapalone[mask] = zapalone[mask / 2] + mask % 2;
}
a kod funckji zapalone_bity to:
int zapalone_bity(int a) {
return zapalone[a >> 16] + zapalone[a & ((1 << 16) - 1)];
}
Łącznie w rozwiązaniu wykonujemy rzędu O(2n*n) operacji.
W grafie nieskierowanym chcemy zliczyć trójkąty, czyli trójki wierzchołków połączone każdy z każdym. Tutaj n ≤ 1500, a rozwiązanie wielomianowe o złożoności O(n3) jest oczywiste. (To zadanie da się też rozwiązać w czasie O(m3/2), gdzie m to liczba krawędzi grafu, ale nie będziemy się tym rozwiązaniem przejmować).
Tutaj również można wykorzystać maski bitowe. Tylko tym razem graf nie zmieści się w tablicy intów, więc musimy go upakować w tablicę dwuwymiarową mask bitowych: int g[n][(n + 31) / 32]. Teraz już implementacja jest zupełnie jasna:
long long wynik = 0;
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
if (g[i][j / 32] & (1 << (j % 32))) { // jest krawędź z i do j
for (int k = 0; k < (n + 31) / 32; ++k)
wynik += zapalone_bity(g[i][k] & g[j][k]);
return wynik / 6;
Koszt algorytmu to O(n3/B), przy czym B oznacza liczbę bitów, jaką mamy do dyspozycji (B=32, B=64...).
Patrz także mój artykuł z Delty na ten temat (PDF).
Mamy dany graf skierowany G. Domknięciem zwrotno-przechodnim grafu G nazywamy graf G*, w którym dwa wierzchołki są połączone krawędzią, jeśli w oryginalnym grafie były połączone ścieżką (być może jednowierzchołkową). Rozwiązanie O(n3) to tzw. algorytm Floyda-Warshalla. Pokaż rozwiązanie działające w czasie O(n3/B).
Znów dany jest graf nieskierowany o n wierzchołkach. Chcemy znaleźć w nim doskonałe skojarzenie, czyli taki podział wierzchołków na pary, że wierzchołki w każdej parze są połączone krawędzią. Wystarczy nam informacja, czy takie skojarzenie istnieje. Mamy n ≤ 25.
Uwagi rozszerzające: Znane są algorytmy wielomianowe rozwiązujące ten problem, działające w czasie O(n4) lub nawet O(n3). Są one jednak dość trudne. W grafie dwudzielnym mamy algorytm przez ścieżki naprzemienne, działający w czasie O(n3) (tak naprawdę O(n * m)). Na upartego można by dzielić wierzchołki grafu na dwa podzbiory na wszystkie możliwe sposoby (patrz zad. 1), a potem wyrzucać krawędzie mieszczące się w ramach tych podzbiorów i uruchamiać algorytm skojarzenia w grafie dwudzielnym. Otrzymalibyśmy w ten sposób algorytm O(2n * n3), i do tego trochę skomplikowany. A da się prościej.
Pokażemy, jak to zadanie rozwiązać prościej, w koszcie czasowym wykładniczym. Zastosujemy programowanie dynamiczne: dla każdego możliwego podzbioru zbioru wierzchołków chcemy stwierdzić, czy da się skojarzyć wszystkie wierzchołki w ramach tego podzbioru (nieważne jakie jest to skojarzenie, ważne czy jest). Skoro to programowanie dynamiczne, to przy obliczaniu wyników dla większcyh zbiorów będziemy korzystali z wyników dla mniejszych. Mamy zatem tablicę bool czy[1 << 25], zainicjowaną fałszem poza czy[0] = 1, chcemy ją wypełnić i zwrócić czy[(1 << n) - 1]. Obliczywszy czy[mask], możemy na wszystkie możliwe sposoby dodać do tego częściowego skojarzenia jedną krawędź łączącą wierzchołki spoza zbioru mask, przechodząc w ten sposób do dalszego stanu w programowaniu dynamicznym. Oto kod:
for (int mask = 0; mask < (1 << n); ++mask)
if (czy[mask])
for (int i = 0; i < n; ++i)
if (!(mask & (1 << i)))
for (int j = 0; j < n; ++j)
if ((g[i] & (1 << j)) // jest krawędź z i do j
&& !(mask & (1 << j)))
czy[mask | (1 << i) | (1 << j)] = 1;
return czy[(1 << n) - 1];
Mamy tu ewidentnie O(2n * n2) operacji. A da się lepiej, jeśli tylko sprytniej obsłużymy dwie wewnętrzne pętle. Otóż wystarczy wziąć dowolne i znajdujące się poza aktualną maską i tylko dla niego szukać odpowiednich j. Faktycznie, jeśli istnieje doskonałe skojarzenie, to wierzchołek i musi z czymś być połączony. Dzięki tej drobnej modyfikacji otrzymujemy rozwiązanie o koszcie czasowym O(2n * n). Chyba nie muszę nikogo przekonywać, że rozwiązanie działające 25 razy szybciej jest ewidentnie lepsze.
for (int mask = 0; mask < (1 << n); ++mask)
if (czy[mask]) {
int i0 = -1;
for (int i = 0; i < n; ++i)
if (!(mask & (1 << i))) {
i0 = i;
break;
}
if (i0 != -1) {
for (int j = 0; j < n; ++j)
if ((g[i] & (1 << j)) && !(mask & (1 << j)))
czy[mask | (1 << i0) | (1 << j)] = 1;
}
}
return czy[(1 << n) - 1];
Pytanie rozszerzające: Jak na podstawie tablicy czy odtworzyć doskonałe skojarzenie? W czasie O(n2) i bez dodatkowej pamięci!
Zadanie domowe: Trójkąty na ASD-SIO. Warto dokładnie przeczytać treść zadania.