Optimierungen für längste Wege problem in zyklischen Graphen

Welche Optimierungen existieren für auf der Suche nach dem längsten Pfad in einem zyklischen graph?

Längste Pfad in die zyklische Graphen bekannt ist NP-vollständig. Was Optimierungen und Heuristiken kann die Suche nach dem längsten Pfad schneller als DFSing die gesamte Grafik? Gibt es probabilistische Ansätze?

Ich habe einen Graphen mit bestimmten Eigenschaften, aber ich bin auf der Suche nach einer Antwort auf diese in den Allgemeinen Fall. Verknüpfen Papiere wäre fantastisch. Hier ist eine unvollständige Antwort:

  1. Bestätigen, es ist zyklisch. Längste Wege in azyklischen Graphen leicht berechnen mit dynamischer Programmierung.

  2. Finden Sie heraus, ob der graph planar (welcher Algorithmus ist der beste?). Wenn es wird, könnte man sehen, ob es ein block-Diagramm, ptolemäische Graphen, oder Kakteen-graph und Anwendung der Methoden in dieses Papier.

  3. Finden Sie heraus, wie viele einfache Zyklen gibt es mit Donald B Johnson ' s Algorithmus (Die Java-Implementierung). Sie können ändern zyklische Graphen in ein azyklisches man durch das entfernen einer Kante in einem einfachen Zyklus. Sie können dann die dynamische Programmierung Lösung gefunden die Wikipedia-Seite. Für Vollständigkeit, Sie hätte zu tun, das N-mal für jeden Zyklus, wobei N die Länge des Zyklus. Also, für ein gesamtes Diagramm, die Anzahl der Zeiten, die Sie ausführen müssen, der DP-Lösung ist gleich dem Produkt der Längen aller Zyklen.

  4. Wenn Sie DFS-die gesamte Grafik, die Sie beschneiden können einige Wege durch die Berechnung der "Erreichbarkeit" der einzelnen Knoten im Voraus. Diese Erreichbarkeit, die ist vor allem geeignet, um gerichtete Graphen, ist die Anzahl der Knoten jeder Knoten erreichen kann, ohne Wiederholungen. Es ist das maximum, das die längste Pfad von diesem Knoten sein könnte. Mit diesen Informationen, wenn Sie Ihre aktuellen Pfad und die Erreichbarkeit der untergeordneten Knoten ist kleiner als die längste, die Sie bereits gefunden habe, es gibt keinen Punkt in diesem Zweig, wie es unmöglich ist, dass Sie finden würde, einen längeren Weg.

  • Hat (3) beziehen sich auf finden von starken zusammenhangskomponenten? (en.wikipedia.org/wiki/Strongly_connected_component) - wenn nicht, würde ich gedacht haben, Sie könnten etwas tun mit denen. Ich fand Tarjans Algorithmus relativ einfach zu verstehen.
  • Ich weiß es ehrlich gesagt nicht sehen, wie die Identifizierung von stark miteinander verbundenen Komponenten oder vertex contraction hilft LPP lösen, aber ich könnte falsch sein. Zwingen ihn in einen azyklischen Graphen, ich glaube, Sie müssen die einfache Zyklen (Johnson ' s), da kann es noch werden Zyklen in der starken zusammenhangskomponenten.
  • vielleicht ist es noch nicht helfen. Mein Gedanke war, dass die SCCs sind in der Regel kleiner als das gesamte Diagramm, so finden sich die längsten Routen, die durch Sie für jeden entry/exit-pair-Mädchen sollte auch relativ schnell. Entfernen Sie die SCCs und füge eine gewichtete Kante, anstatt für jede dieser längsten Strecke-durch-SCC-Lösungen und Sie sollten am Ende mit eine azyklische digraph, dass Sie tun können dynamische Programmierung auf. Jeder der längsten route, die durch die SCC-edge tatsächlich ersetzt eine Kante, trat der SCC und eine Kante, die linke, als auch die route durch das SCC selbst. Ich kann etwas fehlt, aber.
  • Der längste Weg könnte durch eine SCC-mehr als einmal (aber noch ohne den Besuch jeder Knoten mehr als einmal). Ich glaube nicht, dass es einen Weg gibt, um für dieses Konto ohne die Erweiterung des SCC.
  • Wie kann man den längsten Pfad durch eine SCC-mehr als einmal? Wenn Sie Faktor aus der SCCs, das Ergebnis ist eine azyklische graph - also, wenn Sie exit ein, SCC, es gibt keinen Weg, um zu Ihr zurückkehren. Wenn es eine solche route, die Sie entdeckt hätten eine größere SCC. Vielleicht ich sollte haben darauf hingewiesen, dass algorithmen wie Tarjans finden Sie die maximale SCCs, nicht irgendein SCCs?
Schreibe einen Kommentar