Kluczem do sukcesu okazała się metoda pozwalająca uzyskiwać dokładniejsze przybliżenia najkrótszych ścieżek między punktami położonymi blisko siebie, nie zwiększając przy tym czasu obliczeń. A jest to przecież zadanie, z jakim komputery mierzą się każdego dnia. Korzystają z niego między innymi aplikacje nawigacyjne, systemy transportowe i infrastruktura internetowa. Problem staje się jednak znacznie bardziej skomplikowany, gdy trzeba obliczyć odległości między każdą możliwą parą punktów w ogromnej sieci.
Czytaj też: Zegarek jak kropla deszczu? Ten skomplikowany mechanizm używa prostej sztuczki
W informatyce zagadnienie to określa się mianem APSP (All-Pairs Shortest Paths), czyli problemu najkrótszych ścieżek między wszystkimi parami wierzchołków. Sieć można w tym przypadku rozumieć jako zbiór punktów połączonych ze sobą relacjami. Mogą one reprezentować miasta, komputery, stacje kolejowe, a nawet neurony czy elementy struktur biologicznych.
Dokładne wyznaczenie wszystkich najkrótszych tras w dużej i gęsto połączonej sieci wymaga ogromnych zasobów obliczeniowych. Dlatego naukowcy od dawna poszukują metod, które pozwalają uzyskać wiarygodne wyniki bez konieczności analizowania każdej możliwej ścieżki. Istotny postęp nastąpił właśnie w 1996 roku. Badacze Dor, Halperin i Zwick opracowali wówczas algorytm pozwalający szacować odległości z gwarancją, że wynik nie będzie większy niż dwukrotność rzeczywistej najkrótszej drogi. Takie rozwiązanie nosi nazwę przybliżenia 2-krotnego.
Metoda ta miała jednak istotną słabość. Gwarancja dokładności sprawdzała się przede wszystkim w przypadku punktów znacznie oddalonych od siebie. Przy krótkich połączeniach algorytm mógł popełniać większe błędy. Przykładowo, jeśli rzeczywista trasa obejmowała dwa połączenia, oszacowanie mogło wskazać pięć. To oznaczało przekroczenie dopuszczalnego dwukrotnego marginesu.
Rozwiązanie zaproponowane przez Guptę polega na udoskonaleniu sposobu wybierania punktów wykorzystywanych do szacowania odległości. Wcześniejsze podejście opierało się na stosunkowo niewielkim zbiorze reprezentatywnych wierzchołków, które pomagały wyznaczać przybliżone trasy. Nowy algorytm wykorzystuje natomiast strategię próbkowania wieloskalowego. Oznacza to analizowanie struktury sieci na kilku różnych poziomach, zamiast polegania na jednym zestawie wybranych punktów.
Dzięki temu metoda potrafi uwzględniać krótsze połączenia, które wcześniej mogły zostać pominięte. Najważniejsze jest jednak to, że poprawa dokładności nie wymaga zwiększenia ogólnej złożoności obliczeniowej algorytmu. Innymi słowy, można uzyskać bardziej wiarygodne wyniki bez ponoszenia dodatkowego kosztu w postaci wydłużonego czasu działania.
Przełom Gupty może mieć znaczenie dla wielu dziedzin wykorzystujących analizę rozbudowanych sieci. Chodzi między innymi o telekomunikację, transport, media społecznościowe czy systemy sztucznej inteligencji. W każdym z tych obszarów szybkie i wiarygodne szacowanie odległości między elementami sieci może ułatwiać analizę zależności i optymalizację działania całych systemów.
Źródło: IEEE Explore
