Informatyczny kącik olimpijski
Infiltracja
Tym razem zajmiemy się zadaniem z finałów Akademickich Mistrzostw Świata w Programowaniu Zespołowym 2012, które odbyły się w Warszawie. Zadanie zatytułowane Infiltration zostało rozwiązane przez 31 spośród 112 drużyn i było średnim pod względem trudności zadaniem na tych zawodach.
W zadaniu dany jest graf skierowany o
wierzchołkach
, w którym każda nieuporządkowana para wierzchołków
i
jest połączona dokładnie jedną krawędzią skierowaną
(taki graf nazywa się turniejem). Możemy wykonywać operacje kliknięcia
w wierzchołek, co powoduje zaznaczenie tego wierzchołka oraz wszystkich
wierzchołków, do których wchodzi z niego bezpośrednia krawędź. Naszym
celem jest zaznaczenie wszystkich wierzchołków grafu, chcemy przy tym
zminimalizować liczbę kliknięć. Należy podać tę liczbę oraz dowolny
podzbiór wierzchołków, które należy kliknąć, aby uzyskać ów wynik.
Wierzchołki mogą być zaznaczane wielokrotnie.

Rysunek obok przedstawia przykładowy turniej dla
Kliknięcie
w wierzchołek numer 1 powoduje zaznaczenie wierzchołków 1, 2 oraz
3.
Dosyć intrygujące w tym zadaniu wydaje się choćby ograniczenie na rozmiar
danych wejściowych. Maksymalny rozmiar grafu
wskazuje raczej
na algorytm wielomianowy. Rzadko kiedy mamy jednak do czynienia
z algorytmami o złożoności
czy
Okazuje się, że
w tym zadaniu poszukujemy właśnie takiego algorytmu.
Czasami, aby rozwiązać zadanie dobrze, należy najpierw rozwiązać zadanie źle. Pierwszym pomysłem, który mógłby się nasunąć, byłoby rozwiązanie heurystyczne. Na przykład takie: wybieramy wierzchołek o największym stopniu i klikamy go, następnie wyrzucamy z grafu wszystkie zaznaczone wierzchołki i analogicznie próbujemy zaznaczyć resztę. Rozwiązanie to może nie zadziałać (choćby wtedy, gdy wszystkie wierzchołki mają równy stopień). Narysowanie kontrprzykładu pozostawiam Czytelnikowi (nie jest to, wbrew pozorom, takie łatwe!). Pytanie, jakie należałoby sobie w tym momencie zadać, brzmi:
jaki wynik w najgorszym przypadku zwróci owo błędne rozwiązanie? Odpowiedź może być zaskakująca: zaledwie sześć!
Zauważmy, że każdy wierzchołek jest incydentny z
krawędziami.
Mogą być one skierowane albo od niego, albo do niego. Nie może być tak,
żeby każdy wierzchołek miał większy stopień wejściowy niż wyjściowy,
więc w grafie musi istnieć wierzchołek o stopniu wyjściowym co najmniej
To oznacza, że w pierwszym kroku zaznaczamy co najmniej
połowę wierzchołków. Ponadto po usunięciu zaznaczonych wierzchołków
oraz krawędzi z nimi incydentnych otrzymujemy nadal turniej, a zatem
własność ta zachodzi nie tylko w pierwszym kroku, ale w każdym. Stąd,
jeśli
to w kolejnych krokach zostaje nam co najwyżej
wierzchołków niezaznaczonych. Czyli w najgorszym
przypadku wynik dla naszego problemu wynosi sześć, ponadto mamy
algorytm, który takie rozwiązanie znajduje.
Wystarczy zatem sprawdzić, czy wynik może być równy pięć lub mniej.
Najprostsze naiwne rozwiązanie rozpatruje rzędu
konfiguracji
wierzchołków, co dla
daje ponad 2 miliardy, czyli zdecydowanie
za dużo (zwłaszcza że liczba przypadków do rozpatrzenia w jednym
pliku testowym wynosiła kilkanaście). Czy naprawdę jest aż tak źle?
Okazuje się, że nie. Bardzo łatwo zauważyć, że kolejność klikania
wierzchołków jest bez znaczenia. To oznacza, że możemy rozpatrywać
każdą nieuporządkowaną piątkę wierzchołków tylko raz (w poprzednim
rozwiązaniu każdą taką piątkę analizowalibyśmy
razy), a zatem
realnie do przetestowania jest niecałe 20 milionów takich piątek.
Wydawałoby się, że to już koniec. 20 milionów operacji jest wartością
akceptowalną. Sęk w tym, że po uwzględnieniu czasu na klikanie i zaznaczanie
wierzchołków, a także sprawdzenie, czy wszystkie wierzchołki są już
zaznaczone (co z grubsza kosztuje
), sytuacja wygląda zupełnie
inaczej – nadal przekraczamy limit czasu. Czy to oznacza, że należy wykonać
jeszcze mniej sprawdzeń? Na szczęście nie, możemy bowiem zredukować
czas sprawdzenia.
Zbiór krawędzi wychodzących z każdego wierzchołka można reprezentować
w postaci maski bitowej (w tym przypadku można zastosować na przykład
trójkę liczb 32-bitowych lub parę liczb 64-bitowych). Dla ułatwienia
implementacji możemy dla wierzchołka
ustawić dodatkową jedynkę
na pozycji
wtedy maska bitowa będzie reprezentować wszystkie
wierzchołki, które zostaną zaznaczone po kliknięciu w wierzchołek
Jeśli chcemy poznać zbiór zaznaczonych wierzchołków,
powinniśmy wziąć maski bitowe wszystkich klikniętych wierzchołków
i skorzystać z bitowej operacji alternatywy (or). Teraz, aby dowiedzieć się, czy
zaznaczyliśmy wszystkie wierzchołki, wystarczy sprawdzić, czy maska
bitowa zawiera same jedynki. Zastosowanie masek bitowych pozwala zatem
przyspieszyć proces sprawdzania, czy dana piątka wierzchołków jest
rozwiązaniem, o czynnik proporcjonalny do liczby bitów dostępnych
w wybranym typie całkowitoliczbowym.
Na koniec zauważmy, że oszacowanie liczby konfiguracji przez
jest
bardzo pesymistyczne. W zestawie testów nie znalazł się ani jeden przypadek
z wynikiem 6. Pozwala to sądzić, że podany algorytm znajdzie rozwiązanie
dużo wcześniej. Wystarczy choćby, żeby kombinacji dających wynik 5 było
kilka lub żeby algorytm heurystyczny (podany na początku) dał wynik 5.
Proponuję Czytelnikom przygotowanie złośliwych testów do tego zadania, jest
to całkiem trudne wyzwanie.