Dies ist ein Hausaufgabenproblem, das mir gegeben wurde, und ich habe stundenlang mein Gehirn geharkt (also bin ich mit einigen Hinweisen zufrieden). Ich weiß bereits, dass das Approximationsverhältnis nicht schlechter als . Ich habe ein Raddiagramm, in dem jede Kante kostet und der Abstand zwischen allen Knoten, die nicht durch Kanten verbunden sind, beträgt . Der ist dieser:
Ich habe blau markiert, was meiner Meinung nach die Ausgabe eines heuristischen MST-Algorithmus ist. Ich denke aber auch, dass dies die optimale Lösung ist, da alle Knoten nur einmal besucht werden können. Die Kosten für die Tour wären also für Optimal und MST.
Ich sehe nicht, wie diese Art von Graph zeigt, dass die Approximationsgrenze der MST-Heuristik eng ist (nicht unbedingt diese Instanz, aber die Graphen im Allgemeinen). Kann mich jemand aufklären?
Antworten:
Der Algorithmus bietet viel Freiheit: mehrere minimale Spannbäume und mehrere entsprechende Eulersche Touren. Versuchen Sie, die schlechteste Wahl zu finden und zeigen Sie, dass dies zu einer minderwertigen Tour führt. Was Sie zeigen, dass der Algorithmus könnte diese Wahl machen, und so könnte eine schlechte Approximation erzeugen.
Wenn Ihnen diese Idee der Wahl nicht gefällt, können Sie manchmal garantieren, dass der Algorithmus die gewünschten Entscheidungen trifft, indem Sie die Gewichte leicht anpassen.
quelle
In der Grafik, die ich gepostet habe, fehlen einige Kanten. Benachbarte Knoten im Zyklus sollen verbunden sein. ( Bearbeiten : Das Diagramm wurde mit der TSP-Tour korrigiert.)
Das eigentliche Diagramm ist dies
Meine Lösung lautet wie folgt. Nun ist der für die MST-Heuristik berechnete MST offensichtlich
Erlaubt viele Euler-Touren, unter anderem diese:
Hier können die Zyklusknoten in beliebiger Reihenfolge besucht werden. Jetzt ist jede der Touren gültig, sodass wir zum Beispiel die schlechteste auswählen könnenv0,v4,v0,v1,v0,v3,v0,v6,v0,v2,v0,v5,v0 . Basierend auf dieser Tour findet die MST-Heuristik diese TSP-Lösung:
Jetzt haben da alle Kanten Kosten1 und und alle Knoten, die nicht in der Grafik verbunden sind, haben Abstand 2 Die Kosten für die Tour betragen 2 ( n - 1 ) + 2 wo die optimale Tour gekostet hätte n + 1 . Im Limit
quelle