Przybliżone obliczenia usprawnią internet?

Precyzyjne obliczenia nie zawsze są możliwe. Czasem, kiedy liczy się czas, trzeba obliczyć coś w przybliżeniu. Służą do tego algorytmy aproksymacyjne, wykorzystywane m.in. w wielu usługach internetowych

Dr hab. Piotr Sankowski z Wydziału Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego przez cztery najbliższe lata będzie kierował międzynarodowym projektem badawczym poświęconym rozwojowi algorytmów aproksymacyjnych i ich praktycznym zastosowaniem. Umożliwi to przyznany mu właśnie grant Europejskiej Rady ds. Badań. Jak powiedział PAP, projekt będzie prowadzony w ścisłej współpracy z uniwersytetem Sapienza w Rzymie.

Celem prac jest m.in. stworzenie biblioteki algorytmów aproksymacyjnych, które będą mogły w przyszłości zostać wykorzystane przez twórców oprogramowania komputerowego.

"Algorytmy aproksymacyjne pozwalają znajdować przybliżone rozwiązania dla problemów optymalizacyjnych. Stosuje się je do problemów trudnych, dla których nie istnieją szybkie algorytmy znajdujące rozwiązania dokładne. Jednym z takich problemów jest problem komiwojażera, w którym naszym celem jest znalezienie najkrótszej trasy przechodzącej przez zadany zbiór miast" - tłumaczył naukowiec.

Problemy optymalizacyjne (jak ten, przed którym stoi przykładowy komiwojażer) to takie, w których nie tyle chodzi o znalezienie jedynego poprawnego rozwiązania, ile raczej o wybranie spośród możliwych rozwiązań takiego, które najlepiej spełnia podane kryteria. Komiwojażer może przebyć swoją drogę pomiędzy miastami na wiele sposobów, chodzi o to, aby wskazać mu najkrótszą.

Jeśli miast jest tylko kilka (np. Kraków, Poznań, Warszawa i Wrocław) to obliczenie optymalnej trasy dla handlarza wyruszającego np. z Warszawy jest stosunkowo łatwe. "W takim przypadku najkrótsza trasa ma długość 106. km i biegnie: Warszawa-Kraków-Wrocław-Poznań-Warszawa" - mówił Sankowski.

Problem komplikuje się wraz z wzrostem liczby miast do objechania. Jeśli byłoby ich np. kilka tysięcy to obliczenie tej najkrótszej trasy trwałoby bardzo długo. Dlatego bardziej opłacalne może się okazać zastosowanie takich rozwiązań, które nie pozwolą, co prawda obliczyć tej jednej najkrótszej trasy, ale podadzą kilka tras nieco dłuższych, a za to umożliwią komiwojażerowi szybki wyjazd i dostarczenie towaru na czas.

Podobnie jest z przetwarzaniem danych pobieranych z internetu. Dopóki nie ma szybkiego sposobu na to, by z ich masy wybrać te, które są najbardziej istotne, warto zastosować podobne przybliżenie jak w przypadku podróży komiwojażera. Błąd nie będzie duży, a można zaoszczędzić cenny czas.

"Problemem, na którym chcemy przetestować użyteczność naszej biblioteki, jest cache'owanie informacji w serwisach WWW. Pozwala ono na dostarczanie treści szybciej dzięki częściowemu jej przechowaniu bliżej użytkownika. Mamy jednak nadzieję, że nasza biblioteka będzie na tyle uniwersalna, że zawarte w niej algorytmy znajdą szersze zastosowania" - wyjaśnił Sankowski.

Cache'owanie informacji polega np. na tym, że przeglądarka internetowa zapisuje na dysku internauty część danych pobranych z odwiedzonych niedawno stron. Jeśli ten internauta będzie chciał wrócić na te strony, to będzie mógł to zrobić szybciej, bo nie będzie konieczne ponowne pobieranie tych danych.

"To jest w pewnym sensie najprostszym przypadkiem. Informacje z serwisów WWW przechowywane są także na innych komputerach np. serwerze, który leży blisko ostatecznego użytkownika. W takim wypadku użytkownik nie musi kontaktować się z oryginalnym dostarczycielem informacji, ale z serwerem, który jest dużo bliżej. Ten problem ma wiele aspektów, np. gdzie umieścić cache'ujący serwer, co on ma przechowywać, a także w jakiej postaci" - dodał informatyk.

Program obsługujący pamięć cache musi nie tylko "zapamiętać" ostatnio odwiedzone serwisy WWW, ale też przewidzieć, jakie inne strony może chcieć odwiedzić internauta w przyszłości - mogą to być np. strony, do których prowadzą linki z odwiedzonych serwisów. Aby przeprowadzić taką operację, potrzeba masy obliczeń. W tym przypadku bardziej liczy się czas niż precyzja wyniku. Dlatego usługi internetowe tak często bazują na algorytmach aproksymacyjnych. Jednak, jak zaznaczył Sankowski, wiele jest w tej dziedzinie jeszcze do zrobienia.

"W ostatnich latach bardzo owocne były badania nad stworzeniem algorytmów aproksymacyjnych, które działałyby dobrze w przypadku, gdy dane są losowe. Aktualnie próbuje się stworzyć dynamiczne algorytmy aproksymacyjne, czyli takie, które działają bardzo szybko, gdy dane wejściowe ulegają małym zmianom. Obydwie te problematyki są także zawarte w naszym projekcie. Nasz cel, w pewnym sensie, jest bardzo prosty i jest nim stworzenie algorytmów, które są w stanie obliczyć jak najlepsze rozwiązania. Brzmi to trywialnie, ale nawet dla najprostszych problemów aproksymacyjnych wiemy, że jesteśmy jeszcze bardzo daleko od ich pełnego zrozumienia i stworzenia tak dobrych, jak to tylko możliwe rozwiązań" - podkreślił.