© Jakub Wróblewski     (jeśli nie zaznaczono inaczej)

Zadania z metod optymalizacji

Wspólne pytania do poniższych zadań:

  • Zaprojektuj rozwiązanie tego zadania za pomocą algorytmu zachłannego.
  • Wskaż przykład sytuacji (konkretne dane liczbowe), w której algorytm zachłanny da rozwiązanie nieoptymalne.
  • Zaprojektuj rozwiązanie tego zadania za pomocą algorytmu wychładzania (funkcja celu, definicja sąsiedztwa rozwiązań).
  • Zaprojektuj rozwiązanie tego zadania za pomocą algorytmu genetycznego (funkcja celu, sposób kodowania rozwiązań, ew. definicja operatorów genetycznych, jeśli inne niż standardowe).
  • Uzasadnij, że poniższe problemy są NP-trudne.



Zadanie 1:

'To kawiarnia' - pomyślał Stierlitz. Stierlitz wolnym krokiem wszedł do kawiarni Elefant. Pod oknem zobaczył barczystego mężczyznę z szelkami spadochronu zwisającymi spod kurtki.

‘Łącznik z Centrali’ – pomyślał Stierlitz.

‘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ął Stierlitzowi niewielką książeczkę.

‘To jest to, o co prosiliście. Uniwersalne rozmówki rosyjsko-albańsko-niemiecko-gaelickie.’

Stierlitz 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ę Stierlitz – ‘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ż Stierlitz, 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.


Stierlitz czy Stirlitz?




Zadanie 2:

’Mistrz Ulryk’ - rzekł herold – ‘wzywa twój majestat, panie, i księcia Witolda na bitwę śmiertelną i aby męstwo wasze, którego wam widać brakuje, podniecić, śle wam tych K nagich mieczy.’ To rzekłszy, złożył miecze u stóp królewskich.

Jagiełło zadumał się. ‘Mieczów ci u nas dostatek, a z Bożą pomocą nim dzień minie napełnimy wozy łupami.’

Król skinął na stojącego opodal Jaśka Mążyka z Dąbrowy. ‘Rozdziel te miecze między rycerstwo nasze i naszego brata Witolda. Bacz jeno, by żaden z nas dwóch nie był pokrzywdzony.’

Jaśko zabrał się do pracy. Wprawnym okiem ocenił każdy z K mieczy i zanotował jego cenę ki. Teraz czekało go trudniejsze zadanie: wybrać takie miecze dla księcia Witolda, by ich wartość była taka sama, jak mieczy pozostawionych królowi. Pojął szybko, że to mu się może nie udać, postanowił więc dokupić z własnego majątku nieco kosztowności tej stronie, która otrzyma mniej cenne miecze – by wartość się wyrównała. Jak powinien postąpić, by wydać jak najmniej?




Zadanie 3:

Pewien jubiler-amator wykuł K1 pierścieni dla królów elfów pod otwartym niebem, K2 dla krasnoludów w ich podziemnych pałacach, K3 dla śmiertelników, ludzi śmierci podległych. A że ów jubiler był z zamiłowania dyktatorem, postanowił wykuć też N Pierścieni Władzy, z których każdy kontrolował pewien ustalony podzbiór pierścieni uprzednio wykutych (przy czym każdy zwykły pierścień mógł być kontrolowany przez co najmniej jeden z Pierścieni Władzy).

Pewnego dnia jubiler postanowił wszystkie zwykłe pierścienie zgromadzić i w ciemności związać. W tym celu musiał założyć na palce tyle Pierścieni Władzy, by móc na raz kontrolować wszystkie pierścienie zwykłe. Zauważył jednak, że każdy założony Pierścień Władzy odbija się negatywnie na zdrowiu – postanowił więc założyć tylko te Pierścienie, które są niezbędne. Które Pierścienie powinien założyć, by użyć ich jak najmniej?




Zadanie 4:

’Mistrz Ulryk’ - rzekł herold – ‘wzywa twój majestat, panie, i księcia Witolda na bitwę śmiertelną i aby męstwo wasze, którego wam widać brakuje, podniecić, śle wam tych K nagich mieczy.’ To rzekłszy, złożył miecze u stóp królewskich.

Jagiełło zadumał się. ‘Mieczów ci u nas dostatek, a z Bożą pomocą nim dzień minie napełnimy wozy łupami. Niechaj więc miecze te nagie zawiezione zostaną do naszego obozu za lasem.’

Król skinął na stojącego opodal Jaśka Mążyka z Dąbrowy, a ten zabrał się do pracy. Każdy z K mieczy miał na klindze wygrawerowaną wagę w pudach (ozn. mi). Jaśko wiedział, że na wozy, aby nie połamać osi, można załadować najwyżej 100 pudów, musiał więc tak powiązać miecze w pęczki, by żaden z wozów nie był przeciążony. Pamiętał jednak słowa królewskie o łupach i pomny tej przestrogi postanowił wysłać do obozu możliwie najmniej wozów. Jak powinien postąpić, by odesłać do obozu wszystkie K nagich mieczy i by jak najmniej wozów zostało do tego użytych?


- - - - - - - -