Algorytmy dla problemu optymalizacyjnego

---

Symetryczny problem komiwojażera (TSP)

Opis problemu

Mamy n miast o współrzędnych (x_i,y_i), położonych w kwadracie o boku 100 jednostek. Należy tak ustalić kolejność odwiedzin miast przez komiwojażera, by odległość przezeń przebyta była minimalna przy założeniu, że miasto można odwiedzić tylko jeden raz oraz że wracamy do miasta początkowego

Obliczenie odległości między miastami
Odl(i,j)=int(sqr((x_i- x_j)²+(y_i-y_j )²)+0.51)

Reprezentacja rozwiązania (trasy)
n-elementowy wektor zawierąjacy numery odwiedzanych miast, przy czym j-ty numer miasta może wystąpić tylko raz (1<=j<=n); trasa(i)=j oznacza, że miasto nr j jest odwiedzane jako i-te z kolei.

Struktura zbioru testowego
Zbiór TSP50.TXT, zawierający dane dla 50 miast, zorganizowany jest następująco:

liczba miast
najlepszy wynik osiągnięty przez znane algorytmy (tutaj - wynik optymalny),
współrzędne pierwszego miasta
...
współrzędne i-tego miasta
...
współrzędne ostatniego miasta

Algorytmy rozwiązujące

1. Losowy
wylosować trasę komiwojażera,
obliczyć jej długość,
obliczenia powtórzyć k (np. 100) razy,
najlepszy wynik spośród k jest rozwiązaniem problemu.

2. NN - najbliższego sąsiada
podać miasto startowe,
trasa powstaje przez dodanie kolejnego, nieodwiedzonego miasta, które jest najbliższe bieżącemu,
pamiętać o powrocie do miasta startowego.

3. Prosty algorytm poprawy
wylosować trasę komiwojażera, co daje trasę startową (i najlepszą zarazem),
wykonać k (np. 1000) iteracji, w których:
    wylosować dwie pozycje trasy i zamienić miejscami miasta na tych pozycjach (wykorzystać rozwiązanie problemu nr 23),
    jeśli otrzymana trasa jest krótsza niż najlepsza, mamy nową trasę najlepszą (do poprawy w następnym kroku), w przeciwnym wypadku - wracamy do trasy poprzedniej (czyli odwracamy zamianę miast).

Zadania

1. napisać programy,
2. sprawdzić wpływ parametru k na jakość wyników (algorytm 1 i 3)
3. porównać działanie algorytmów (proszę pamiętać, że 1 i 3 są algorytmami losowymi).

Uwagi

1. dane z pliku najlepiej przenieść do arkusza,
2. opracować arkusz służący do obliczenia długości trasy na podstawie kolejności odwiedzanych miast (niekoniecznie wykorzystamy go podczas obliczeń, ale na pewno przyda się do sprawdzenia otrzymanych wyników),
3. można spróbować znaleźć rozwiązanie optymalne przy użyciu Solvera.