Algorytmy aproksymacyjne służą do znajdowania przybliżonych rozwiązań problemów optymalizacyjnych – czyli takich, w których poszukujemy najmniejszej lub największej wartości pewnego parametru. Różnią się one od zwykle wykorzystywanych w tym celu algorytmów heurystycznych powiązaniem z informacją o koszcie uzyskanego rozwiązania w porównaniu do rozwiązania optymalnego. Stosuje się je zwykle dla problemów trudnych pod względem obliczeniowym, dla których nie są znane algorytmy zwracające dokładne wyniki.

Właśnie tą kwestią zajmować się ma dr hab. Piotr Sankowski z MIMUW; został on laureatem trzeciej edycji konkursu ERC Starting Grant. Finansowanie zapewnione przez Europejską Radę ds. Badań ma posłużyć m.in. stworzeniu software'owej biblioteki, która będzie mogła być wykorzystywana przez twórców oprogramowania do problemów przypominających znany problem komiwojażera. Projekt badawczy „PAAL – Practical Approximation Algorithms” rozwijany jest we współpracy z Uniwersytetem Sapienza w Rzymie.

Znany z literatury problem komiwojażera dotyczy znalezienia najkrótszej trasy przechodzącej przez zadany zbiór miast. Jak tłumaczy dr hab. 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”.

Podobny problem dotyczy dostarczania treści w Internecie. Nie istnieje algorytm pozwalający wyznaczyć najlepszą trasę dla pakietów danych od serwera do klienta, można jednak, wyliczając odpowiednie przybliżenia, znacznie zoptymalizować ten proces. Na początku tworzona przez polskich i włoskich badaczy biblioteka znaleźć ma zastosowanie przy cache'owaniu informacji w serwisach WWW, służącemu szybszemu dostarczaniu treści, dzięki przechowywaniu ich bliżej użytkownika. Informatyk ma jednak nadzieję, że opracowywana biblioteka okaże się bardziej uniwersalna – problem cache'owania jest tu najprostszym wypadkiem.

„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” – podsumował dr Sankowski.

Według uczonego, w ostatnich latach doszło do dużego postępu w tej dziedzinie – algorytmy aproksymacyjne dobrze już sobie radzą z losowymi danymi. Powstają też pierwsze dynamiczne algorytmy aproksymacyjne, reagujące na małe zmiany danych wejściowych. Mimo tych osiągnięć, do pełnego zrozumienia problemów aproksymacyjnych i stworzenia optymalnych rozwiązań wciąż jest jeszcze bardzo daleko.

Źródło: polskatimes.pl