Algorytm symulowanego wyżarzania dla problemu komiwojażera

Question

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.

-------------------------------------------------------------------------------------------------

1. 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.

2. 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

3. 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

Answer 1

Dostajesz macierz sąsiedztwa grafu i masz znaleźć takie przejście po grafie, aby odwiedzić wszystkie wierzchołki przechodząc jak najmniejszą odległość (sumę wag krawędzi).

Nie jest znane rozwiązanie tego problemu, więc wystarczy, że sprawdzisz wszystkie możliwe permutacje wierzchołków.

Comments

Teraz się skapłem, że nie chodzi o to aby znaleźć rozwiązanie najlepsze, a prawie najlepsze w rozsądnej złożoności. Trzeba więc użyć tej heurystyki. Nie wiem jak ona działa więc nie jestem w stanie pomóc.