Algorytmy do rozwiązywania asymetrycznego problemu Komiwojadżera (ATSP)

Zadanie PR1: Implementacja i analiza efektywności algorytmu podziału i ograniczeń oraz programowania dynamicznego

W ramach projektu należy zaimplementować oraz dokonać analizy efektywności algorytmu brutalnej śiły (BruteForce) oraz podziału i ograniczeń (B&B) dla asymetrycznego problemu komiwojażera (ATSP).

Założenia:

• Używane struktury danych powinny być alokowane dynamicznie (w zależności od aktualnego rozmiaru problemu).
• Program powinien umożliwić weryfikację poprawności działania algorytmu. W tym celu powinna istnieć możliwość wczytania danych wejściowych z pliku tekstowego.
• Po zaimplementowaniu i sprawdzeniu poprawności działania algorytmu należy dokonać pomiaru czasu jego działania w zależności od rozmiaru problemu (N) (gdzie (N) oznacza liczbę miast). Badania należy wykonać dla minimum 7 różnych reprezentatywnych wartości (N).
• Dla każdej wartości (N) należy wygenerować zestaw losowych instancji problemu w celu uśrednienia wyników (przykładowa liczba instancji może wynosić np. 20, 50, 100, w sprawozdaniu należy umieścić tylko wyniki uśrednione).
• Implementacje algorytmów należy dokonać zgodnie z obiektowym paradygmatem programowania.
• Używanie „okienek” nie jest konieczne i nie wpływa na ocenę (wystarczy wersja konsolowa).
• Kod źródłowy powinien być odpowiednio komentowany.