Ich habe ein Hausaufgabenproblem und ich weiß nicht, wie ich es lösen soll. Wenn Sie mir eine Idee geben könnten, wäre ich sehr dankbar.
Das ist das Problem: "Ihnen wird ein zusammenhängender ungerichteter Graph gegeben, der N Ecken und N Kanten hat. Jeder Scheitelpunkt hat Kosten. Sie müssen eine Teilmenge von Scheitelpunkten finden, so dass die Gesamtkosten der Scheitelpunkte in der Teilmenge minimal sind und jede Kante mit einfällt mindestens einen Eckpunkt aus der Teilmenge. "
Vielen Dank im Voraus!
PS: Ich habe schon lange über eine Lösung nachgedacht, und die einzigen Ideen, die ich mir ausgedacht habe, sind Backtracking oder eine minimale Kostenanpassung in bipartiten Graphen, aber beide Ideen sind zu langsam für N = 100000.
Dies kann in linearer Zeit durch dynamische Programmierung gelöst werden.
Ein zusammenhängender Graph mit N Ecken und N Kanten enthält genau einen Zyklus. Beginnen Sie mit der Erkennung dieses Zyklus (mit Hilfe der Tiefensuche).
Entfernen Sie dann eine Kante in diesem Zyklus. Zwei an dieser Kante einfallende Vertices sind u und v . Nach dieser Kantenentfernung haben wir einen Baum. Interpretiere es als einen verwurzelten Baum mit der Wurzel u .
Die dynamische Programmwiederholung für diesen Baum kann folgendermaßen definiert werden:
Hier ist k die Knotendichte (Entfernung von der Wurzel), w 0 ist die Kosten des Unterbaums beginnend mit dem Knoten w Wenn w nicht in der "Teilmenge" ist, sind w 1 die Kosten des Teilbaums beginnend mit dem Knoten w wenn w in der "Teilmenge" ist.
Für jeden Knoten sollten nur zwei Werte berechnet werden: w 0 und w 1 . Aber für Knoten, die im Zyklus waren, benötigen wir 4 Werte: w i, j , wobei i = 0 ist, wenn der Knoten v nicht in der "Teilmenge", i = 1, wenn Knoten v in der "Teilmenge" ist, j = 0, wenn der aktuelle Knoten nicht in der "Teilmenge" ist, j = 1, wenn der aktuelle Knoten in der "Teilmenge" ist .
Die optimalen Kosten der "Teilmenge" werden als min ( u 0,1 , u 1,0 , u 1,1 ). Um die "Teilmenge" selbst zu erhalten, speichern Sie Rückzeiger zusammen mit jeder Teilbaumkosten und verwenden Sie sie, um die Teilmenge zu rekonstruieren.
Da die Anzahl der Kanten streng gleich ist, ist es nicht das übliche Vertex-Coverage-Problem Das ist NP-Complete. Ich denke, hier gibt es eine polynomische Lösung:
Ein N Knoten und (N-1) Kanten Graph ist ein Baum. Ihr Graph hat N Ecken und N Kanten. Finden Sie zuerst die schreckliche Kante, die eine Schleife verursacht und machen Sie das Diagramm zu einem Baum. Sie könnten DFS verwenden, um die Schleife zu finden ( O(N) ). Das Entfernen einer der Kanten in der Schleife würde einen möglichen Baum ergeben. In extremem Zustand würden Sie N mögliche Bäume bekommen (der rohe Graph ist ein Kreis).
Wenden Sie einen einfachen dynamischen Planungsalgorithmus ( O(N) ) auf jeden möglichen Baum ( O(N^2) ) an und suchen Sie dann den mit den geringsten Kosten.