Optymalizacja kombinatoryczna − laboratorium

semestr zimowy 2010/2011

Wierzchołki wszystkich wielokątów i cykli mają w poniższych problemach współrzędne będące liczbami naturalnymi. Dopuszcza się zastosowanie pewnego przybliżenia przy obliczaniu powierzchni/obwodu wielokąta i długości cyklu. Wielokąt jest prosty, jeżeli jedynymi punktami wspólnymi jego boków są wierzchołki boków sąsiednich.

Problem I

Mamy dany zdefiniowany na płaszczyźnie zbiór wielokątów prostych, nazywanych sąsiedztwami. Należy skonstruować taki wielokąt prosty zawierający część sąsiedztw (co najmniej dwa) i nie przecinający pozostałych (co najmniej jedno sąsiedztwo na zewnątrz wielokąta), że stosunek liczby otoczonych sąsiedztw do obwodu wielokąta jest maksymalny.

Problem II

Mamy dany zdefiniowany na płaszczyźnie zbiór wielokątów prostych, nazywanych sąsiedztwami. Należy skonstruować taki wielokąt prosty zawierający co najmniej połowę sąsiedztw i nie przecinający pozostałych (co najmniej jedno sąsiedztwo na zewnątrz wielokąta), że jego wierzchołki stanowią podzbiór wszystkich wierzchołków sąsiedztw i jego powierzchnia jest minimalna.

Problem III

Mamy dany zdefiniowany na płaszczyźnie wielokąt prosty z "dziurami" (również wielokąty proste). Należy znaleźć taki cykl zawarty w całości wewnątrz tego obszaru, że otacza on co najmniej połowę dziur i jego długość jest minimalna.

Program

Należy zaprojektować i zaimplementować algorytm dokładny rozwiązujący jeden wybrany problem. W przypadku przerwania obliczeń przed końcem program musi poprawnie wyświetlić najlepsze osiągnięte rozwiązanie. Dodatkowo należy zaimplementować procedurę generującą nietrywialne instancje w sposób losowy (z parametrem pozwalającym na utworzenie instancji o różnym stopniu trudności) oraz moduł wizualizacji rozwiązania.

Sprawozdanie

Termin oddania − najpóźniej do 17 stycznia 2011 (grupy z tygodni nieparzystych) lub 24 stycznia 2011 (grupy z tygodni parzystych), na nośniku papierowym. W sprawozdaniu należy zamieścić m.in. opis metod zastosowanych do generowania instancji oraz do rozwiązania problemu (w tym co najmniej jednej heurystyki wspomagającej algorytm dokładny), wyniki testów na instancjach o różnym stopniu trudności (w tym jakość rozwiązań uzyskanych w trybie przerwania obliczeń), wnioski obejmujące plusy i minusy zaproponowanego rozwiązania. Mile widziane propozycje zastosowania algorytmu w praktyce.

Zaliczenie

Najpóźniej na ostatnich zajęciach w semestrze, czyli odpowiednio w dniu 19 lub 21 stycznia 2011 (grupy z tygodni nieparzystych) oraz 26 lub 28 stycznia 2011 (grupy z tygodni parzystych). Dodatkowo w dniach 1 grudnia lub 19 listopada (odpowiednio środa i piątek z tygodni nieparzystych) oraz 24 lub 26 listopada (grupy z tygodni parzystych) należy zaprezentować działający generator instancji wraz z ich wizualizacją. Każdy tydzień spóźnienia w stosunku do podanego terminu prezentacji generatora instancji, oddania sprawozdania lub zaliczenia programu skutkuje obniżeniem oceny o kolejne 0,5 stopnia (do granicy 3,0 w przypadku wystawienia oceny pozytywnej).

Konsultacje

W semestrze zimowym 2010/2011: Ośrodek Nauki PAN, ul. Wieniawskiego 17/19, p. 215, piątki 11:30−13:00.