Prowadzę zajęcia odbywające się w czwartki o godzinie 18:30.

Materiały do zajęć z heurystyk:

• Szablon programu rozwiązującego symetryczne TSP z zaimplementowanym LS (3.59 kB)
• TSP mała instancja (4.36 kB) - najlepsze znane rozwiązanie 42080
• Szablon programu rozwiązującego symetryczne TSP (1.75 kB)
• TSP instancja I (15.71 kB) - najlepsze znane rozwiązanie 36905
• TSP instancja II (17.98 kB) - najlepsze znane rozwiązanie 48912

Podstawą zaliczenia przedmiotu jest raport z przeprowadzonego projektu. Zadanie polega na implementacji trzech różnych algorytmów rozwiązujących problem optymalizacji kombinatorycznej. Należy zaimplementować następujące algorytmy:

• algorytm dokładny,
• branch and bound,
• heurystyka,
• inna heurystyka (dla zespołów dwuosobowych).

Treść zadania (431.62 kB)

UWAGA: Można założyć, że dane dobrane są tak, że nie opłaca się zrzucać dwóch agentów w tym samym miejscu.

Sprawdzarka rozwiązań (6.99 kB) - program sprawdzający poprawność wygenerowanego pliku wyjściowego i podający liczbę punktów (czas uszeregowania). Kod w C++, jako pierwszy parametr należy przekazać plik .in, jako drugi plik .out.

Testy (81.61 kB) - test do zadania.

Testy dla par (28.77 kB) - dodatkowe testy dla zespołów chcących wykonać projekt w parze.

Raport z przeprowadzonego ćwiczenia powinien zawierać porównanie czasów wykonania oraz jakości otrzymanych wyników. Dodatkowo otrzymane wyniki powinny być zgłoszone poprzez przeznaczoną do tego stronę internetową. 

Szczegółowy terminarz, wymagania odnośnie raportu i strona do zgłaszania wyników pojawią się wkrótce.

Dodatkowo można dostać nagrody specjalne za:

• wystartowanie w TopCoder Marathon Match i znalezienie się w górnych 25% - zwolnienie z pisania raportu (wyniki i kody źródłowe należy mimo to zgłosić),
• wystartowanie w TopCoder Marathon Match i osiągnięcie zadowalającego wyniku (wg mojej oceny) - pół oceny w górę,
• największą liczbę najlepszych wyników - ocena w górę,
• drugie i trzecie miejsce pod względem liczby najlepszych wyników - pół oceny w górę.

Sprawozdanie powinno zawierać:

• Opis środowiska (sprzęt i oprogramowanie) w którym realizowany był projekt.
• Opis sposobu implementacji, użytych algorytmów i wyników dla algorytmu dokładnego, branch and bound oraz jednej lub dwóch (w przypadku pracy w parze) heurystyk.
• Wyniki powinny zawierać czas wykonania oraz ocenę rozwiązania, w przypadku b&b również liczbę odcięć, a w przypadku rozwiązania dokładnego i b&b liczbę odwiedzonych węzłów i liści.
• Porównanie wyników i czasów wykonania wszystkich algorytmów.
• Dla zespołów pracujących w parach porównanie czasu działania algorytmu dokładnego i b&b w zależności od liczby baz i agentów (tests_ok_all.zip).
• W momencie gdy alg. dokładny lub b&b działa ponad 3 minuty powinien być zatrzymany, najlepszy zwrócony do tego czasu przez niego wynik zapisany jako wynik działania algorytmu, a czas wykonania uznany za zbyt długi, aby program mógł się zakończyć. Ambitne osoby mogą podwyższyć limit czasowy z 3 min. do dłuższego czasu, ale nie jest to wymagane.
• Analizę złożoności obliczeniowej algorytmów (w tym złożoność liczenia lower bounda).
• Wnioski.
• Dane i wyniki gdzie to tylko możliwe powinny być zaprezentowane i porównywane na wykresach. Na końcu raportu powinny znaleźć się tabele ze wszystkimi liczbami.

Przykładowe wartości optymalne dla testów ze zbioru dla par (do przetestowania algorytmu dokładnego):

• test_ok_4_2.in - 63.625 
• test_ok_6_2.in - 102.343
• test_ok_6_4.in - 51.650