Potyczki algorytmiczne, czyli Alicja i Bogdan w nowych sytuacjach. Alicja i Bogdan na wczasach | Politechnika Gdańska

Zagadka 1

Alicja jest początkującą narciarką, a Bogdan doradcą finansowym. Oboje wybrali się na wczasy do Zakopanego na ponad 2 miesiące. Pierwszego dnia Alicja musi rozstrzygnąć: czy kupić narty za 1500 zł, czy też wypożyczać je codziennie za 50 zł (cena obejmuje kaucję za uszkodzenie nart). Co Bogdan powinien doradzić Alicji?

Rozwiązanie
Ponieważ istnieje możliwość, że Alicja połamie narty w pierwszych dniach pobytu, nie powinna ich kupować na początku. Ale nie powinna też kupować ich do 30. dnia pobytu włącznie. W 31. dniu powinna udać się do sklepu i jeździć już na własnych nartach do chwili wypadku. Po ewentualnym złamaniu nart winna przerzucić się na wypożyczanie itd. Przy takim podejściu Alicja w żadnym razie nie wyda na narty dwukrotnie więcej niż to, co i tak musiałaby wydać w optymalnym układzie. A groziłoby to jej, gdyby kupiła narty w pierwszych dniach lub pod koniec pierwszego miesiąca pobytu w Zakopanem.
Uwaga 1.
Oczywiście kwoty złotowe występujące w zagadce można zmienić. Ważne, że jeżeli narty kosztują b, a wynajęcie kosztuje c, to dokładnie w dniu b/c + 1 należy je kupić.
Uwaga 2.
Jest to problem z dziedziny tzw. algorytmów online, tj. takich, które nie znają danych wejściowych od początku w całości, lecz otrzymują je w partiach. Po każdej takiej turze algorytm online musi podać częściową odpowiedź, której nie może zmienić. Sytuację taką można interpretować jako grę algorytmu z przyrodą.

Zagadka 2

Bogdan (który jest krótkowidzem) pewnego upalnego dnia udał się na nieznaną mu plażę. Pozostawił swoje ubranie przy brzegu, zdjął okulary i poszedł się kąpać. Pływał ponad godzinę i fale zniosły go daleko od miejsca, w którym wszedł do wody. Jak powinien postąpić, gdy wyjdzie na brzeg i nie znajdzie swojego ubrania?

Rozwiązanie
Oczywiście gdyby Bogdan posiadał monetę, to rzut monetą mógłby go pokierować prosto do celu. Ale w najgorszym przypadku skutki tak randomizowanego algorytmu probabilistycznego okazałyby się opłakane. Dlatego Bogdan powinien rozpocząć wędrówkę po brzegu, cały czas bacznie obserwując plażę. Najpierw powinien pójść np. 100 kroków w lewo. Gdy nie znajdzie koca, powinien wrócić 100 kroków, następnie przejść 100 kroków w prawo. W przypadku fiaska, winien wrócić do punktu startowego i ponownie pójść w lewo, ale tym razem 200 kroków i tak dalej, za każdym razem dwukrotnie zwiększając obszar poszukiwań (rys. 1).
Uwaga 3.
Algorytm probabilistyczny to algorytm, który do swojego działania używa losowości. W praktyce oznacza to, że implementacja takiego algorytmu korzysta przy obliczeniach z generatora liczb losowych.
Uwaga 4.
Gdyby Bogdan posiadał cudowną monetę, która wskazywałaby mu właściwy kierunek, to mógłby trafić prosto do celu. Skoro taka moneta nie istnieje, to musimy liczyć się z pewnym narzutem przebytej drogi. Jaki to narzut? Załóżmy, że koc znajduje się w odległości x jednostek długości. Wówczas w najgorszym przypadku Bogdan przejdzie co najwyżej 9x jednostek odległości, czyli jego droga będzie wprost proporcjonalna do x.

Marek Kubale
kubale@eti.pg.edu.pl