Algorytm Christofides (ręcznie)
On 1 lutego, 2021 by adminPostępuję zgodnie z tym przykładem algorytmu: https://en.wikipedia.org/wiki/Christofides_algorithm#example
The graph:
[! [tutaj wprowadź opis obrazu] [1]] [1]
Calculate minimum spanning tree T:
[! [Tutaj wprowadź opis obrazu] [2]] [2]
Calculate the set of vertices O with odd degree in T
To samo co „the minimalne drzewo rozpinające T „, ponieważ stopień wszystkich wierzchołków jest nieparzysty.
Form the subgraph of G using only the vertices of O
(ponieważ wszystkie były nieparzyste, powinno to dać nam oryginalny wykres) [! [ wprowadź tutaj opis obrazu] [1]] [1]
Construct a minimum-weight perfect matching M in this subgraph
( Nie mam pewności, czy czy to dobrze ) [! [tutaj wprowadź opis obrazu] [3]] [3]
Unite matching and spanning tree T ∪ M to form an Eulerian multigraph
[! [tutaj wprowadź opis obrazu] [4]] [4]
To zdecydowanie nie w porządku.
Co poszło nie tak?
Komentarze
- Uwaga: wydaje się, że wszystkie obrazy w poście zniknęły. Czy autor ma oryginały?
Odpowiedź
W rzeczywistości przez cały czas masz rację . Jednak nie ukończyłeś jeszcze algorytmu Christofidesa.
Następnym krokiem jest „Oblicz trasę Eulera”.
W ostatnie zdjęcie , otrzymałeś multigraf, którego wszystkie wierzchołki mają równe stopnie. Więc musi mieć ścieżkę Eulera. Na przykład wybierzmy ścieżkę Eulera A -> F -> A -> C -> B -> D -> E -> D -> A.
Ostatnim krokiem jest „Usuń powtórzone wierzchołki , dając algorytm „wyjście”.
Usuwając drugie A i drugie D na powyższej ścieżce, otrzymujemy pożądane wyjście, A -> F -> C -> B -> D -> E -> A . Gotowe.
Należy pamiętać, że zastosowanie algorytmu Christofidesa do danego wykresu nie ma większego sensu.
„Algorytm Christofides to algorytm do znajdowania przybliżonych rozwiązań dla problem komiwojażera , w przypadkach, gdy odległości tworzą przestrzeń metryczną (są symetryczne i są zgodne z nierównością trójkąta „. Podane odległości nie są zgodne z nierównością trójkąta, ponieważ d (B, D) + d (D, E) = 1 + 4 < 6 = d (B , E). Ponadto (bezpośrednia) odległość między A i B nie jest podana, co budzi wątpliwości, czy jest to w ogóle problem komiwojażera.
Komentarze
- Jestem w tym nowy, więc dziękuję za uwagi dodatkowe! Mam kilka pytań: 1. Czy każdy wierzchołek musi być połączony ze sobą, aby był prawidłowym TSP? Chodzi mi o to, że nadal można utworzyć trasę " TSP ", nawet jeśli brakuje tej trasy, więc powiedziałbym, że jest prawidłowa – ale Myliłem się wcześniej. 2. Czy myślisz (lub wiesz), czy możliwe jest zwiększenie wag niektórych wierzchołków na moim wykresie w taki sposób, aby był on zgodny z nierównością trójkąta ? Myślę, że bardziej niechlujnie wyglądające wykresy lepiej przedstawiają rzeczywiste scenariusze map, dlatego właśnie ' stworzyłem je takim, jakim jest.
- 1. Możesz potraktować to jako TSP, jeśli przyjmiesz na przykład, że wszystkie brakujące bezpośrednie odległości między miastami są wystarczająco duże lub po prostu nieskończone. W ten sposób te brakujące odległości nie wpłyną na rozwiązanie. Jednak nadal nie jest to przestrzeń metryczna. 2. Aby zachować zgodność z nierównością trójkąta, możesz po prostu dodać 10 do każdej określonej odległości i pozwolić, aby wszystkie brakujące odległości wyniosły 20.
- To nieprawda: " Na ostatnim obrazku otrzymałeś multigraf, którego wszystkie wierzchołki mają parzyste stopnie. " – Wierzchołki E, D, A i F mają nieparzysty stopień.
- " Otrzymałeś multigraf ", wykres, który może mieć wiele krawędzi, czyli krawędzie, które mają takie same węzły końcowe. Pomiędzy D i E. istnieją dwie krawędzie. Pomiędzy A i F. Są dwie krawędzie.
- Możesz także sprawdzić przykład w Wikipedii . " To nie jest ścieżka Eulera, ponieważ odwiedzasz wierzchołek więcej niż raz na tej ścieżce ". Ścieżka Eulera polega na odwiedzeniu każdej krawędzi dokładnie raz. Mówisz o ścieżce Hamiltona.
Dodaj komentarz