Problem Komiwojażera

Odpowiedz Nowy wątek
2019-01-06 18:47
0

Cześć mam problem polegający na tym że muszę :

a) Przeprowadzić „odręczną” symulację działania algorytmu dokładnego: wypisać wszystkie możliwe trasy przejazdu komiwojażera, wyznaczyć odpowiadające im długości oraz wskazać trasę najkrótszą.
b) Przeprowadzić „odręczną” symulację działania algorytmu zachłannego. Wypisać etapy tworzenia trasy przejazdu.
c) Dla wyniku otrzymanego algorytmem zachłannym wyznaczyć wartość względnego odchylenia od optimum.
Należy przyjąć, że komiwojażer wyrusza z miasta 0 i nie wraca do tego miasta
.

Oto mój zestaw danych
0 43 62 69 85
83 0 17 93 6
85 79 0 57 64
72 78 71 0 58
49 13 92 44 0

Jak to zrobić

edytowany 1x, ostatnio: kq, 2019-01-06 18:48
Wyszedłbym od zrozumienia tego, co opisuje "zestaw danych". - yarel 2019-01-06 19:01

Pozostało 580 znaków

2019-01-06 19:03
0

Jest to macierz 5x5 opisująca liczbę miast

Ta macierz opisuje coś innego ;) Liczbę miast można opisać jedną liczbą: 5 - yarel 2019-01-06 19:06

Pozostało 580 znaków

2019-01-06 19:08
0

Po pierwsze to dziękuje ci za tak szybkie odpowiedzi . Ja rozwiązuje ten problem komiwojażera pierwszy raz , i za bardzo nie wiem jak przeprowadzić te odręczne symulacje podając czas i wszystkie możliwe trasy przejazdu

Pozostało 580 znaków

2019-01-06 19:15
0
  1. Macierz opisuje Ci koszt (czas?) przejazdu z miasta i do j.

  2. W problemie komiwojażera szukasz "najtańszego" rozwiązania. Wszystkich rozwiązań masz N!

  3. Startujesz z miasta 0 i masz odwiedzić pozostałe (1,2,3,4), więc masz 4! = 24 kombinacje
    0-1-2-3-4
    0-1-2-4-3
    0-1-3-2-4
    0-1-3-4-2
    0-1-4-2-3
    0-1-4-3-2
    0-2-...
    ...

  4. Z macierzy odczytujesz koszty przejazdu, np. 0-1-2-3-4: koszt z 0-1 + koszt z 1-2 ...
    Koszt 0-1: 43
    Koszt 1-2: 17
    itd.

W dokładnej metodzie rozważasz wszystkie możliwości, w zachłannej wybierasz najbliższą/najkrótszą trasę startująca z 0, później najkrtószą z tego miasta, które znalazłeś w poprzednim kroku itd.

Pozostało 580 znaków

2019-01-06 19:20
0
Cisi204 napisał(a):

Cześć mam problem polegający na tym że muszę :

*a) Przeprowadzić „odręczną” symulację działania algorytmu dokładnego: wypisać wszystkie możliwe trasy przejazdu komiwojażera, wyznaczyć odpowiadające im długości oraz wskazać trasę najkrótszą.

no to czeka Cię wycieczka przez wszystkie dopuszczalne warianty i tyle... ;)

b) Przeprowadzić „odręczną” symulację działania algorytmu zachłannego. Wypisać etapy tworzenia trasy przejazdu.
c) Dla wyniku otrzymanego algorytmem zachłannym wyznaczyć wartość względnego odchylenia od optimum.

Optymalna (najkrótsza) trasa ma długość X. Sub-optymalna trasa znaleziona algorytmem zachłannym ma długość Y - zatem względne odchylenie będzie równe

\epsilon = \frac{Y}{X}

Jak to zrobić

A co do tej pory próbowałeś zrobić? :)

Dla zapisu macierzowego grafu możesz przyjąć, że numer wiersza oznacza wierzchołek grafu, z którego wychodzisz, zaś numer kolumny wierzchołek grafu, do którego wchodzisz - albo na odwrót*. Byleby się trzymać cały czas jednej konwencji i aby była zgodna z tym, co podał autor.

Algorytm zachłanny będzie dokonywał najlepszego w danej chwili wyboru - czyli będzie dobierał tak krótką krawędź, jak tylko może, i próbował przejść dalej. Następnie z nowego wierzchołka będzie próbował iść dalej w ten sam sposób.

Możesz to zrealizować (w dużym uproszczeniu) tak:

  1. na początku masz pustą ścieżkę
  2. wybierasz numer wiersza odpowiadający miastu, z którego startujesz (np. 0)
  3. w wybranym wierszu znajdujesz najkrótszą krawędź do miasta, którego jeszcze nie odwiedziłeś, i bierzesz jego indeks
  4. zapamiętujesz, że odwiedziłeś to miasto i dodajesz je do swojej ścieżki - nie będziesz mógł odwiedzić go po raz drugi
  5. bierzesz indeks nowo wybranego miasta i przechodzisz do wiersza o tym indeksie
  6. jeśli wróciłeś do punktu początkowego, kończysz działanie **
  7. wracasz do kroku 3.

* nie pamiętam, czy jest jakaś narzucona konwencja odnośnie tego przyporządkowania skąd/dokąd do wierszy/kolumn. Może nawet są dwie sprzeczne, nieważne. Mam tylko nadzieję, że nie przyleci mi tu zaraz @Tig żeby cytować Wikipedię.

