Na dyskretnej planszy 1000x1000 należy rozwiązać problem komiwojażera (TSP - Travelling Salesman Problem) dla 400 miast. Zakładamy, że odległość między miastami jest obliczana za pomocą metryki euklidesowej na płaszczyźnie.
Ocenie podlega przede wszystkim jakość wygenerowanej drogi (minimalna długość), w drugiej kolejności szybkość zastosowanego algorytmu. Oczywiście wygenerowana droga musi być prawidłowym cyklem komiwojażera. Na ocenę nie mają wpływu: język programowania wykorzystany w implementacji i zastosowany algorytm (heurystyka), tak długo jak autor potrafi wytłumaczyć w jaki sposób otrzymał wynik.
Dla celów treningowych zamieszczam poniżej kilka przykładowych zbiorów danych wejściowych. Podczas zaliczenia trzeba będzie uruchomić program dla podanego przeze mnie (wcześniej nieznanego) zbioru miast.
To zadanie jest w znacznej części powtórzeniem zadania sprzed kilku lat. Zapewniam jednak, że "egzaminacyjny" zbiór miast będzie inny niż w poprzednich edycjach. Zatem próba wykorzystania gotowca od kolegów ze starszych lat może nie przynieść spodziewanego efektu.
Wejście = Opis miast jest plikiem tekstowym z rozszerzeniem .city, który w pierwszym wierszu zawiera liczbę miast a następnie wiersz po wierszu pozycję X i Y (z zakresu 0-1000) każdego miasta (z 400) na mapie.
Wyjście = Opis drogi komiwojażera jest plikiem tekstowym z rozszerzeniem .trs zawierającym permutację numerów miast (od 0 do N-1) stanowiąca drogę komiwojażera.
Ponadto dla pliku wyjściowego winien się generować (wypisywać na konsoli) sumaryczny koszt drogi.
Wyniki przykładowe dla zbiorów A-D uzyskano za pomocą prostej heurystyki zachłannej zaczynającej od losowego miasta i zawsze dodającej aktualnie najbliższe nieodwiedzone miasto.
Ponadto trzy przykłady skonwertowanych problemów z TSPlib - nie spełniają one wszystkich warunków dotyczących formatu wejścia (liczba miast).
i wiele innych.