Manoj Gupta przełamuje barierę z 1996 roku w algorytmach tras

Manoj Gupta z Indian Institute of Technology Gandhinagar opracował algorytm, który pozwala dokładniej szacować odległości w ogromnych sieciach, i to bez wydłużania czasu obliczeń. Rozwiązanie przełamuje ograniczenie, które od 1996 roku blokowało postęp w tej dziedzinie informatyki.

Problem APSP i stara bariera

Kluczem okazała się metoda dająca dokładniejsze przybliżenia najkrótszych ścieżek między punktami położonymi blisko siebie. Z takim zadaniem komputery mierzą się codziennie: korzystają z niego aplikacje nawigacyjne, systemy transportowe i infrastruktura internetowa. Ssprawa komplikuje się, gdy trzeba wyznaczyć odległości między każdą parą punktów w dużej sieci. W informatyce nazywa się to problemem APSP (All-Pairs Shortest Paths). Siecią mogą być miasta, komputery, stacje kolejowe, a nawet neurony.

Dokładne policzenie wszystkich tras w gęstej sieci wymaga ogromnych zasobów, dlatego badacze szukają metod przybliżonych. W 1996 roku Dor, Halperin i Zwick pokazali algorytm gwarantujący, że oszacowanie nie przekroczy dwukrotności rzeczywistej odległości (przybliżenie 2-krotne). Gwarancja działała jednak głównie dla punktów odległych od siebie. Przy krótkich połączeniach błędy bywały większe: zamiast dwóch przeskoków algorytm mógł wskazać pięć, co wykraczało poza dozwolony margines.

Próbkowanie wieloskalowe

Gupta zmienił sposób wyboru punktów używanych do szacowania. Wcześniej opierano się na niewielkim zbiorze reprezentatywnych wierzchołków. Nowy algorytm stosuje próbkowanie wieloskalowe, czyli analizuje strukturę sieci na kilku poziomach zamiast na jednym zestawie punktów. Dzięki temu uwzględnia krótsze połączenia, które wcześniej mogły umknąć.

Najważniejsze jest to, że wyższa dokładność nie zwiększa ogólnej złożoności obliczeniowej, więc wyniki są bardziej wiarygodne bez dodatkowego kosztu czasowego.

Osiągnięcie może się przydać wszędzie tam, gdzie analizuje się rozbudowane sieci: w telekomunikacji, transporcie, mediach społecznościowych i systemach sztucznej inteligencji. Szybkie, wiarygodne szacowanie odległości ułatwia tam analizę zależności i optymalizację działania całych systemów.