Przykładowe zadanie



Dany jest problem:

'To kawiarnia' - pomyślał Stirlitz.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.