Ich bezweifle sehr, dass Sie den Prim-Algorithmus so modifizieren können, dass er für dieses Problem funktioniert, weil negative Zahlen ihn komplett verändern. Wenn es Ihnen gelingt, ein negatives Ergebnis zu erhalten, muss der absolute Wert maximiert werden, was bedeutet, dass die Kanten mit den höchsten absoluten Werten verwendet werden müssen, um ein von Prims algo gefundenes Ergebnis zu optimieren und das Protokoll (abs ()) zu verwenden nicht funktionieren, es sei denn, es ist unmöglich, ein negatives Ergebnis zu erhalten, dann wird dies tatsächlich die beste Lösung zurückgeben.
Dies macht das Problem etwas einfacher, weil wir nur nach der besten negativen Lösung suchen müssen und wenn wir keine finden, verwenden wir Prims mit log (abs ()).
Wenn wir jedem Scheitelpunkt einen Wert von 1 zuweisen, können zwei Scheitelpunkte zusammengeführt werden, indem ein neuer Scheitelpunkt mit allen Kanten der beiden Scheitelpunkte mit Ausnahme desjenigen, der sie verbindet, erstellt wird. Der Wert ist das Produkt der Werte der entfernten Scheitelpunkte und Kante.
Auf dieser Basis können wir anfangen zu vereinfachen, indem wir alle Knoten mit nur einer Kante zusammenführen. Parallel zu jedem Zusammenführungsschritt muss die entfernte Kante markiert werden, wie sie im ursprünglichen Diagramm verwendet wurde, so dass der Baum am Ende aus den markierten Kanten rekonstruiert werden kann.
Zusätzlich können wir alle Knoten mit nur positiven oder nur negativen Kanten zusammenführen, wobei die Kante mit dem höchsten absoluten Wert entfernt wird. Nach dem Zusammenführen kann der neue Knoten mehrere Verbindungen zum selben Knoten haben, Sie können alle außer der negativen und positiven Flanke mit dem höchsten absoluten Wert verwerfen (also max 2 Kanten zum selben Knoten). Übrigens. Sobald wir zwei Kanten zum selben Knoten haben (nach den obigen Entfernungsbedingungen), wissen wir, dass eine Lösung & lt; = 0 existieren muss.
Wenn Sie einen Knoten haben und dieser negativ ist, wurde das Problem erfolgreich gelöst. Wenn es positiv ist, gibt es keine negative Lösung. Wenn wir eine Null haben, können wir die übrigen Knoten in beliebiger Reihenfolge zusammenführen. Es ist wahrscheinlicher, dass wir einen hochgradig verbundenen Graphen haben, in dem jeder Knoten mindestens eine negative und eine positive Flanke hat. Wenn wir eine ungerade Anzahl von negativen Scheitelpunkten haben, wollen wir die Knoten mit einer geraden Anzahl von negativen Kanten zusammenführen und umgekehrt.
Immer an der Kante mit dem höchsten absoluten Wert zusammenführen. Wenn der resultierende Vertex & lt; = 0 ist, dann haben Sie die beste Lösung gefunden. Sonst wird es kompliziert. Sie können alle unbenutzten Kanten betrachten, versuchen, sie hinzuzufügen, sehen, welche Kanten entfernt werden können, um sie wieder zu einem Baum zu machen, nur die mit anderen Vorzeichen betrachten und das Verhältnis abs (added_edge / removed_edge) erstellen. Dann tue endlich die Änderung mit dem besten Verhältnis (wenn du irgendeine Kombination mit entgegengesetzten Zeichen gefunden hast, sonst gibt es keine negative Lösung). Aber ich bin mir nicht 100% sicher, ob das immer das beste Ergebnis bringen würde.