** ewentualnie kończysz, jeśli nie odwiedziłeś jeszcze tylko punktu startowego i masz do niego nie wracać. Możesz też wrzucić go na początku na listę odwiedzonych i dzięki temu nie odwiedzisz go przez przypadek.


Prosząc o pomoc w wiadomości prywatnej odbierasz sobie szansę na otrzymanie pomocy od kogoś bardziej kompetentnego :)

Pozostało 580 znaków

2019-01-06 19:31
0

Panowie dziękuje wam za szybką odpowiedz , z tym grafem sobie poradzę ponieważ znalazłem materiał z poprzednich lat . Mam jeszcze jeden problem który polega na tym aby dla algorytmów heurystycznych wyznaczyć średnie wartości względnych odchyleń ich rozwiązań od optimum,wyznaczyć poprawę , jaką uzyskuje się przez zastosowanie algorytmu symulowanego wyżarzania w stosunku do rozwiązania dostarczonego przez algorytm zachłanny.

Tabelkę długością tras oraz czasem wykonywania obliczeń mam uzupełnioną (jeśli wam się przyda dla z wizualizowania sytuacji wrzucę wam) czy istnieją jakieś wzory na mój problem?

ale chwileczkę, z czym dokładnie masz problem, z realizacją algorytmu heurystycznego czy z wyznaczeniem poprawy? Jeśli z tym drugim to oblicz względne odchylenia dla obu metod i porównaj ;) - superdurszlak 2019-01-06 19:33

Pozostało 580 znaków

2019-01-06 19:38
0

Dla algorytmu zachłannego oraz algorytmu symulowanego wyżarzania mam wyznaczyć Średnie względne odchylenie od optimum
W drugim wariancie dla algorytmu symulowanego wyżarzania mam wyznaczyć średnia względną poprawę .

Czy na te obliczenia istnieje jakiś wzór ? na tym polega mój problem

Pozostało 580 znaków

2019-01-06 19:43
0
Cisi204 napisał(a):

Dla algorytmu zachłannego oraz algorytmu symulowanego wyżarzania mam wyznaczyć Średnie względne odchylenie od optimum

No puszczasz algorytm zachłanny i z wyżarzaniem dla różnych punktów startowych (np. startując po kolei z każdego miasta), liczysz odchylenia i liczysz średnią - ot, cała filozofia

W drugim wariancie dla algorytmu symulowanego wyżarzania mam wyznaczyć średnia względną poprawę .

Jeśli droga wyznaczona przez algorytm zachłanny jest średnio 4 razy dłuższa od optymalnej, a algorytm symulowanego wyżarzania daje tylko 2 razy dłuższą, to uzyskałeś dwukrotną poprawę - przynajmniej tak to rozumiem

Czy na te obliczenia istnieje jakiś wzór ? na tym polega mój problem

Wzór na względne odchylenie już masz, jeszcze potrzebujesz wzoru na średnią arytmetyczną :)


Prosząc o pomoc w wiadomości prywatnej odbierasz sobie szansę na otrzymanie pomocy od kogoś bardziej kompetentnego :)

Pozostało 580 znaków

2019-01-06 20:30
0

Nie wiem czy się dobrze rozumiemy , ale postaram ci pokazać jak ja to rozumiem.
Mam algorytm zachłanny:
n=5 Długość trasy w przebiegu 1,2,3 ma się następująco:205,113,78 ( z tego wyliczam średnią arytmetyczną). Następnie (205-średnia)^2+(113-średnia)^2+(78-średnia)^2 wszystko pod pierwiastkiem z tego otrzymuje jakiś wynik i on jest moim średnim odchyleniem od Optimium tak ?

Pozostało 580 znaków

2019-01-07 08:11
0

Witam w nowym dniu. Otóż wracając do zadania :
a)Przeprowadzić „odręczną” symulację działania algorytmu dokładnego: wypisać wszystkie możliwe trasy przejazdu komiwojażera, wyznaczyć odpowiadające im długości oraz wskazać trasę najkrótszą.
Zrobiłem go , wypisałem wszystkie możliwe trasy przejazdu i wybrałem z niego tę najkrótszą.

b)Przeprowadzić „odręczną” symulację działania algorytmu zachłannego. Wypisać etapy tworzenia trasy przejazdu.

Mam problem z tym zadaniem , a dokładnie rzecz ujmując nie wiem czy dobrze kombinuje : otóż mam takie trasy
0-1-4
0-2-3-4-1
0-3-2-4
0-4-3

Jak dla mnie w zachłannym wybierasz najkrótszą do jeszcze nieodwiedzonego miasta i masz odwiedzić wszystkie miasta, więc nie możesz mieć trasy "0-4-3", bo brakuje 1 i 2. - yarel 2019-01-07 08:40
Tak Tak trochę się zagmatwałem z tymi drogami ale poniżej mam swoje propozycję - Cisi204 2019-01-07 08:43

Pozostało 580 znaków

2019-01-07 08:21
0

Lub taka trasa algorytmem zachłannym 0-1-4-1-2-3-4 ( komiwojażer był we wszystkich miastach , problem w tym że był 2x w mieście 1)

lub taka trasa 0-1-4-3-2 (komiwojażer był we wszystkich miejscach , lecz w pewnym momencie aby nie powtarzać tej samej trasy , wybrał nie najkrótszą ścieżkę)
co o tym myślicie ?

edytowany 3x, ostatnio: Cisi204, 2019-01-07 08:31
Korzystaj z edycji postu - piszesz po kilka postów z rzędu, w każdym dodając jakieś poprawki czy dopowiedzenia do poprzedniego ;) - superdurszlak 2019-01-07 08:28

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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