Algorytm symulowanego wyżarzania dla problemu komiwojażera

Odpowiedz Nowy wątek
2019-05-06 09:18
0

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

  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.

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

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

Pozostało 580 znaków

2019-05-06 09:28
0

Przerobiliśmy "zmienne, tablice oraz pętle", a dalej nic? Żadnych algorytmów, struktur danych, w szczególności grafów?


Pozostało 580 znaków

2019-05-06 10:11
0
lion137 napisał(a):

Przerobiliśmy "zmienne, tablice oraz pętle", a dalej nic? Żadnych algorytmów, struktur danych, w szczególności grafów?

Hej, poruszaliśmy następujące zagadnienia: "Transformacja wielomianowa", "Diagram przejść", "Sortowanie szybkie", "Sortowanie bąbelkowe", "Problem jako czarna skrzynka", "Optimum lokalne", itd...

Pozostało 580 znaków

2019-05-06 10:43
0

@Agrash: to szukasz optimum lokalnego funkcji, która zwraca trasę komiwojażera.

Pozostało 580 znaków

2019-05-06 11:27
0

Może zacznij od tego czy masz problem z samym

  • algorytmem wyżarzania?
  • czy na czym polega komiwojażer?
  • czy sama implementacja? (wiedza ze zmiennych/pętli Ci wystarczy do zaprogramowania) wteyd zapytaj o cos konkretnego pokaż jaki już masz kod
  • czy oczekujesz gotowca? lepiej się nie przyznawaj :D

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 0, botów: 1

Robot: CCBot