Niektóre problemy w informatyce nie mają jednej dobrej odpowiedzi. Prawidłowych wyników może być tak wiele, że znalezienie jednego, najlepszego, poprzez przeszukanie wszystkich możliwych jest zbyt kosztowne. W takich sytuacjach często wystarczają wyniki zbliżone do optymalnego.

Do rozwiązania tych problemów Jarosław Byrka używa tzw. zrandomizowanych algorytmów aproksymacyjnych. Dzięki nim możliwe odpowiedzi są przeszukiwane w sposób losowy i dość szybko można znaleźć zadowalający, choć niekoniecznie najlepszy wynik. Laureatowi Nagrody im. Lipskiego udało się udoskonalić niektóre sposoby losowego przeszukiwania odpowiedzi i poprawić jakość uzyskiwanych wyników.

Jednym z zagadnień, którego rozwiązania udoskonalił młody badacz jest problem tzw. drzewa Steinera. "Mamy dany graf i koszt jego krawędzi. Problem polega na tym, żeby połączyć wybrane wierzchołki najtaniej jak się da. Jedną z trudności jest jednak to, że kupno jednej krawędzi może skutkować zmianą przydatności innych krawędzi" - objaśnia nagrodzony.

Na przykład mamy serwery i sieć połączeń między nimi. Wykorzystanie każdego z połączeń związane jest z jakimś kosztem, a użycie konkretnego połączenia wpływa na koszt optymalnego uzupełnienia sieci pozostałymi połączeniami.

Rozwiązanie tego problemu może znaleźć zastosowanie przemysłowe. "To ważny problem z punktu widzenia działania sieci telekomunikacyjnych. Jeśli chcemy zapewnić sobie możliwość łączenia lokalizacji w internecie, konieczne jest rezerwowanie przepustowości na łączach, co jest usługą płatną. Dlatego ważna jest minimalizacja kosztu rezerwacji. Zależy nam, żeby pewne protokoły podejmowały decyzje szybko, bo czas działania, a nie optymalność rozwiązania jest tutaj kluczowa" - podkreśla informatyk.

Innym zagadnieniem, nad którym pracuje Byrka jest problem lokalizacji. "Mamy pewien zbiór klientów, którym chcemy zapewnić świadczenie (np. dostarczyć prąd) konstruując pewne obiekty (np. elektrownie). Dysponujemy zbiorem lokalizacji (miejsc, w których możemy zbudować elektrownie) wraz z ich kosztem (ceną za wybudowania ich właśnie w tych miejscach). Chodzi o to, żeby wybrać podzbiór lokalizacji i przypisać każdego z klientów do poszczególnych obiektów tak, żeby zminimalizować łączny koszt tego działania" - wyjaśnia Byrka.

Informatyk obrazuje problem: "Dwa banki miały jakąś liczbę biur i iluś klientów. W pewnej chwili postanowiły połączyć się w jeden bank. Nowy bank po połączeniu ma tyle samo klientów co dwa banki, ale prawdopodobnie może mieć o połowę mniej biur. Musi wybrać, które z nich można zlikwidować. Usuwanie niepotrzebnych biur powinno przebiegać tak, żeby klienci nie mieli zbyt daleko do banku. Chcielibyśmy zminimalizować społeczny koszt tego rozwiązania."

"Podobne algorytmy znajdują zastosowanie przy produkcji elementów elektronicznych, gdzie na układzie scalonym umieszcza się pewne części, które muszą być ze sobą połączone. Czasem elementów jest tak dużo, że próba znalezienia najlepszego rozwiązania skazana byłaby na porażkę. I wtedy właśnie przydają się algorytmy aproksymacyjne" - dodaje naukowiec.

"Istotą algorytmów aproksymacyjnych jest to, że działają szybko, ale są niedokładne" - zaznacza informatyk. Ale jemu udało się zmniejszyć niedokładność tych rozwiązań i zbliżyć je do optimum. Na razie jeszcze nikomu nie udało się poprawić jego wyniku.

Laureat nagrody im. Witolda Lipskiego zaznacza, że bada tylko najprostsze wersje problemów. "Ich rozwiązania nie są bezpośrednio stosowane, ale prowadzą do głębszego zrozumienia problemu i do konstrukcji odpowiednich narzędzi przemysłowych" - wyjaśnia.

Innym problemem, nad którym pracuje Byrka, jest stworzenie programu do ilustrowania historii ewolucji gatunków. Złożone dane, np. genetyczne, mogłyby być zobrazowane za pomocą drzewa. W budowie tego drzewa znalazłyby odbicie zależności ewolucyjne między poszczególnymi organizmami. Młody naukowiec interesuje się też teorią gier i tym, jak mogą się zmieniać strategie graczy. Problem ten jest ważny z punktu widzenia ekonomii.

PAP - Nauka w Polsce, Ludwika Tomala

agt/