Problem Komiwojażera

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ć

Jest to macierz 5x5 opisująca liczbę miast

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

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.

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

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.

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?

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

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ą :)

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 ?

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

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 ?

Po pierwsze dziękuje za tak szybką odpowiedz . Czyli droga 0-1-4-3-2 realizowana algorytmem zachłannym jest prawidłowa ?

Mam jeszcze pytanko jak obliczyć Odchylenie od optimum (%). Posiadam najkrótszą trasę komiwojażera która wynosi 157 , oraz najkrótszą trasę wyznaczoną algorytmem zachłannym która wynosi 164. Czy to odchylenie będzie równe 164/157?

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.

Wcześniej się rypnąłem we wzorze - powinno być

gdzie Y-X to różnica między trasą optymalną a tą znalezioną przez algorytm zachłanny.

Przeliczenie na procenty jest już chyba oczywiste :P

Tzn. jeśli trasa optymalna ma długość 100, a znaleziona 110, to względne odchylenie wyniesie 0,1 lub 10%.

O tego szukałem drogi kolego , tego szukałem a jak jeszcze obliczyć to średnią względną poprawę

Cisi204 napisał(a):

O tego szukałem drogi kolego , tego szukałem a jak jeszcze obliczyć to średnią względną poprawę

pisałem już wcześniej, potrzebujesz porównać odchylenia dla obu metod i obliczyć średnią arytmetyczną.

Trasa algorytmem zachłannym = 164
Trasa optymalna=157

167-157/157=0,044

czyli 4,4% tak ?

i teraz te odchylenia porównań z sobą i policzyć ich średnią arytmetyczną

Czy normalna jest sytuacja że długość drogi dla algorytmy symulowanego wyżarzania jest przy każdym przebiegu takiego samego n identyczna co długość drogi wykonywana przez algorytm dokładny ?

Cisi204 napisał(a):

Czy normalna jest sytuacja że długość drogi dla algorytmy symulowanego wyżarzania jest przy każdym przebiegu takiego samego n identyczna co długość drogi wykonywana przez algorytm dokładny ?

Nie wiem, nie próbowałem bawić się algorytmem symulowanego wyżarzania dla problemu komiwojażera :)

Możliwe, że otrzymałeś taki wynik z dwóch powodów:

• pracujesz na grafie pełnym (każde dwa miasta są połączone)
• pracujesz na bardzo małym grafie (masz tylko 5 wierzchołków)

Podejrzewam, że dla grafu mającego np. 300 wierzchołków i tylko 10 krawędzi wychodzących z każdego wierzchołka problematyczne byłoby nie tylko znalezienie optymalnego rozwiązania, ale nawet znalezienie poprawnego rozwiązania w ogóle ;)

Bardzo możliwe i jeszcze bardziej prawdopodobne , zastanawiam się nad tym jak obliczyć w takim przypadku odchylenie optimum skoro drogi są sobie równe , w takim przypadku to odchylenie będzie się równało 0%

Skoro obie drogi są równe, to raczej naturalne, że odchylenie jest zerowe.

Powód do zmartwień miałbyś, gdyby droga była równa optymalnej a odchylenie wynosiło 300% :P

Weź mi wytłumacz jeszcze raz aby wyznaczyć poprawę , jaką uzyskuje się przez zastosowanie algorytmu symulowanego wyżarzania w stosunku do rozwiązania dostarczonego przez algorytm zachłanny.

**dla n=5 **(3 przebiegi) długosć tras algorytmem zachłannym 136,61,119 | algorytmem wyrzażania 101,61,119

dla n=10 (3 przebiegi) długosć tras algorytmem zachłannym 233,115,268 | algorytmem wyrzażania 150,63,171

dla n=11 (3 przebiegi) długosć tras algorytmem zachłannym 187,195,245 | algorytmem wyrzażania 111,142,188

dla n=20 (3 przebiegi) długosć tras algorytmem zachłannym 221,262,257 | algorytmem wyrzażania 177,178,146

dla n=40 (3 przebiegi) długosć tras algorytmem zachłannym 380,326,250 | algorytmem wyrzażania 362,356,250

Czyli mam obliczyć średnia odchylenie tych dwóch algorytmów i policzyć ich średnią arytmetyczną czy jak to zrobić?

Cisi204 napisał(a):

Czyli mam obliczyć średnia odchylenie tych dwóch algorytmów

Tak

i policzyć ich średnią arytmetyczną czy jak to zrobić?

Nie.

Możesz

• pójść na skróty i policzyć, o ile punktów procentowych mniejsze (a może jednak większe? w paru przypadkach dał gorsze wyniki) odchylenie daje algorytm heurystyczny. Jeśli zachłanny daje 20% odchylenie, a heurystyczny 10%, to masz poprawę o 10 punktów procentowych.
• policzyć o ile % krótsza jest przeciętna trasa wyznaczona algorytmem heurystycznym od algorytmu zachłannego:
  

Proszę cię weż mnie teraz sprawdź czy poprawa dla n=5 będzie się równała 10,8 %??

Proszę cię abyś sprawdził tylko czy dobrze to obliczyłem przy pomocy mojego kalkulatora , który z algorytmami radzi sobie gorzej niż ty :)

Cisi204 napisał(a):

Proszę cię abyś sprawdził tylko czy dobrze to obliczyłem przy pomocy mojego kalkulatora , który z algorytmami radzi sobie gorzej niż ty :)

Ale to już nie są algorytmy, masz już wyniki, masz długości tras, dla kalkulatora to bez różnicy czy dodajesz cenę marchewki do ceny selera czy odejmujesz odchylenia jakichś dwóch algorytmów... jeśli wyliczyłeś z tego, co Ci wyszło, że odchylenie wynosi 10,4% albo 27,8%, to tyle wyszło i tyle.

żeby się jeszcze upewnić pisząc Średnia zachłannego oraz średnia heurystycznego masz na myśli średnią długość tras dla poszczególnych n tak ?

Cisi204 napisał(a):

żeby się jeszcze upewnić pisząc Średnia zachłannego oraz średnia heurystycznego masz na myśli średnią długość tras dla poszczególnych n tak ?

no jeśli chcesz liczyć poprawę z długości tras, a nie z odchyleń, to tak będzie chyba bezpieczniej niż zbierać wszystko do kupy.

Zauważ, że jeśli dla małych n uzyskasz średnią długość trasy krótszą o 100, to może to oznaczać znaczną poprawę, dla bardzo dużych n trasa gorsza o 100 może być tak naprawdę pomijalnie małym pogorszeniem wyniku, ale jeśli uśrednisz te wyniki to się okaże, że wychodzisz na zero.

Dlatego może lepiej będzie jednak porównywać średnie względne odchylenia zamiast liczyć z długości.