Algorithmus zum Auffinden des minimalen Spannbaums der ausgewählten Knoten

Question

Man kann den Algorithmus von Prim oder den Algorithmus von Kruskal verwenden, um den minimalen aufspannenden Baum/Graph einer Sammlung von Scheitelpunkten/Knoten und Kanten/Verbindungen zu finden. Was ich jedoch möchte, ist ein Algorithmus, der das Minimum-Spanning-Diagramm dieser Sammlung findet, aber das resultierende Diagramm muss nur willkürlich ausgewählte Knoten anstelle aller Knoten enthalten. Es ist in Ordnung, wenn das resultierende Diagramm mehr Knoten enthält als nur die benötigten.

Gibt es einen solchen Algorithmus? Vielleicht könnte man den Algorithmus von Prim (oder Kruskal) einfach verwenden, nachdem man den Graph so modifiziert hat, dass er nur die benötigten Knoten enthält? Aber ich bin mir nicht sicher, wie ich den Graph ändern soll, um seine Verbundenheit aufrechtzuerhalten.

Zum Beispiel, sagen wir einen rautenförmigen Ausgang Graph haben (mit Kosten von Links in Klammern):

A 
(2)/ \(1) 
    B C 
(2)\ /(5) 
    D 

Nun wir willkürlich entscheiden, dass nur A und D benötigt werden Knoten. Wenn wir bei A anfangen, würden wir immer noch wollen, dass es den linken Weg nimmt, weil ((2 + 2) < (1 + 5)).

Sagen wir die Grafik leicht ändern:

A 
(2)/ \(1) (2) 
    B C ------E 
(2)\ /(5) 
    D 

Wenn wir, dass nur A, D entscheiden Knoten und E benötigt werden, erkennen wir, dass der Weg mit minimal Kosten nicht unbedingt derjenige mit dem geringsten Links. A - B - D und A - C - E kostet 7, aber A - C - D und C - E kostet 8.

Answer 1

Was Sie finden möchten, ist eine diskrete Steiner tree. Wenn nicht alle Scheitelpunkte im Diagramm obligatorisch sind, aber der Baum an den optionalen Scheitelpunkten aufgeteilt werden kann, ist das Problem NP-schwer.

Wikipedia sagt (oben verlinkt) dieses Problems: es wird angenommen, dass willkürlich gute Approximationsverhältnisse im Allgemeinen nicht in polynomieller Zeit erreicht werden können. Es gibt einen Polynomialzeit-Algorithmus, der einen Faktor von 1,39 für einen minimalen Steinerbaum findet.