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.
Back to the Marta Kasprzak's Home Page
7 Oct 2010