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

Zagadka 1

Alicja udała się do sklepu obuwniczego, by nabyć buty w swoim rozmiarze. Zobaczyła regał z 49 parami butów ułożonymi rosnąco według długości i szerokości od najmniejszej pary w lewym górnym rogu do największej w prawym dolnym rogu. Ponieważ buty są bardzo drogie, ekspedient pozwala na przymierzanie obuwia jedynie najmniejszą możliwą liczbę razy. Ile wynosi ta liczba, skoro buty są ułożone w kwadracie 7 × 7?

Rozwiązanie
Alicja winna przymierzyć parę stojącą w środku regału, czyli z czwartej półki i czwartej kolumny. Jeżeli buty te nie pasują, może być to spowodowane tym, że są za ciasne lub zbyt obszerne i/lub za krótkie bądź zbyt długie. Mamy zatem 8 możliwości, jak na rys. 2. Na przykład gdyby buty okazały się zbyt wąskie, to następnym wyborem Alicji winny być buty z tej samej półki leżące na miejscu przedostatnim. Gdy i te okażą się za wąskie, to należy sięgnąć po buty leżące na ostatniej pozycji. W przeciwnym razie należy cofnąć się o 1 pozycję itd. Widzimy, że w najgorszym przypadku potrzebne będą 2 przymiarki próbne, by podjąć właściwą decyzję. A ogólnie, stosując metodę połówkową wobec regału
n × n, dokonamy co najwyżej log₂n prób.

Zagadka 2

Alicja szczęśliwie wybrała buty i poszła do kasy, by za nie zapłacić. Odbierając resztę, poprosiła kasjerkę, by ta wypłaciła jej jak najmniejszą liczbę nominałów, bo „nie lubi nosić przy sobie drobnych”. Jak optymalnie zrealizować taką wypłatę?

Rozwiązanie
Na początek dobra wiadomość: pani w kasie ma dostateczną liczbę monet i banknotów każdego rodzaju, zaś polski system monetarny jest kanoniczny, co oznacza, że algorytm zachłanny rozwiązuje nasz problem w sposób optymalny. Algorytm zachłanny to taki, który działa iteracyjnie i na każdym etapie stara się postąpić w sposób lokalnie najlepszy. Suma tych rozwiązań częściowych daje rozwiązanie często globalnie najlepsze. W naszym przypadku, poczynając od najwyższych nominałów, kasjerka zmniejsza sukcesywnie należną kwotę dopóty, dopóki nie osiągnie ona wartości zero. Zaletą tego podejścia jest prostota i szybkość algorytmu. Załóżmy na przykład, że do wypłaty jest kwota 14,06 zł. Kwotę tę dzielimy na 10 zł + 2 zł + 2 zł + 5 groszy + 1 grosz. W efekcie wypłacamy 1 banknot i 4 monety.
Uwaga 2.
Problem wypłaty reszty jest w ogólności NP-trudny.

Uwaga 3.
Algorytm zachłanny jest poprawny dla tego problemu w większości stosowanych obecnie systemów monetarnych, jednak nie działałby np. w przypadku systemu, w którym zamiast dwugroszówek byłyby czterogroszówki. Wówczas kontrprzykładem byłaby końcówka 8 groszy, bowiem algorytm rozbiłby ją na 5 groszy + 2 grosze + 1 grosz, zamiast 2 razy po 4 grosze. Historycznym przykładem podobnej sytuacji był system monetarny funkcjonujący w Anglii do roku 1971. Algorytm zachłanny może nie zadziałać także w polskim systemie monetarnym, jeżeli zabraknie monet jednogroszowych. Rzeczywiście, załóżmy, że zabrakło w kasie jednogroszówek, zaś do wypłaty pozostała powyższa kwota 14,06 zł. Algorytm zachłanny wypłaci 10 zł + 2 zł + 2 zł + 5 groszy i wpadnie w tarapaty, mimo że rozwiązanie istnieje. Wady tej nie ma algorytm programowania dynamicznego. Dzięki niemu możliwe jest znalezienie rozwiązania przy dowolnym zbiorze nominałów i dowolnej kwocie do wypłaty. Pomysł polega na podzieleniu problemu na mniejsze i stopniowym rozwiązywaniu podproblemów (poprzez budowanie tabeli wyników częściowych), by ostatecznie otrzymać upragniony rezultat. Tutaj przetwarzamy kolejne nominały n i obliczamy minimalną liczbę potrzebnych monet dla wydania kwot od O do k. Przy analizie kolejnego nominału wykorzystywane są informacje pozyskane w czasie wcześniejszych analiz. Jeśli nie będzie możliwe wydanie kwoty przy użyciu dostępnych nominałów, zostanie zwrócony wynik nieskończoność (∞). Aby zilustrować działanie algorytmu programowania dynamicznego, podzielimy nasz problem na część złotową (tab. 1) i groszową (tab. 2). Odpowiedź optymalną odczytujemy w prawym dolnym rogu tabeli.
Uwaga 4.
Złą wiadomością jest to, że algorytm programowania dynamicznego działa w czasie proporcjonalnym do wartości k, a ta może być bardzo duża. O tego typu algorytmach mówimy, że są pseudowielomianowe.

Marek Kubale
kubale@eti.pg.edu.pl