Naukowcy stworzyli rewolucyjny algorytm przepływu sieci, który umożliwia ultraszybkie obliczenia w sieciach dynamicznych, zmieniając sposób podejścia i rozwiązywania problemów w informatyce teoretycznej.
Dokonując przełomu, który przywodzi na myśl Lucky’ego Luke’a – człowieka, który strzela szybciej niż jego cień – Rasmus Kyng i jego zespół opracowali superszybki algorytm, który prawdopodobnie odmieni całą dziedzinę badań. Przełomowa praca zespołu Kynga obejmuje tak zwany algorytm przepływu w sieci, który rozwiązuje problem osiągnięcia maksymalnego przepływu w sieci przy jednoczesnej minimalizacji kosztów transportu.
Wyobraź sobie, że korzystasz z europejskiej sieci transportowej i szukasz najszybszej i najtańszej trasy, aby przewieźć jak najwięcej towarów z Kopenhagi do Mediolanu. W takich przypadkach algorytm Kynga można zastosować do obliczenia optymalnego i najtańszego przepływu ruchu dla dowolnego rodzaju sieci – kolejowej, drogowej, wodnej czy internetowej. Jego algorytm wykonuje te obliczenia tak szybko, że może dostarczyć rozwiązanie w momencie, gdy komputer odczytuje dane opisujące sieć.
Obliczenia tak szybkie jak sieć jest duża
Przed Kyng nikomu się to nie udało – mimo że badacze pracują nad tym problemem od około 90 lat. Wcześniej obliczenie optymalnego przepływu zajmowało znacznie więcej czasu niż przetwarzanie danych sieciowych. W miarę jak sieć stawała się większa i bardziej złożona, wymagany czas obliczeń rósł znacznie szybciej, mówiąc porównywalnie, niż rzeczywisty rozmiar problemu obliczeniowego. Dlatego też widzimy problemy z przepływem w sieciach, które są zbyt duże, aby komputer mógł je w ogóle obliczyć.
Podejście Kynga eliminuje ten problem: przy użyciu jego algorytmu czas obliczeń i rozmiar sieci rosną w tym samym tempie – to trochę jak pójście na wędrówkę i ciągłe utrzymywanie tego samego tempa, niezależnie od tego, jak stroma jest ścieżka. Rzut oka na surowe liczby pokazuje, jak daleko zaszliśmy: aż do przełomu tysiącleci żaden algorytm nie był w stanie wykonywać obliczeń szybciej niż M1,5Gdzie M oznacza liczbę połączeń w sieci, którą komputer musi obliczyć i wystarczy tylko raz odczytać dane sieciowe M czas. W 2004 roku prędkość obliczeniowa wymagana do rozwiązania problemu została pomyślnie zmniejszona do M1,33. Stosując algorytm Kynga, „dodatkowy” czas obliczeń potrzebny na dotarcie do rozwiązania po odczytaniu danych sieciowych jest obecnie znikomy.
Jak Porsche ścigające się powozem konnym
W ten sposób badacze z ETH Zurich opracowali teoretycznie najszybszy możliwy algorytm przepływu sieci. Dwa lata temu Kyng i jego zespół przedstawili matematyczny dowód swojej koncepcji w przełomowym artykule. Naukowcy nazywają te nowatorskie, niemal optymalnie szybkie algorytmy „algorytmami działającymi w czasie prawie liniowym”, a społeczność informatyków teoretycznych zareagowała na przełom Kynga z mieszaniną zdumienia i entuzjazmu.
Promotor Kynga, Daniel A. Spielman, profesor matematyki stosowanej i informatyki w Yale, będący pionierem i seniorem w tej dziedzinie, porównał „absurdalnie szybki” algorytm do wyprzedzania powozów przez porsche. Oprócz zdobycia nagrody za najlepszą publikację 2022 na dorocznym sympozjum IEEE na temat podstaw informatyki (FOCS), ich artykuł został również wyróżniony w czasopiśmie komputerowym Komunikaty ACMoraz redaktorzy magazynu popularnonaukowego Kwanta nazwał algorytm Kynga jednym z dziesięć największych odkryć informatyki w 2022 roku.
Od tego czasu badacze z ETH Zurich udoskonalili swoje podejście i opracowali dalsze algorytmy działające w czasie niemal liniowym. Na przykład pierwszy algorytm w dalszym ciągu skupiał się na sieciach stacjonarnych, statycznych, których połączenia są ukierunkowane, czyli funkcjonują jak ulice jednokierunkowe w sieciach dróg miejskich. Algorytmy opublikowane w tym roku są teraz w stanie obliczyć optymalne przepływy w sieciach, które zmieniają się stopniowo w czasie. Błyskawiczne obliczenia to ważny krok w walce z bardzo złożonymi i bogatymi w dane sieciami, które zmieniają się dynamicznie i bardzo szybko, takimi jak cząsteczki lub mózg w biologii lub przyjaźnie międzyludzkie.
Błyskawiczne algorytmy do zmieniania sieci
W czwartek Simon Meierhans – członek zespołu Kynga – zaprezentował nowy algorytm działający w czasie prawie liniowym podczas dorocznego sympozjum ACM na temat teorii informatyki (STOC) w Vancouver. Algorytm ten rozwiązuje problem maksymalnego przepływu przy minimalnym koszcie w sieciach, które zmieniają się stopniowo w miarę dodawania nowych połączeń. Co więcej, w drugim artykule zaakceptowanym w październiku przez Sympozjum IEEE na temat podstaw informatyki (FOCS) badacze ETH opracowali inny algorytm, który obsługuje również usuwanie połączeń.
W szczególności algorytmy te identyfikują najkrótsze trasy w sieciach, w których połączenia są dodawane lub usuwane. W rzeczywistych sieciach ruchu przykłady takich zmian w Szwajcarii obejmują całkowite zamknięcie, a następnie częściowe ponowne otwarcie tunelu Gotthard Base Tunnel w miesiącach począwszy od lata 2023 r. lub niedawne osunięcie się ziemi, które zniszczyło część autostrady A13, która jest główną alternatywą trasa do tunelu Gotthard Road.
Jak w obliczu takich zmian komputer, internetowy serwis mapowy lub narzędzie do planowania trasy oblicza najtańsze i najszybsze połączenie między Mediolanem a Kopenhagą? Nowe algorytmy firmy Kyng obliczają także optymalną trasę dla tych sieci zmieniających się przyrostowo lub dekrementalnie w czasie niemal liniowym – tak szybko, że czas obliczeń dla każdego nowego połączenia, niezależnie od tego, czy jest dodany w wyniku przekierowania, czy utworzenia nowych tras, jest ponownie znikomy.
Ale co dokładnie sprawia, że podejście Kynga do obliczeń jest o wiele szybsze niż jakikolwiek inny algorytm przepływu sieci? W zasadzie wszystkie metody obliczeniowe stoją przed wyzwaniem polegającym na konieczności analizowania sieci w wielu iteracjach w celu znalezienia optymalnego przepływu i trasy o minimalnych kosztach. Robiąc to, przeglądają każdy z różnych wariantów tego, które połączenia są otwarte, zamknięte lub przeciążone z powodu osiągnięcia limitu przepustowości.
Oblicz całość? Albo jego części?
Przed Kyngiem informatycy mieli tendencję do wybierania pomiędzy dwiema kluczowymi strategiami rozwiązania tego problemu. Jedno z nich zostało zamodelowane na sieci kolejowej i polegało na obliczeniu całego odcinka sieci ze zmodyfikowanym przepływem ruchu w każdej iteracji. Druga strategia – inspirowana przepływami mocy w sieci elektroenergetycznej – obliczała całą sieć w każdej iteracji, ale wykorzystywała statystyczne wartości średnie dla zmodyfikowanego przepływu w każdym odcinku sieci, aby przyspieszyć obliczenia.
Zespół Kynga połączył teraz zalety tych dwóch strategii, aby stworzyć zupełnie nowe, połączone podejście. „Nasze podejście opiera się na wielu małych, wydajnych i tanich etapach obliczeniowych, które razem wzięte są znacznie szybsze niż kilka dużych” – mówi Maximilian Probst Gutenberg, wykładowca i członek grupy Kynga, który odegrał kluczową rolę rolę w opracowywaniu algorytmów czasu prawie liniowego.
Krótkie spojrzenie na historię tej dyscypliny nadaje dodatkowy wymiar znaczeniu przełomu Kynga: problemy przepływu w sieciach były jednymi z pierwszych, które zostały systematycznie rozwiązane za pomocą algorytmów w latach pięćdziesiątych XX wieku, a algorytmy przepływu odegrały ważną rolę w ustaleniu informatyka teoretyczna jako odrębna dziedzina badań.
Z tego okresu wywodzi się także dobrze znany algorytm opracowany przez matematyków Lestera R. Forda Jr. i Delberta R. Fulkersona. Ich algorytm skutecznie rozwiązuje problem maksymalnego przepływu, który ma na celu określenie, w jaki sposób przewieźć jak największą liczbę towarów siecią, nie przekraczając przepustowości poszczególnych tras.
Szybko i wszechstronnie
Postępy te pokazały badaczom, że problem maksymalnego przepływu, problem minimalnych kosztów (problem przeładunku lub transportu) i wiele innych ważnych problemów z przepływem w sieci można postrzegać jako szczególne przypadki ogólnego problemu przepływu przy minimalnych kosztach. Przed badaniami Kynga większość algorytmów była w stanie skutecznie rozwiązać tylko jeden z tych problemów, chociaż nawet tego nie można było zrobić szczególnie szybko ani nie można było ich rozszerzyć na szerszy problem przepływu przy minimalnych kosztach.
To samo dotyczy pionierskich algorytmów przepływu z lat 70. XX wieku, za które teoretyczni informatycy John Edward Hopcroft, Richard Manning Karp i Robert Endre Tarjan otrzymali Nagrodę Turinga, uważaną za „Nagrodę Nobla” w informatyce. Karp otrzymał go w 1985 roku; Hopcroft i Tarjan wygrali swoje w 1986 roku.
Zmiana perspektywy z kolei na energię elektryczną
Dopiero w 2004 roku matematycy i informatycy Daniel Spielman i Shang-Hua Teng – a później Samuel Daitch – zdołali napisać algorytmy, które zapewniły również szybkie i wydajne rozwiązanie problemu przepływu przy minimalnych kosztach. To właśnie ta grupa skupiła się na przepływach mocy w sieci elektroenergetycznej. Ich przejście z kolei na energię elektryczną doprowadziło do kluczowego matematycznego rozróżnienia: jeśli pociąg zostanie przekierowany w sieci kolejowej z powodu nieczynności danej linii, następną najlepszą trasę zgodnie z rozkładem jazdy może już zajmować inny pociąg.
W sieci elektroenergetycznej możliwe jest częściowe przekierowanie elektronów tworzących przepływ mocy do połączenia sieciowego, przez które przepływa już inny prąd. Tym samym, w odróżnieniu od pociągów, prąd elektryczny można, z matematycznego punktu widzenia, „częściowo” przenieść na nowe połączenie.
To częściowe przekierowanie umożliwiło Spielmanowi i jego współpracownikom znacznie szybsze obliczanie takich zmian tras, a jednocześnie ponowne obliczanie całej sieci po każdej zmianie. „Odrzuciliśmy podejście Spielmana zakładające stworzenie najpotężniejszych algorytmów, jakie mogliśmy dla całej sieci” – mówi Kyng. „Zamiast tego zastosowaliśmy jego koncepcję częściowego obliczania trasy do wcześniejszych podejść Hopcrofta i Karpa”. Obliczenie tras częściowych w każdej iteracji odegrało główną rolę w przyspieszeniu obliczeń całkowitego przepływu.
Punkt zwrotny w zasadach teoretycznych
Duża część postępu badaczy ETH Zurich sprowadza się do decyzji o rozszerzeniu swojej pracy poza opracowanie nowych algorytmów. Zespół wykorzystuje także i projektuje nowe narzędzia matematyczne, które jeszcze bardziej przyspieszają algorytmy.
W szczególności opracowali nową strukturę danych do organizowania danych sieciowych; umożliwia to niezwykle szybką identyfikację wszelkich zmian w połączeniu sieciowym; to z kolei sprawia, że rozwiązanie algorytmiczne jest tak zdumiewająco szybkie. Przy tak dużej liczbie aplikacji obsługujących algorytmy działające w czasie niemal liniowym i narzędzia takie jak nowa struktura danych ogólna spirala innowacji może wkrótce kręcić się znacznie szybciej niż dotychczas.
Jednak stworzenie podstaw do rozwiązywania bardzo dużych problemów, których wcześniej nie można było efektywnie obliczyć, to tylko jedna z korzyści płynących z tych znacznie szybszych algorytmów przepływu – ponieważ zmieniają one przede wszystkim sposób, w jaki komputery obliczają złożone zadania. „W ciągu ostatniej dekady nastąpiła rewolucja w teoretycznych podstawach uzyskiwania możliwych do udowodnienia szybkich algorytmów dla podstawowych problemów informatyki teoretycznej.” – pisze międzynarodowa grupa badaczy z Uniwersytet Kalifornijski w Berkeleyw skład której wchodzą Rasmus Kyng i Deeksha Adil, badaczka w Instytucie Studiów Teoretycznych na ETH Zurich.
Odniesienie: „Prawie liniowe algorytmy czasu dla wykresów przyrostowych: wykrywanie cykli, SCC, st najkrótsza ścieżka i przepływ o minimalnym koszcie” Li Chen, Rasmus Kyng, Yang P. Liu, Simon Meierhans i Maximilian Probst Gutenberg, 11 czerwca 2024 r., STOC 2024: Materiały z 56. dorocznego sympozjum ACM na temat teorii informatyki.
DOI: 10.1145/3618260.3649745
