Algoryrmika - komiwojażer

Cześć :)
Dostałam na algorytmach zadanie którego treść brzmi:

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

0 24 71 65 5
50 0 31 36 7
29 64 0 97 77
87 64 53 0 94
66 52 21 8 0
to moje liczby

**i nie mam pojęcia jak się do tego zabrać. **

i tak 24 razy
W jaki sposób to uzupełnić nie mam pojęcia, jak napisać program do symulacji - tym bardziej.

Tu masz algorytm wyznaczania wszystkich permutacji:
https://www.geeksforgeeks.org/heaps-algorithm-for-generating-permutations/

Dla każdej takiej permutacji (np 0 4 2 1 3) bierzesz sobie liczby (np. tab[0][4]+tab[4][2]+tab[2][1]+tab[1][3]). Wybierasz sobie najkrótszą z nich.

W jaki sposób to uzupełnić nie mam pojęcia,

No normalnie, wyznaczasz wszystkie możliwe ścieżki (tu - wszystkie permutacje zaczynające się od wierzchołka 0), wyznaczasz długość każdej i wybierasz tę, która jest najkrótsza.

jak napisać program do symulacji - tym bardziej.

Zacznij od rozpisania sobie, co program musi zrobić, krok po kroku, może być jako lista kroków, może być w pseudokodzie. Zadanie mówi, że masz przeprowadzić "odręczną" symulację więc zakładam, że żadnego prawdziwego programu pisać nie musisz, "wykonanie" tego algorytmu wizualnie na kartce powinno wystarczyć.

Algorytm zachłanny będzie zawsze podejmował decyzję, która w danej chwili jest najbardziej opłacalna. Działając algorytmem zachłannym, powinnaś zawsze spośród wszystkich dozwolonych wybierać najkrótszą krawędź - dozwolonych, czyli takich, które wychodzącą z wierzchołka, w którym się teraz znajdujesz i prowadzą do wierzchołka, którego jeszcze nie odwiedziłaś.

Jeśli masz, dajmy na to, taką sytuację - jesteś w wierzchołku B, odwiedziłaś już A i D, a z B wychodzą takie krawędzie:

B->A = 10
B->C = 15
B->D = 20
B->E = 25 

To musisz wybierać między B->C, a B->E mimo, że B->A byłoby najkrótsze. B->C jest krótsze niż B->E, więc wygrywa.

Warunkiem koniecznym możliwości rozwiązania problemu jest istnienie co najmniej cyklu Hamiltona w grafie (jak jest ich kilka to należy znaleźć ten, który ma najmniejszą sumę wag krawędzi).

Ja proponuję bazować na iteracyjnym algorytmie przeszukiwania grafu wgłąb. Ten algorytm ma stos, wykonasz dwie modyfikacje:

1. Jeżeli na stosie są wszystkie wierzchołki (jest to równoważne faktowi, że stos liczy tyle pozycji, ile jest wierzchołków) i jest krawędź między ostatnim a pierwszym wierzchołkiem, to masz cykl Hamiltona, który wypisujesz jako uporządkowana krotka wierzchołków oraz obliczasz sumę wag krawędzi.
2. W przypadku, gdy algorytm przeglądający graf w głąb wycofuje się, to kasujesz oznaczenie wierzchołków jako odwiedzone.

Tak zmodyfikowany algorytm wypisze wszystkie możliwe cykle Hamiltona wychodząc z określonego wierzchołka. W przypadku grafów nieskierowanych nie ma znaczenia, z którego wierzchołka wyjdziesz. Dla grafów skierowanych możesz powtórzyć algorytm dla każdego wierzchołka, jednak wypisane cykle mogą się powtarzać.

W drugim etapie, mając wszystkie możliwe cykle Hamiltona, wybierasz cykl z najmniejszą sumą wag krawędzi i to jest rozwiązanie problemu komiwojażera. Oczywiście można połączyć te dwa etapy w jeden w taki sposób, że cykl Hamiltona zostanie wypisany tylko w jednym z dwóch przypadków:

1. Gdy jest to pierwszy znaleziony cykl Hamiltona.
2. Gdy poprzednio wypisany cykl miał większą sumę wag krawędzi.

W takim przypadku ostatni wypisany cykl Hamiltona będzie najkorzystniejszym rozwiązaniem zadania.

Myślę, że takie podejście będzie korzystniejsze niż badanie w ciemno wszystkich możliwych kolejności wierzchołków.

W przypadku założenia, że komiwojażer wyrusza z danego wierzchołka, zwiedza pozostałe, ale nie wraca do wierzchołka startowego, wystarczy znaleźć ścieżkę Hamiltona. Sposób rozwiązania jest taki sam z tą różnicą, że nie sprawdza się krawędzi łączącej ostatni wierzchołek z pierwszym i w grafie nieskierowanym może mieć znaczenie, z którego wierzchołka się wyrusza. W zadaniu nie jest to doprecyzowane, więc musisz się określić, czy zadanie polega na znalezieniu najlepszej ścieżki w ogóle, czy najlepszej ścieżki ze wskazanego wierzchołka. Jeżeli to drugie, to nie potrzeba powtarzać algorytmu dla każdego wierzchołka, również w grafie skierowanym.

Dziękuję wszystkim za pomoc!
Ogarnięte :)