Ciąg dalszy zagadek z pierwszych zajęć, ważne "klasyki":
Dany jest graf nieskierowany o n wierzchołkach, tym razem mamy wagi (nieujemne, całkowite) na krawędziach. Szukamy cyklu przechodzącego przez każdy wierzchołek grafu dokładnie raz, o minimalnej wadze. Mamy n ≤ 20. W literaturze nazywa się to Problemem Komiwojażera (TSP, ang. Travelling Salesman Problem). Jest to problem NP-trudny, czyli nie należy spodziewać się, że da się go rozwiązać w wielomianowej złożoności czasowej.
I tym razem zastosujemy programowanie dynamiczne po maskach bitowych, ale nie tylko. Dla danej maski bitowej mask, jako dp[mask] chcielibyśmy pamiętać długość najkrótszej ścieżki prostej przechodzącej w jakiejś kolejności przez wszystkie wierzchołki z tejże maski. Tego się jednak nie da sensownie obliczać, tj. wyznaczać dla większego podzbioru na podstawie wyników dla mniejszych podzbiorów. Dlatego trzeba dołożyć jeszcze jeden parametr: dp[mask][i] pamięta długość najkrótszej takowej ścieżki kończącej się w wierzchołku i. To pozwoli nam łatwo przedłużać takie ścieżki o jeden wierzchołek.
Zamiast szukać cyklu przechodzącego przez wszystkie wierzchołki, będziemy szukali ścieżki prostej przechodzącej przez wszystkie wierzchołki, zaczynającej się w jakimś ustalonym wierzchołku (np. 0) i kończącej się w jakimkolwiek innym. Każdą taką ścieżkę łatwo uzupełnić do cyklu Hamiltona za pomocą jednej krawędzi prowadzącej do zera. Graf reprezentujemy jako macierz wag krawędzi int t[n][n]; brak krawędzi między i a j oznaczamy jako nieskończoność, czyli, w praktyce, bardzo dużą stałą (ale taką, której dwukrotność mieści się w rozważanym typie, żeby INFTY+INFTY nie wyszło poza zakres typu). Stosowny fragment kodu poniżej:
for (int i = 0; i < n; ++i)
dp[0][i] = dp[1 << 0][i] = INFTY;
dp[1 << 0][0] = 0;
for (int mask = 2; mask < (1 << n); ++mask)
for (int i = 0; i < n; ++i) {
dp[mask][i] = INFTY;
if (mask & (1 << i)) {
int mask1 = mask ^ (1 << i);
for (int j = 0; j < n; ++j)
if (mask1 & (1 << j))
dp[mask][i] = min(dp[mask][i], dp[mask1][j] + t[j][i]);
}
}
int wynik = INFTY;
for (int i = 0; i < n; ++i)
wynik = min(wynik, dp[(1 << n) - 1][i] + t[i][0]);
return wynik;
Mamy tu ewidentnie O(2n * n2) operacji.
Znów dany jest graf nieskierowany o n wierzchołkach. Chcemy podzielić zbiór wierzchołków tego grafu na niepuste podzbiory, tak żeby każdy taki podzbior spełniał pewną zadaną własność. Owa własność jest określona w jakiś sposób; ważne, że jest dostatecznie skomplikowana, żeby zadania nie dało się rozwiązać wielomianowo. Można po prostu założyć, że w tablicy bool czy[1 << n] mamy dla każdej maski bitowej zapisane, czy odpowiadający jej podzbiór wierzchołków spełnia tę własność czy nie. Należy wyznaczyć maksymalną liczbę podzbiorów w szukanym podziale. Mamy n ≤ 18.
Szkic rozwiązania jest całkiem jasny. Znów programowanie dynamiczne: dla danej maski bitowej, jako ile[mask] pamiętamy, na ile maksymalnie dobrych podzbiorów możemy ją podzielić. Z wyłączeniem jednej drobnej niejasności, możemy już właściwie zapisać kod:
ile[0] = 0;
for (int mask = 1; mask < (1 << n); ++mask) {
ile[mask] = -INFTY;
for_all(mask1 będąca podmaską mask)
if (czy[mask1])
ile[mask] = max(ile[mask], ile[mask ^ mask1] + 1);
}
return ile[(1 << n) - 1];
Owa niejasność to oczywiście pytanie, jak wyznaczać wszystkie podzbiory danej maski. Rozwiązanie siłowe:
for (int mask1 = 1; mask1 << mask; ++mask1)
if (((mask & mask1) == mask1) && czy[mask1])
jest niespecjalnie efektywne, gdyż za jego pomocą otrzymujemy rozwiązanie o koszcie czasowym O(4n). Chcielibyśmy jakoś ograniczyć się tylko do niezerowych masek mogących zawierać jedynki jedynie tam gdzie mask. Okazuje się, że można to zrobić tak:
int mask1 = mask;
while (mask1) {
wykonaj_obliczenia_dla(mask1);
mask1 = (mask1 - 1) & mask;
}
Gorąco polecam sprawdzenie na przykładzie, że to rzeczywiście działa. It's a kind of magic...
Należy także zauważyć, że koszt całego rozwiązania przy wykorzystaniu tej metody spada do O(3n). Można to sprawdzić numerycznie: podzbiorów i-elementowych mamy dokładnie dwumian(n,i), dla każdego z nich rozważamy dokładnie wszystkie jego podzbiory, których jest 2i, co wysumowuje się właśnie do 3n. Więcej tłumaczy jednak argument kombinatoryczny. Otóż dla danego układu (mask1, mask), w którym mask1 jest podzbiorem mask, każdy z bitów 0,...,n-1 może mieć jedną z trzech własności: (A) należy do obu masek; (B) należy tylko do mask; (C) nie należy do żadnej z masek. Widzimy także, że układ wartości (A), (B) lub (C) dla każdego bitu pozwala jednoznacznie odtworzyć maski mask1 i mask. To oznacza, że wszystkich par (mask1, mask) jest równo 3n.
Zadanie domowe: implementacja rozwiązania zadania Województwa na ASD-SIO.
Zwięzły opis metod opartych na maskach bitowych jest zawarty w artykule Bruce'a Merry'ego na TopCoderze.