Dzięki nowemu, superszybkiemu algorytmowi spowolnienia sieci mogą wkrótce stać się przeszłością.
Przełom ten oferuje znacznie szybsze rozwiązanie problemu, który dręczył informatyków od lat 50. XX wieku: maksymalnego przepływu, czyli sposobu osiągnięcia najszybszego przepływu informacji w systemie o ograniczonej przepustowości.
Poprzednie algorytmy maksymalnego przepływu dokonywały stałych i przyrostowych postępów, ale nadal dłużej zajmowało im znalezienie optymalnego przepływu niż przetworzenie danych sieciowych. Jednak nowe badania, zaprezentowane 11 czerwca na Materiały z 56. dorocznego sympozjum ACM na temat teorii informatykiopisuje algorytm, który może rozwiązać problem w czasie mniej więcej tak szybkim, jak zapisanie szczegółów sieci.
Problem maksymalnego przepływu jest kamieniem węgielnym nauki algorytmicznej i zainspirował wiele najważniejszych postępów w tej dziedzinie. Pierwsza próba jego rozwiązania miała miejsce w 1956 r., kiedy matematycy Delbert Fulkerson i Lester Ford zaproponowany to, co nazwali „chciwym rozwiązaniem” problemu.
Algorytmy zachłanne działają w ten sposób, że w każdym punkcie drzewa decyzyjnego podejmują najkorzystniejsze decyzje, wybierając najlepszą ścieżkę przed sobą, bez względu na to, jakie trasy może ona zablokować w przyszłości.
Wyobraź sobie problem optymalizacja ruchu przechodzącego z punktu A do punktu B wzdłuż wielu możliwych ścieżek, jedna trasa składa się z pierwszego segmentu, który jest sześciopasmową autostradą, a ostatni z trzypasmowej drogi. Aby to rozwiązać, zachłanny algorytm uruchomi jak najwięcej ruchu (trzy pasy samochodów) wzdłuż trasy, dostosowując jej przepustowość i powtarzając te same kroki dla innych tras, aż każda możliwa ścieżka będzie w pełni przepustowa.
Algorytm Fulkersona i Forda okazał się wystarczająco skuteczny, ale często nie dawał najlepszego możliwego przepływu: jeśli inne trasy zostały odcięte i pojawiły się suboptymalne korki, niech tak będzie. Następne 70 lat wkładu w problem miało na celu udoskonalenie tego aspektu rozwiązania, wygładzając niepotrzebne spowolnienia poprzez wbudowanie lepszego podejmowania decyzji w algorytm.
Zmiany te spowodowały, że czas wykonania algorytmu zmienił się z wielokrotności m^2 (gdzie m jest liczbą węzłów w sieci) na wielokrotność m^1,33 w 2004 r., lecz wkrótce potem postęp prac został zahamowany.
Aby osiągnąć przełom, badacze połączyli dwa wcześniejsze podejścia: oryginalne rozwiązanie traktujące sieci jako ruch; i późniejsze, które zamiast tego postrzegało je jako sieć elektryczną. W przeciwieństwie do samochodów lub pociągów, przepływ elektronów można częściowo przekierować, aby dołączyć do prądu wzdłuż innej trasy, co umożliwia informatykom zmapowanie najlepszego przepływu w całej sieci przed zastosowaniem podejścia opartego na ruchu segment po segmencie.
Połączenie tych dwóch podejść zaowocowało hybrydowym algorytmem, który był „absurdalnie szybki”, Daniel A. Spielmanprofesor matematyki stosowanej i informatyki na Uniwersytecie Yale’a, który nadzorował program doktorancki jednego z badaczy, powiedział w oświadczeniu. Spielman porównał nowe rozwiązanie do poprzednich, mówiąc, że jest jak „porsche wyprzedzające powozy konne”.
Po udoskonaleniu nowy algorytm będzie mógł zostać wykorzystany w wielu zastosowaniach, m.in. w przetwarzaniu danych internetowych, ustalaniu rozkładu lotów i zwiększaniu efektywności rynków – twierdzą badacze.
