Minimal Kosten stark verbunden digraph

StackOverflow https://stackoverflow.com/questions/1536067

Frage

I einen Digraph hat, die stark verbunden ist (das heißt es gibt einen Pfad von i zu j und j auf i für jedes Paar von Knoten (i, j) in dem Graphen G). Ich mag ein stark zusammenhängenden Graphen aus diesem Graphen finden, so dass die Summe aller Kanten ist die am wenigsten.

Um es anders zu sagen, ich brauche so loswerden Kanten zu bekommen, dass sie nach dem Entfernen wird der Graph noch stark verbunden werden und von den geringsten Kosten für die Summe von Kanten.

Ich denke, es ist ein NP schwieriges Problem. Ich suche nach einer optimalen Lösung, nicht Näherung für eine kleine Menge von Daten wie 20 Knoten.

Bearbeiten

Eine allgemeinere Beschreibung: Bei einem grap G (V, E) findet einen Graphen G ‚(V, E‘), so dass, wenn es existiert, die einen Weg von v1 zu v2 in G als auch einen Weg zwischen v1 existiert und v2 in G ‚und Summe jedes ei in E‘ ist eine möglichst geringe. so sein ähnlich mindestens gleichwertig Graphen zu finden, nur hier wollen wir die Summe der Kantengewichte minimieren, anstatt Summe von Kanten.

Edit:

Mein Ansatz so weit: Ich dachte, es zu lösen TSP unter Verwendung mit mehreren Besuchen, aber es ist nicht richtig. Mein Ziel hier ist es, jede Stadt zu decken aber einen minimalen Kosten Pfad. Also, es ist eher wie das Cover-Set Problem, ich denke, aber ich bin nicht ganz sicher. Ich bin verpflichtet, jeden und jede Stadt mit Pfaden, deren Gesamtkosten zu decken minimal ist, so besuchen bereits besuchten Wege mehrmals, um die Kosten nicht hinzuzufügen.

War es hilfreich?

Lösung

Ihr Problem ist bekannt als minimale Spann starke Unter (di) Graph (MSSS) oder, allgemeiner, minimalen Kosten Spanning sub (di) Graph und ist NP-hard in der Tat . Siehe auch ein anderes Buch: Seite 501 und Seite 480

Ich würde beginnen mit allen Kanten zu entfernen, die die Dreiecksungleichung nicht erfüllen - Sie Rand a entfernen -> c wenn das Gehen a -> b -> c billiger ist. Das erinnert mich an TSP, aber nicht wissen, ob das führt überall.

Meine vorherige Antwort war die Chu-Liu / Edmonds Algorithmus welche löst zu verwenden Arborescence Problem; wie Kazoom und ShreevatsaR wies darauf hin, das nicht hilft.

Andere Tipps

Ich würde versuchen, dies in einer dynamischen Programmierung Art und Weise.

0- setzen Sie die Grafik in eine Liste

1- machen eine Liste der neuen Subgraphen jedes Graphen in der vorherigen Liste, wo Sie eine andere Kante für jeden der neuen Subgraphen entfernen

2- Duplikate entfernen aus der neuen Liste

3- entfernen Sie alle Grafiken aus der neuen Liste, die nicht stark verbunden ist,

4- vergleichen die beste Grafik aus der neuen Liste mit den aktuellen besten, wenn besser, setzen neue aktuelle beste

5-, wenn die neue Liste leer ist, am besten die aktuelle ist die Lösung, sonst, recurse / loop / goto 1

In Lisp, könnte es vielleicht so aussehen: 

(defun best-subgraph (digraphs &optional (current-best (best digraphs)))
  (let* ((new-list (remove-if-not #'strongly-connected
                                  (remove-duplicates (list-subgraphs-1 digraphs)
                                                     :test #'digraph-equal)))
         (this-best (best (cons current-best new-list))))
    (if (null new-list)
        this-best
        (best-subgraph new-list this-best))))

Die Definitionen von strongly-connected, list-subgraphs-1, digraph-equal, best und better sind für den Leser als Übung.

Dieses Problem entspricht das hier beschriebene Problem: http: // www .facebook.com / careers / puzzles.php? puzzle_id = 1

Ein paar Ideen, die mir geholfen, die berühmten facebull Rätsel zu lösen:

Preprocessing Schritt:

  1. Pruning: Entfernen Sie alle Kanten a-b, wenn es billiger oder mit den gleichen Kosten Pfad, zum Beispiel:. A-c-b

  2. Graph Zersetzung: Sie können Subprobleme lösen, wenn der Graph Anlenkpunkte hat

  3. Merge Scheitel in einen virtuellen Scheitelpunkt, wenn es nur eine abgehende Kante.

Berechnung Schritt:

  1. Get Näherungslösung der gerichteten TSP mit wiederholten Besuchen verwenden. Verwendung Floyd Warshall und löst dann Zuordnungsproblem O (N ^ 3) unter Verwendung ungarische Methode. Wenn wir einmal Zyklus bekommen - es ist gerichtet TSP Lösung, wenn nicht - Verwendung Branch and Bound TSP. Danach haben wir obere Schranke Wert haben -. Den Zyklus des minimalen Kosten

  2. Exakte Lösung - Branch and Bound-Ansatz. Wir entfernen die Spitzen aus dem kürzesten Zyklus und versuchen zu bauen stark zusammenhängenden Graph mit weniger Kosten, als obere Grenze.

Das ist, alle Leute. Wenn Sie Ihre Lösungen testen wollen - probieren Sie es hier: http://codercharts.com/puzzle/caribbean-salesman

Sounds wie Sie die Dijkstra-Algorithmus

Es scheint, wie das, was Sie im Grunde wollen, ist eine optimale Lösung für die Reise-Verkäufer, wo es erlaubt ist, für die Knoten mehr als einmal besucht werden.

Edit:

Hmm. Könnten Sie dies über jeden Knoten im Wesentlichen durch lösen i laufen und dann ein Minimum tun, um die Kanten Spanning zeigen Baum von allen , dass der Knoten i, mit einem anderen minimalen Spannbaum aller Kanten unioned zeigen weg von diesem Knoten?

A 2-Annäherung an die minimal stark verbundenen Subgraphen erhalten wird, indem man eine Vereinigung einer minimal in-Verzweigung und minimal out-Verzweigung, wurzelt sowohl am selben (aber beliebigen) Scheitel.

Ein out-Verzweigung , auch bekannt als arborescence , ist ein gerichteter Baum an einem einzelnen Scheitelpunkt verwurzelt alle Vertices überspannt. Ein In-Verzweigung ist das gleiche mit reverser Kanten. Diese können von Edmonds' Algorithmus rechtzeitig gefunden werden O (VE) , und es gibt speedups zu O (E log (V)) (die Wikiseite ). Es gibt sogar eine Open-Source-Implementierung .

Die ursprüngliche Referenz für das 2-Näherungsergebnis ist das Papier durch JaJa und Frederickson , aber das Papier ist nicht frei zugänglich.

Es gibt sogar eine 3/2 Annäherung von Adrian Vetta (PDF) , aber komplizierter als die oben.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top