Optymalizacja dyskretna

Zadania kwalifikacyjne są tutaj.

Opis

Bardzo często zdarza się tak, że pomimo ogromnego postępu, jaki cywilizacja poczyniłA dzięki komputerom, wciąż jesteśmy w pewnych dziedzinach bezsilni. Dla przykładu: policzenie prostego problemu znalezienia najkrótszego cyklu łączącego największe 50 miast w Polsce (cyklu Hamiltona) okazuje się nieosiągalne. Musimy sobie radzić w inny sposób. Jedną z metod są algorytmy aproksymacyjne, które dają nam przybliżone rozwiązanie, zwykle gorsze o optymalnego o co najwyżej pewną stałą. Inną metodą są heurystyki, które dają nam przybliżone rozwiązania, które zwykle są dopuszczalne przez aktualne standardy (dużej firmie kurierskiej mimo, że bardzo zależy na optymalnym rozwiązaniu, to zwykle pogodzi się z rozwiązaniem wystarczająco bliskim optymalnemu).

Warsztaty będą stanowiły przegląd wybranych metod używanych w optymalizacji dyskretnej. Opowiemy sobie (i zaimplementujemy, aby zobaczyć jak działają na wybranych przykładach z prawdziwego życia) co najmniej o następujących algorytmach: A*, ALT, IDA*, beam search, hill climbing, simulated annealing, taboo search (można sobie wygooglować te rzeczy). Zmierzymy także się z kilkoma zadaniami optymalizacyjnymi z konkursów typu Deadline24. 

Wymagania i przydatne rzeczy