Dany jest problem:
Stirlitz wolnym krokiem wszedł do kawiarni Elefant. Pod oknem zobaczył barczystego mężczyznę z szelkami spadochronu zwisającymi spod kurtki.
‘Łącznik z Centrali’ – pomyślał Stirlitz.
‘Tak, to ja’ – pomyślał Łącznik.
Usiedli przy pustym stoliku, wymieniając wcześniej umówione 43 uściski dłoni. Po chwili milczenia Łącznik podsunął Stirlitzowi niewielką książeczkę.
‘To jest to, o co prosiliście. Uniwersalne rozmówki rosyjsko-albańsko-niemiecko-gaelickie.’
Stirlitz zamyślił się. ‘Potrzebuję tego więcej. Mam do opanowania N języków.’
‘Proszę, oto K książeczek z rozmówkami. Każdy język jest w co najmniej jednej, a niektóre zawierają całkiem dużo różnych języków!’. Łącznik otworzył wielki kufer udający futerał na flet piccolo.
‘Ale ja nie mogę paradować po kancelarii Rzeszy z K tomami pod pachą!’ – bronił się Stirlitz – ‘Wybierzcie mi z tego taki podzbiór, żeby obejmował wszystkie N potrzebnych języków. I żeby był jak najmniejszy.’
Ale Łącznika już nie było: niepostrzeżenie wybiegł z kawiarni, zostawiając asa wywiadu sam na sam z wielkim kufrem rozmówek. Po chwili wyszedł też Stirlitz, niosąc pod pachą optymalny podzbiór. Śledzący go Müller zdziwił się, że tak szybko uporał się z zadaniem – nie wiedział, że Bohaterowie Związku Radzieckiego potrafią rozwiązywać problemy NP-trudne w czasie wielomianowym.
Zaprojektuj rozwiązanie tego zadania za pomocą algorytmu zachłannego, algorytmu wychładzania (funkcja celu, definicja sąsiedztwa rozwiązań), algorytmu genetycznego (funkcja celu, sposób kodowania). Wskaż przykład sytuacji (konkretny rozkład języków w książkach), w której algorytm zachłanny da rozwiązanie nieoptymalne.