Witajcie, dostaliśmy na drugim semestrze studiów zaocznych zadanie, do którego nie mam pojęcia, jak się zabrać. Prosiłbym o podpowiedzi, jakiekolwiek wskazówki, nie mogłem znaleźć nic podobnego, jeśli chodzi o treść. Dodam, że na ten moment przerobiliśmy tylko podstawy programowania, jak zmienne, tablice oraz pętle.
Laboratorium 3, 4
Algorytm symulowanego wyżarzania dla problemu komiwojażera
- Cel ćwiczenia
Celem ćwiczenia jest nauka implementacji algorytmów symulowanego wyżarzania. Algorytm należy zaimplementować w języku C++. Algorytm będzie rozwiązywał problem komiwojażera.
- Dane wejściowe
Algorytm będzie czytał dane ze standardowego wejścia w następującym formacie:
n
c(1,1) c(1,2) ... c(1,n)
c(2,1) c(2,2) ... c(2,n)
…
c(n,1) c(n,2) ... c(n,n)
Wiersz pierwszy zawiera jedną liczbę całkowitą, określającą liczbę n (n ≤ 100) miast. Każdy z kolejnych n wierszy zawiera n liczb całkowitych oddzielonych jedną spacją, gdzie c(i,j) oznacza dystans pomiędzy parą miast i, j. Przykładowe dane:
5
0 4 5 2 1
5 0 2 4 1
3 8 0 8 4
2 7 4 0 6
4 5 6 2 0
- Wyniki wyjściowe
Algorytm będzie zwracał wyniki na standardowe wyjście w następującym formacie:
c
𝛑(1) 𝛑(2) … 𝛑(n)
Wiersz pierwszy zawiera jedną liczbę całkowitą, określającą dystans c, jaki ma pokonać komiwojażer (długość cyklu Hamiltona). Kolejny wiersz zawiera n liczb całkowitych (permutację zbioru miast) oddzielonych jedną spacją, gdzie 𝛑(i) oznacza i-te w kolejności miasto odwiedzone przez komiwojażera. dystans pomiędzy parą miast i, j. Przykładowe wyniki:
15
1 5 4 2 3