Diskussion:Algorithmus von Christofides

Die Heuristik ist hier zwar korrekt dargestellt und die Schritte werden korrekt wiedergegeben.

Aber erstens wird ein Erst-Anwender sicher nicht daraus schlau und zweitens fehlt ein Hinweis darauf, dass diese Heuristik beim Suchen des "perfekten minimalen Matchings" wieder ein Variationsproblem lösen muss, dass bei genügend großer Anzahl von Knoten ungeraden Grades keine leichte Aufgabe ist!

Wird das oben genannte Matching nicht zuverlässig gefunden, kann für die Güte von max 50% über Optimum keine Garantie gegeben werden!

Desweiteren wäre ein Beispiel nicht schlecht...

Ein formaler Beweis findet sich unter http://troy.troy.org/cs170/week13.pdf. Der Beweis lässt sich aber auch leichter nachvollziehbar grafisch erklären, indem man beispielsweise erklärt, dass es (mindestens) ein "Komplementärmatching" gibt, das für die Abschätzung mit der Dreiecksungleichung jede Kante des minimal aufspannenden Baums definitiv nur einmal nutzt.

Ein einfaches Beispiel zur Konstrukion steht unter [1] zur Verfügung und dürfte gerne verwendet werden.

In diesem Sinn...

Hopferuh

-- 92.193.81.12 00:05, 24. Jan. 2008 (CET)

Moin, ich hatte den Artikel damals wirklich nur als "Anfang" angelegt, weil ich selbst nicht vom Fach bin. Ich bin Stochastiker, also schon ein Stück weit von Optimierung entfernt. Wenn du Zeit und Lust hast, um selbst ein paar Erweiterungen in den Artikel zu bringen: Hau rein. Ich selbst werde dazu aber keine Zeit haben. Bei Fragen stehe ich dir aber natürlich gern zur Verfügung - und wer weiß, vielleicht liest ja noch ein Experte mit. :) Gruß --Scherben 09:26, 24. Jan. 2008 (CET)

Konfiguration des Graphen

Kann der Algorithmus mit Graphen $G=\left(V,E\right)$ umgehen, für die $\left\{v_{1},v_{2}\right\}\in E$, $\left\{v_{2},v_{3}\right\}\in E$, aber $\left\{v_{1},v_{3}\right\}\notin E$? Oder werden solche Eingaben durch die Forderung, dass der Graph metrisch sein soll, bereits unterbunden? Die Erweiterung zu einem vollständigen Graphen $G^{'}=\left(V,E^{'}\right)$ mit $\left\{u,v\right\}\in E^{'}\forall u,v\in V$ und Kantengewicht $c_{e}=\infty$ für Kanten $e\notin E$ ist ja nicht metrisch, da $c_{\left\{v_{1},v_{3}\right\}}=\infty >c_{\left\{v_{1},v_{2}\right\}}+c_{\left\{v_{2},v_{3}\right\}}$. --92.226.147.54 12:03, 23. Feb. 2015 (CET)

Du hast es ja schon selbst beantwortet: Für solche Graphen funktioniert es nicht, die "Abkürzungen" könnten ja beliebig lang werden... Zuzufügen ist noch, dass es vermutlich für keine Konstante c irgendeinen polynomialen c-Approximationsalgorithmus für das allgemeine TSP (ohne Dreiecksungleichung) gibt. Andernfalls hätte man auch exakte Polynomzeit-Algorithmen für alle NP-vollständigen Probleme, z.B. für das TSP selber.Graf Alge (Diskussion) 15:16, 9. Nov. 2015 (CET)