Christofides-Algorithmus (von Hand)
On Februar 1, 2021 by adminIch folge diesem Algorithmusbeispiel: https://en.wikipedia.org/wiki/Christofides_algorithm#example
The graph:
[! [Bildbeschreibung hier eingeben] [1]] [1]
Calculate minimum spanning tree T:
[! [Bildbeschreibung hier eingeben] [2]] [2]
Calculate the set of vertices O with odd degree in T
Wie „the minimaler Spannbaum T „, da der Grad aller Eckpunkte ungerade ist.
Form the subgraph of G using only the vertices of O
(da alle ungerade waren, sollte dies den ursprünglichen Graphen ergeben) [! [ Geben Sie hier die Bildbeschreibung ein] [1]] [1]
Construct a minimum-weight perfect matching M in this subgraph
( Ich bin nicht sicher, ob ich hat dies richtig gemacht ) [! [Bildbeschreibung hier eingeben] [3]] [3]
Unite matching and spanning tree T ∪ M to form an Eulerian multigraph
[! [Bildbeschreibung hier eingeben] [4]] [4]
Dies ist definitiv nicht richtig.
Was ist schief gelaufen?
Kommentare
- Hinweis: Alle Bilder im Beitrag scheinen verschwunden zu sein. Hat der Autor zufällig die Originale?
Antwort
Tatsächlich Sie haben die ganze Zeit korrekt gearbeitet. Sie haben den Christofides-Algorithmus jedoch noch nicht fertiggestellt.
Der nächste Schritt ist „Euler-Tour berechnen“.
In das letzte Bild Sie haben einen Multigraph erhalten, dessen Scheitelpunkte gerade Grad haben. Es muss also einen Eulerschen Pfad haben. Wählen wir beispielsweise den Eulerschen Pfad A -> F -> A -> C -> B -> D -> E -> D -> A.
Der letzte Schritt lautet „Wiederholte Scheitelpunkte entfernen“ Wenn wir das zweite A und das zweite D auf dem obigen Pfad entfernen, erhalten wir eine gewünschte Ausgabe, A -> F -> C -> B -> D -> E -> A. Fertig.
Bitte beachten Sie, dass es nicht sehr sinnvoll ist, den Christofides-Algorithmus auf das angegebene Diagramm anzuwenden.
„Der Christofides-Algorithmus ist ein Algorithmus zum Finden von Näherungslösungen für das Problem des reisenden Verkäufers in Fällen, in denen die Entfernungen einen metrischen Raum bilden (sie sind symmetrisch und gehorchen der Dreiecksungleichung „. Die angegebenen Abstände gehorchen nicht der Dreiecksungleichung, da d (B, D) + d (D, E) = 1 + 4 < 6 = d (B. , E) Darüber hinaus wird der (direkte) Abstand zwischen A und B nicht angegeben, was Zweifel aufkommen lässt, ob dies überhaupt ein Problem für reisende Verkäufer ist.
Kommentare
- Ich bin neu in diesem Bereich, also danke für die Randnotizen! Ich habe einige Fragen: 1. Muss jeder Scheitelpunkt miteinander verbunden sein, damit er ein gültiger TSP ist? Ich meine, es ist immer noch möglich, eine " TSP " Route zu erstellen, auch wenn diese Route fehlt, also würde ich sagen, dass sie gültig ist – aber Ich habe mich vorher geirrt. 2. Denken Sie (oder wissen Sie), ob es möglich ist, die Gewichtung einiger Eckpunkte in meinem Diagramm so zu erhöhen, dass die Dreiecksungleichung eingehalten wird? Ich denke, dass chaotischere Grafiken besser in der Lage sind, Kartenszenarien der realen Welt darzustellen. ' Deshalb habe ich sie so erstellt, wie sie ist.
- 1. Sie können es als TSP behandeln, wenn Sie beispielsweise annehmen, dass alle fehlenden direkten Entfernungen zwischen Städten ausreichend groß oder einfach unendlich sind. Auf diese Weise wirken sich diese fehlenden Abstände nicht auf die Lösung aus. Es ist jedoch noch kein metrischer Raum. 2. Um der Dreiecksungleichung zu gehorchen, können Sie einfach 10 zu jeder von Ihnen angegebenen Entfernung hinzufügen und alle fehlenden Entfernungen auf 20 setzen.
- Dies ist nicht wahr: " Im letzten Bild haben Sie einen Multigraph erhalten, dessen Scheitelpunkte gerade Grad haben. " – Die Eckpunkte E, D, A und F haben einen ungeraden Grad.
- " Sie haben ein Multigraph ", ein Diagramm, das mehrere Kanten haben darf, dh Kanten mit derselben Endknoten. Es gibt zwei Kanten zwischen D und E. Es gibt zwei Kanten zwischen A und F.
- Sie können auch das Beispiel bei Wikipedia überprüfen. " Dies ist kein Euler-Pfad, da Sie einen Scheitelpunkt mehr als einmal in diesem Pfad besuchen. ". Beim Eulerschen Pfad geht es darum, jede Kante genau einmal zu besuchen. Sie sprechen über den Hamilton-Pfad.
Schreibe einen Kommentar