24.06.2022Dzięki rozwojowi technologii cyfrowych możemy skorzystać z jednej z wielu aplikacji nawigacyjnych dostępnych na smartfony i tablety. Używane przez nas na co dzień systemy (jak np. Google lub Apple Maps), potrafią w ciągu kilku chwil wyznaczyć szybkie (o ile nie najszybsze) połączenie drogowe z naszej obecnej lokalizacji do niemal każdego wybranego celu.
Z własnego doświadczenia wiemy jednak, że wyznaczanie trasy wymaga często uwzględnienia kryteriów innych niż dystans, bądź czas niezbędny do pokonania trasy. Czy można pokonać ją rowerem lub traktorem? Czy składa się z samych odcinków dwupasmowych? Czy skorzystanie z wybranej trasy wiąże się z opłatami? W takich sytuacjach, szukając najlepszego rozwiązania powinniśmy najpierw odpowiedzieć sobie na fundamentalne pytanie: czy trasa spełniająca kryteria w ogóle jest możliwa do znalezienia i czy jesteśmy gotowi zaakceptować jakąkolwiek, niekoniecznie najkrótszą trasę?
W teorii grafów zadania tego typu modeluje się w ramach problemu znajdowania (najkrótszych) ścieżek w grafach skierowanych. Grafy skierowane to zbiory wierzchołków i jednokierunkowych połączeń (krawędzi) między parami wierzchołków. Ścieżki w grafach to po prostu ciągi krawędzi, w których każda krawędź prowadzi do początkowego wierzchołka następnej. Przykładowo, w sieciach drogowych wierzchołki grafu modelują skrzyżowania, a krawędzie fragmenty dróg pomiędzy „sąsiednimi” skrzyżowaniami. Gdy interesuje nas jedynie istnienie ścieżki w grafie (a więc informacja typu tak/nie), a nie jej faktyczny kształt, mówimy o problemie osiągalności w grafie.
Teoria versus rzeczywistość – jak uwzględnić w algorytmie ciągłą zmianę?
Zastosowanie problemów osiągalności i znajdowania ścieżek nie ogranicza się oczywiście tylko do sieci drogowych. Z takimi problemami – i to na ogromną skalę – zmagają się dziś twórcy systemów nawigacyjnych, których używamy m.in. w komunikacji publicznej, kolei, żegludze, logistyce, turystyce czy lotnictwie. Przydają się one również w tak nieoczywistych zadaniach jak np. analiza sieci społecznościowych czy analiza kodu źródłowego programów komputerowych. Z punktu widzenia teoretycznego te zagadnienia są stosunkowo dobrze przebadane, tj. znamy optymalne algorytmy rozwiązujące te problemy. Klasyczna literatura na ten temat (np. słynne “Wprowadzenie do algorytmów” Cormena i in.) przyjmuje jednak założenie teoretyczne, które ogranicza ich efektywne stosowanie w rozwiązywaniu wyzwań napotykanych w rzeczywistości – graf nie zmienia się w czasie. Sieci występujące w świecie podlegają jednak ciągłym zmianom: powstają nowe lub remontowane są istniejące drogi, dodajemy nowych znajomych na Facebooku, bądź obserwujemy kolejne konta na Twitterze itp. W wymiarze matematycznym takie działania powodują powstanie nowej krawędzi w odpowiadającej sieci. Grafy podlegające zmianom w czasie nazywamy dynamicznymi, zaś algorytmy na takich grafach, potrafiące przetworzyć małą zmianę szybciej niż obliczając wszystko od nowa – algorytmami dynamicznymi.
Wyobraźmy sobie, że interesuje nas jakaś konkretna para wierzchołków (A, B) i istnienie ścieżki (najkrótszej lub jakiejkolwiek) pomiędzy nimi. Wydawać by się mogło, że po małej zmianie grafu – dodaniu lub usunięciu pojedynczej spośród tysięcy krawędzi – powinniśmy być w stanie znaleźć nową ścieżkę istotnie szybciej, niż rozpoczynając wszystko od nowa (bo przecież interesująca nas sieć „prawie wcale” się nie zmieniła). Niestety, w ogólności (tj. bez dodatkowych założeń dotyczących sieci) tak nie jest, przynajmniej jeśli ograniczymy się do praktycznych algorytmów. Wiadomo, że da się to osiągnąć tylko uciekając się do tzw. szybkiego mnożenia macierzy, zaawansowanego algorytmu algebry liniowej (tu link do wpisu na ten temat w Wikipedii).Teoretycy, algorytmy bazujące na szybkim mnożeniu macierzy nazywają zbiorczo algorytmami algebraicznymi. Choć teoretycznie najszybsze znane algorytmy szybkiego mnożenia macierzy uważa się obecnie za niepraktyczne, metody algebraiczne rozwiązywania problemów grafowych niezmiennie cieszą się wśród informatyków dużym zainteresowaniem.
Problem czarnej skrzynki w dynamicznych, algebraicznych algorytmach znajdowania ścieżek
Dotychczas znane dynamiczne algebraiczne algorytmy znajdowania ścieżek w większości potrafiły jedynie określać czy dana ścieżka w ogóle istnieje (a więc rozwiązywały jedynie problem osiągalności), bądź obliczać jej długość. Nie potrafiły jednak efektywnie wskazać żadnej konkretnej ścieżki, co mocno ograniczało ich dalsze zastosowania. Pierwszy dynamiczny algorytm potrafiący konstruować takie ścieżki został pokazany dopiero niedawno na konferencji SODA [Bergamaschi i in., SODA’21]. Ma on jednak poważną wadę – daje (z dużym prawdopodobieństwem) poprawne wyniki tylko, gdy założy się, że jego użytkownik nie jest bardzo złośliwy. Jak to rozumieć? Jego teoretyczne własności pozostają w mocy jedynie, jeśli kolejne zmiany grafu nie zależą od poprzednich ścieżek wyznaczonych przez algorytm.
Przypuśćmy, że pewnego weekendu używamy naszego algorytmu do zaplanowania wycieczki rowerowej z punktu A do B. W kolejny weekend znów chcemy wybrać się na wycieczkę rowerową z C do D, ale tak, żeby nie jechać tymi samymi drogami co ostatnio. Kolejną drogę można więc zaplanować usuwając najpierw pokonane za pierwszym razem drogi z sieci (co modeluje nasze kryterium, aby drogi się nie powtarzały), a następnie prosząc algorytm o wyznaczenie nowej trasy. W takiej sytuacji algorytm może mieć problem z poprawnym wyznaczeniem kolejnej trasy, gdyż drogi usunięte przed drugim zapytaniem to dokładnie te, które algorytm wyznaczył za ostatnim razem. To zjawisko ma związek z używaniem losowości i potencjalnym ujawnieniem („wyciekiem”) losowych wyborów algorytmu poprzez ujawnienie znalezionej ścieżki w grafie. Niestety, to założenie, nazywane w nauce terminem tzw. nieświadomego adwersarza jest silne i nie pozwala łatwo stosować algorytmu w charakterze „czarnej skrzynki” do uzyskiwania dalszych algorytmów o dobrych własnościach teoretycznych. Jedną z metod radzenia sobie z tym problemem jest szukanie rozwiązań deterministycznych, czyli unikających randomizacji. Niestety, często okazuje się to trudnym zadaniem.
Znalezienie odpowiedzi na to wyzwanie przyświecało badaczom IDEAS NCBR Adamowi Karczmarzowi, Anishowi Mukherjee i Piotrowi Sankowskiemu w artykule Subquadratic Dynamic Path Reporting in Directed Graphs Against an Adaptive Adversary (arxiv). W swojej publikacji opisali oni pierwszy dotychczas nietrywialny (nieobliczający wszystkiego od nowa) w pełni dynamiczny (obsługujący zarówno dodania jak i usunięcia krawędzi) algorytm znajdujący ścieżki w grafach skierowanych, który działa w ogólniejszym modelu tzw. silnego adaptacyjnego adwersarza. Zaproponowany algorytm, choć randomizowany, może być stosowany zatem ,,w ciemno’’, tj. bez ryzyka degradacji jego poprawności czy efektywności. Dodatkowo, w ograniczonym modelu inkrementalnym, w którym dopuszcza się jedynie dodawanie nowych krawędzi (a nie ich usuwanie), autorzy pokazują nowe deterministyczne dynamiczne algorytmy znajdowania ścieżek.
Wyniki pracy badaczy zostaną zaprezentowane i omówione w czerwcu b.r. na konferencji STOC 2022 w Rzymie.
Adam Karczmarz jest badaczem w IDEAS NCBR i adiunktem na Wydziale Matematyki Informatyki i Mechaniki Uniwersytetu Warszawskiego. W swojej pracy naukowej koncentruje się na algorytmach grafowych i strukturach danych.
