Längste Pfad in DAG

Finden Sie den längsten Pfad in einem DAG, ich bin mir bewusst, dass der 2-algorithmen: algo 1: führen Sie eine topologische Sortierung + verwenden Sie dynamische Programmierung auf das Ergebnis der Sortierung ~ oder ~ algo 2: aufzählen aller Pfade in die DAG mit der DFS, und notieren Sie die längste. Es scheint, wie das auflisten aller Wege mit DFS hat eine bessere Komplexität als algo-1. Ist das wahr?

InformationsquelleAutor Frank | 2012-05-23
  1. 8

    Ihre zweite option ist falsch: die DFS nicht erforschen alle möglichen Wege, es sei denn, Ihr graph ein Baum oder ein Wald, und starten Sie von den Wurzeln. Der zweite Algorithmus, den ich kenne, ist die Negation der GEWICHTE und die Suche nach dem kürzesten Weg, aber es ist etwas langsamer als die top-Art + DP-Algorithmus, dass Sie gelistet als #1.

    • OK, ich meinte die DFS mit Neustart von jedem vertex, der noch nicht besucht worden, in der vorherigen DFS geht. Das erkunden der ganzen DAG. Sollte das nicht schneller sein als die topo Art + DP?
    • DFS mit Neustart von Scheitelpunkten, die noch nicht besucht wurde, wird nicht erforschen alle Pfade. Betrachten Sie einen Graphen A->B->C; Sie beginnen DFS von B ist, gehen Sie zu C, und stoppen; dann Neustart von A zu B gehen, und wieder stoppen, weil die Sie besucht haben, C schon. Beide Weg, der DFS gefunden, B-C und A-B sind von der Länge 1; das längste Pfad A-B-C ist der Länge 2.
    • Warum sollten Sie start aus B? Starten Sie die DFS von Quellen.
    • Auch wenn Sie beginnen, die Quellen zu betrachten einen Graphen mit Diamanten: A->B,C ; B->D ; C->D ; D->E,F ; E->G ; F->G. A ist eine Quelle, so dass Sie beginnen die Erkundung von es. Sie gehen A-B-D-E,G, gehen Sie zurück zu D versuchen A-B-D-F-G, gehen Sie zurück zu A versuchen A-C-D, und zu stoppen, weil D vollständig erforscht jetzt. Wenn der längste Pfad durch das Gewicht ist A-C-D-E-G DFS ist nicht zu finden.
    • OK, ich werde post einige Python-code, der es tut.
    • Es stellt sich heraus, dass der DAG (gerichtete azyklische graph) und Baum sind zwei Namen für die gleiche Sache.
    • Alle Bäume sind DAGs, aber nicht alle DAGs sind Bäume.
    • in der Tat, es war ein Fehler, sorry.
    • In Ihrem Beispiel, warum stop bei D in den zweiten Durchgang? DFS in der Regel nicht zu stoppen, weil ein vorheriger Besuch vollständig erforscht es.
    • Obwohl viele Implementierungen überspringen Sie diese "unwichtige" überprüfen, DFS-Algorithmus untersucht nicht vollständig untersucht vertixes.
    • Danke
    • ein DFS (auf einem DAG), die Etiketten der aktuellen erkundet Knoten mit max Gewicht Summe aus Ziel-und das Kind gab ihm dann den längsten Pfad. Man könnte sagen, dies ist bei der Dynamischen Programmierung in der Verkleidung.
    • und es ist die lineare Zeit, richtig?
    • Nein, es wird nicht linear sein, weil, wie pro die Art der DFS haben Sie zu besuchen einige Knoten mehr als einmal. In der Tat wird es sein, die exponentiell in der Anzahl der Ebenen in der DAG. Übrigens, ich beging einen Fehler, als ich vorher gesagt, dass die DFS auf einem DAG ist eine Art DP in der Verkleidung, die eindeutig ist es nicht, weil Sie besuchen die gleiche Knoten immer und immer wieder.
    • hmm ich denke es ist linear mit der richtigen Umsetzung: quora.com/.... Sehen Sie irgendein problem mit dieser Lösung?

    InformationsquelleAutor dasblinkenlight
  2. 3

    Aufzählen aller Pfade in einer DAG mit "DFS":

    def enumerate_dag(g):

  def enumerate_r(n, paths, visited, a_path = []):
    a_path += [n]
    visited[n] = 1
    if not g[n]:
        paths += [list(a_path)]
    else:
        for nn in g[n]:
            enumerate_r(nn, paths, visited, list(a_path))

  paths, N = [], len(g)
  visited = np.zeros((N), dtype='int32')

  for root in range(N):
    if visited[root]: continue
    enumerate_r(root, paths, visited, [])

  return paths
    • Haben Sie versucht, die übergabe eines Doppel-Diamant-graph zu diesem code? Es sieht aus wie es hat eine 50/50 chance fehlt den längsten Pfad.
    • Ich habe einfach versucht, mit: [[1,2],[3],[3],[4],[5,6],[7],[7],[8],[9],[]]. Ich bekomme 4 Wege: [[0, 1, 3, 4, 5, 7, 8, 9], [0, 1, 3, 4, 6, 7, 8, 9], [0, 2, 3, 4, 5, 7, 8, 9], [0, 2, 3, 4, 6, 7, 8, 9]], was ich glaube ist die richtige Antwort. So weit wie ich das beurteilen kann (von vielen anderen tests), ist dieser Algorithmus korrekt listet die Pfade in einer DAG. Topo-Sortierung basiert auf einem ganz ähnlichen Einsatz von DFS. Vorausgesetzt, Sie starten/neu starten an Quellen, DFS erkunden alle die Knoten erreichbar aus jeder Quelle, damit der code über ganz untersucht die DAG, kein Scheitelpunkt verpasst.
    • Ich missverstanden, die Verwendung von visited im code: Sie einzustellen, aber Sie tun es nicht verwenden, um zu entscheiden, ob Sie weiterhin sollten die traversal. Dies ist nicht das, was genannt DFS, da die DFS nicht besuchen Knoten, die vollständig erforscht. Der größte Unterschied zwischen DFS und Ihr code ist, dass dein code ist äußerst ineffizient. Wiederholen Sie die gleiche Diamant-Muster fünfzig mal zu sehen, was ich meine: dein Programm wird untersuchen, alle 2^50 Wege, und das ist eine Menge von Pfaden zu erkunden.
    • die Explorations-Strategie der DAG ist "DFS": es erweitert jeden Pfad in die Spüle, dann backtracks. Für "äußerst ineffizient", die Absicht IST, alle aufzuzählen, die Pfade für diese Funktion. Also ja, es hat zu besuchen, manche Knoten viele Male.
    • Aber ich kann sehen, wie das auflisten aller Wege zu finden, die längste ist die schlechte Komplexität im Vergleich zur topo Art + bestellen.
    • Aufzählung aller Pfade macht die Komplexität exponentiell, was den Algorithmus sehr viel nutzlos für den Allgemeinen Fall. Top-Art + DP Polynom, so ist der kürzeste Pfad auf negierte Kanten.
    • Ja, ich bin völlig einverstanden.
    • Das ist die Antwort, die ich gesucht hatte, die im Vergleich Komplexität der verschiedenen Ansätze. Ich war schläfrig, nicht sofort sehen, dass die Aufzählung war exponentiell.

    InformationsquelleAutor Frank
  3. 2

    Kein DFS benötigt.
    Algorithmus : nimmt eine DAG-G.
    Jeder Bogen besitzt eine variable E

    for each node with no predecessor :
    for each of his leaving arcs, E=1.
for each node whose predecessors have all been visited :
    for each of his leaving arcs, E=max(E(entering arcs))+1.

    max_path ist die höchste E innerhalb der Kanten, wenn alle Knoten verarbeitet wurden.

    InformationsquelleAutor Pyra
Schreibe einen Kommentar