Min. Gewichtete Kantenabdeckung - ist der gierige Algorithmus nicht optimal?
Der Beitrag hier: Das Lösen der minimalen Kantenabdeckung mithilfe des Maximum-Matching-Algorithmus bietet eine Möglichkeit, die minimale Kantenabdeckung aus einer maximalen Übereinstimmung zu erhalten, indem Kanten gierig über die maximale Übereinstimmung hinzugefügt werden, bis alle Scheitelpunkte abgedeckt sind. Wenn man nun über das Problem der min-gewichteten Kantenabdeckung nachdenkt, scheint es, dass dieser Ansatz erweitert werden kann. Suchen Sie zuerst die minimale gewichtete Übereinstimmung mit den maximalen Kanten und fügen Sie dann gierig Kanten mit dem kleinsten Gewicht hinzu, zuerst die mit dem kleinsten Gewicht.
Beim Lesen von Abschnitt 19.3 des Buches "Kombinatorische Optimierung: Polyeder und Effizienz" von Schrijver wird jedoch ein komplizierterer Algorithmus vorgestellt. Dies lässt es scheinen, als ob mein Ansatz oben nicht optimal ist. Ist es möglich, ein Gegenbeispiel zu finden, vorzugsweise in einem zweigeteilten Diagramm, in dem mein gieriger Algorithmus keine optimale Lösung liefern würde? Ich konnte keine mit einigen Spielzeuggraphen finden.
Antworten
Hier ist ein Gegenbeispiel zu Ihrem vorgeschlagenen Algorithmus:
Die optimale Lösung besteht aus 3 Kanten und kostet 3 + 1 + 1 = 5, aber die minimale Kosten-Maximum-Kardinalitätsanpassung, die aus 2 Kanten besteht und 3 + 3 = 6 kostet, wird im ersten Schritt Ihres Algorithmus ausgewählt und sofort zurückgegeben, da es bereits eine Lösung ist. (Die einzige andere maximale Kardinalitätsübereinstimmung kostet 1 + 6 = 7.)