Problem, którym zajmują się naukowcy, może wydawać się na pierwszy rzut oka podobny do działania nawigacji samochodowej. W praktyce jest jednak znacznie bardziej złożony. Chodzi o tzw. APSP (All-Pairs Shortest Paths), czyli wyznaczenie najkrótszych ścieżek pomiędzy każdą możliwą parą punktów w sieci. Taką sieć można przedstawić jako graf składający się z wierzchołków i łączących je krawędzi. Wierzchołkami mogą być na przykład miasta, komputery, stacje kolejowe, neurony czy elementy sieci biologicznej.
Czytaj też: Alternatywny diament wprost z laboratorium. Nigdy przedtem nie udało się uzyskać takiego materiału
W przypadku niewielkiej sieci problem można rozwiązać stosunkowo łatwo. Sytuacja komplikuje się, gdy liczba punktów rośnie do ogromnych rozmiarów. Dokładne obliczenie wszystkich odległości wymaga bowiem bardzo dużej mocy obliczeniowej. W gęstych grafach klasyczne rozwiązania mogą wymagać czasu rosnącego w przybliżeniu proporcjonalnie do sześcianu liczby wierzchołków. Oznacza to, że podwojenie rozmiaru problemu może prowadzić do około ośmiokrotnego wzrostu ilości obliczeń.
Dlatego informatycy od lat rozwijają algorytmy przybliżone. Nie muszą one podawać idealnie dokładnej odpowiedzi, ale oferują matematyczną gwarancję, iż wynik nie będzie zbyt odległy od rzeczywistego. Takie podejście pozwala znacząco ograniczyć czas potrzebny na wykonanie obliczeń.
Jednym z ważnych punktów odniesienia jest algorytm opracowany w 1996 roku przez Dor, Halperina i Zwicka. Zapewnia on tzw. przybliżenie 2, czyli gwarantuje, że oszacowana odległość nie będzie większa niż dwukrotność rzeczywistej najkrótszej ścieżki. Jeżeli prawdziwa odległość między dwoma punktami wynosi 10 jednostek, algorytm może wskazać maksymalnie 20. Metoda wykorzystuje stosunkowo niewielki zbiór reprezentatywnych wierzchołków, które można potraktować jak punkty orientacyjne. W przypadku odległych od siebie punktów takie podejście działa dobrze. Istniał jednak problem z parami wierzchołków znajdujących się blisko siebie.
Nowe rozwiązanie zaproponowane przez Guptę zmienia sposób wybierania punktów odniesienia. Zamiast jednej warstwy próbkowania algorytm wykorzystuje kilka poziomów, odpowiadających różnym skalom struktury grafu. Dzięki temu rośnie prawdopodobieństwo, że także dla krótkiej ścieżki znajdzie się odpowiedni punkt, który pozwoli stworzyć dokładne przybliżenie.
Czytaj też: MIT zrobiło komputer, który pamięta dzięki odkształcaniu materiału
W efekcie udało się rozszerzyć zakres, w którym obowiązuje gwarancja 2-przybliżenia. Co istotne, nowa metoda zachowuje co najmniej tę samą ogólną złożoność czasową. Nie chodzi więc o uzyskanie dokładniejszych wyników za cenę znacznie większej liczby obliczeń, lecz o skuteczniejsze wykorzystanie informacji zawartych w strukturze sieci. Warto mieć na uwadze, iż praca Gupty stanowi przede wszystkim osiągnięcie z zakresu teorii algorytmów, a nie gotową technologię, która z dnia na dzień zmieni działanie aplikacji nawigacyjnych.
Z drugiej strony, to zdecydowanie więcej niż tylko teoria. Algorytmy obliczające odległości w grafach znajdują zastosowanie w analizie sieci komunikacyjnych, transporcie, biologii, systemach społecznościowych czy rozwiązaniach wykorzystujących sztuczną inteligencję. W wielu takich przypadkach możliwość szybkiego uzyskania wiarygodnego przybliżenia jest bardziej użyteczna niż oczekiwanie na idealnie dokładny wynik.
