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