Algo. für längsten Pfad in einem gerichteten Graph
hallo,
ich möchte nach dem längstem Pfad in einem gerichteten Graph suchen.
Input: ein gerichteter zyklenfreier Graph mit n Knoten und m Kanten. Kanten sind gewichtet.
Output: der längste Pfad
Ich habe seit zwei Tagen nach einem passenden Algo. gesucht. Leider habe ich ausser Dijkstra-Algorithmus nichts Passendes gefunden. Wobei ich den Algorithmus entsprechend umformieren muss. Es gibt auch Algorithmus von Floyd und Warshall und Bellman-Ford-Algorithmus. Ich dachte mir, dass Dejkstra meinem Problem am bessten passend ist.
habt ihr bitte eine andere Idee? oder ist meine Auswahl richtig?
Gruss
Burkut
Ich könnte dir noch die ACO (Ant Colony Optimization) empfehlen. Ist allerdings nur eine Heuristik. Haben wir in Algorithmen und Datenstrukturen mal implementiert. Bringt - wenn man es richtig macht - recht schnell gute Ergebnisse.
Wenn ich mich richtig erinnere, ist Backtracking dafür recht gut geeignet.
There are 10 kind of people, those who understand binary and those who don't.
Hallo burkut,
markiere alle Knoten mit der Weglänge 0.
Ermittle alle Knoten, in die keine Kanten hineinführen (da der Graph zyklenfrei ist, muss es mindestens einen solchen Knoten geben) und packe alle diese Knoten in eine Queue.
Hole den jeweils ersten Knoten (k) aus der Queue und markiere für jeden Knoten kn, der vom Knoten k aus durch eine Kante direkt erreichbar ist, mit dem Maximum der Weglänge von k plus eins und der Weglänge von kn. Wird die Weglänge von kn dadurch erhöht, pack kn ans Ende der Queue.
Mach das bis die Queue leer ist (da der Graph zyklenfrei ist, muss dieser Fall eintreten).
Den bzw. einen längsten Pfad bekommst du, wenn du von dem oder einem Knoten mit der höchsten Markierung ausgehend gegen die Richtung der Kanten jeweils einen Knoten suchst, dessen Weglänge um genau eins kleiner ist.
herbivore
hallo, danke für euere Tipps.
Ich habe mir die Algorithem, die von Euch vorgeschlagen mal angeschaut.
Es scheint mir, dass die beiden Algorithmen mehr kompliziert ist als als Djikstra. das hier mein angepasster Djikstra Algorithmus zur Suche nach dem länsgten Pfad:
1 function Dijkstra(Graph, Quelle):
2 for each Knoten v in Graph: // Variablen initialisieren
3 abstand[v] := 0 // Abstand der Quelle zu v
4 vorgänger[v] := null // Vorheriger Knoten auf dem Weg zu v
5 abstand[Quelle] := inf // Der Abstand der Quelle zu sich selbst ist
6
7 Q := Die Menge aller Knoten in Graph
8 NQ := Die Menge aller NachbarKnoten in Graph
9 VQ := Die Menge aller verarbeitet Knoten in Graph
10 nehme Quelle in NQ auf
11 while VQ nicht gleich Q: // Der eigentliche Algorithmus
12 u := Knoten in NQ mit größtem Wert in abstand[]
13 if abstand[u] = 0:
14 break // alle verbleibenden Knoten sind unerreichbar
15 entferne u aus NQ
16
17 for each nachbar v von u: // nur die v, die noch in Q enthalten sind.
18 alternativ := abstand[u] + abstand_zwischen(u, v) // abstand_zwischen bestimmt das
19 // Kantengewicht zwischen u und v
20 if alternativ > abstand[v]: // Verwende (u,v,a)
21 abstand[v] := alternativ
22 vorgänger[v] := u
23 if (v ist in VQ vorhanden)
24 entferne v aus VQ
25 nehme v in NQ auf
26 nehme u in VQ auf
27 return vorgänger[]
was sagt ihr dazu? ich möchte nur eine Lösung, keine Optimierung ist dabei verlangt.
Gruss
Burkut
Hi burkut,
Schau einfach mal bei Longest Path Problem vorbei. Dort ist auch noch ein Ansatz mit dynamischer Programmierung speziell für gerichtete azyklische Graphen.
(Neben dem allgemeinen Ansatz: "Kantengewichte negieren und Shortest-Path-Algo anwenden")
beste Grüße
zommi
Hole den jeweils ersten Knoten (k) aus der Queue und markiere für jeden Knoten kn, der vom Knoten k aus durch eine Kante direkt erreichbar ist, mit dem Maximum der Weglänge von k plus eins und der Weglänge von kn. Wird die Weglänge von kn dadurch erhöht, pack kn ans Ende der Queue.
was mache ich, wenn ich einen Knoten kn, der schon in der Queue ist, updated habe. Wobei mit Update meine ich nur mit grössere Pfadlänge.
Grüsse
burkut
Hallo burkut,
ob du erkennst, wenn ein Knoten schon in der Queue ist, hat nur Auswirkungen auf die Laufzeit nicht auf die Korrektheit. Du kannst es machen oder lassen. Die Ermittlung kostet ja auch Zeit. Was schneller ist, hängt von den Umständen ab. Mein Algorithmus war ja ohnehin auf Funktionalität gerichtet und nicht auf Performance.
herbivore
markiere alle Knoten mit der Weglänge 0.
Ermittle alle Knoten, in die keine Kanten hineinführen (da der Graph zyklenfrei ist, muss es mindestens einen solchen Knoten geben) und packe alle diese Knoten in eine Queue.
Hole den jeweils ersten Knoten (k) aus der Queue und markiere für jeden Knoten kn, der vom Knoten k aus durch eine Kante direkt erreichbar ist, mit dem Maximum der Weglänge von k plus eins und der Weglänge von kn. Wird die Weglänge von kn dadurch erhöht, pack kn ans Ende der Queue.
Mach das bis die Queue leer ist (da der Graph zyklenfrei ist, muss dieser Fall eintreten).
wenn ich dich richtig verstanden habe, meinst du etwa so:
Abs[v] = 0; // v ist ein Knote im Graph
startknoten ermitteln und in Queue Q einfügen // alle Knoten, die keine Vorgänger haben
solange Q nicht leer ist:
1. hole ersten k aus Q // hole den ersten Element in der Queue
2. finde alle Nachfolger NF von k raus
foreach kn in NF // durchlaufe alle Knoten
if (Abs[kn] +1+ Abs[k] > Abs[kn])
Abs[kn]=Abs[kn] +1+ Abs[k]
füge kn in Q ein // kn ist neuer Knoten mit längeren Pfad
entferne k aus Q;
wobei ich nicht ganz verstehe, warum da so eine 1 addiert wird.
Gruss
Burkut
Hallo burkut,
ist alles ok, bis auf die innere Anfrage. Da meine ich:
if (Abs[k] +1 > Abs[kn]) Abs[kn]=Abs[kk] +1
Plus eins, weil der Weg nach kn (über k) eben um eins länger ist, als der Weg nach k.
herbivore
Hi,
@herbivore
Kanten sind gewichtet.
Somit klappt das mit dem "+1" nicht.
ob du erkennst, wenn ein Knoten schon in der Queue ist, hat nur Auswirkungen auf die Laufzeit
Sicher? Ich meine, dass man bei deinem Algorithmus die Knoten immer in die Queue werfen muss, sonst ist die Korrektheit nicht sichergestellt.
Denn es hängt von der Reihenfolge ab.
Siehe Anhang: (alle Kanten mit Gewicht 1)
Wir fangen an mit Knoten 0. Sein erster nachfolger sei Knoten 1. Diesen updaten wir und schmeißen in die Queue. Jetzt updaten wir Knote 2 und schmeißen ihn in die Queue und entfernen 0.
Jetzt ist 1 dran und wir updaten die 3 und werfen ihn in die Queue. Jetzt wird 1 entfernt.
Jetzt updaten wir 2, welcher 1 updated.
Jetzt muss Knoten 1 wieder rein, weil sonst 3 nicht korrekt geupdatet wird von 1.
Und dieses neu in die Queue Einfügen muss ja dann für alle Nachfolger ebenfalls wieder passieren. Somit springt der Algo aus der linearen Laufzeitkomplexität heraus.
Deshalb auch nochmal der Verweis auf die Wiki: Longest Path Problem. Dort steht ja, dass bei diesem Ansatz vorher erst topologisch zu sortieren ist.
(Nur dann ist es ok, die Knoten genau einmal zu besuchen - eben in dieser Reihenfolge)
Man kann natürlich die topologische Sortierung gleich on-the-fly machen.
Der Algorithmus wäre dann:
Abs[k] = maximaler Abstand
Inc[k] = Anzahl eingehender Kanten (incoming)
w[i,j] = Kantengewicht von i nach j
für jeden Knoten Inc[k] bestimmen und Abs[k]=0 setzen.
startknoten ermitteln und in Menge M einfügen // alle Knoten mit Inc[k]==0
solange M nicht leer ist:
1. hole ersten k aus M
2. finde alle Nachfolger NF von k raus
foreach kn in NF
if (Abs[k] + w[k,kn] > Abs[kn]) // wenn länger als vorher, dann speichern
Abs[kn] = Abs[k] + w[k,kn];
Inc[kn]--; // einen Eingang haben wir gerade besucht
if(Inc[kn] == 0) // wenn kn keinen Vorgänger mehr hat (also nie mehr geupdatet wird)
füge kn in M ein // dann in die Menge einfügen
entferne k aus M;
beste Grüße
zommi
Hallo zommi,
Jetzt ist 1 dran und wir updaten die 3 und werfen ihn in die Queue. Jetzt wird 1 entfernt.
Jetzt updaten wir 2, welcher 1 updated.
Jetzt muss Knoten 1 wieder rein, weil sonst 3 nicht korrekt geupdatet wird von 1.
richtig, aber der Prüfung ging es doch nur darum zu verhindern, dass Knoten gleichzeitig mehrmals in der Queue sind. Das ist in deinem Beispiel durch den kursiven Punkt gar nicht der Fall.
Also ich habe jetzt keinen Beweis geführt, aber ich denke schon, dass meine Aussage, dass ein Knoten nicht mehrfach gleichzeitig in der Queue enthalten sein muss, stimmt.
herbivore
hallo Zommi,
vielen Dank für deine Vervollständigung des Algos. Ich habe heute morgen den Longst Path Algo auch gesehen. Es schien mir irgendwie komplizierter als den Algo von herbivore. Besonderes ist die topologische Sortierung. So habe ich einfach den Algo von herbivore implementiert. Es funktioniert auch. ....
sowie ich jetzt siehe, hast du völlig Recht.
Und dieses neu in die Queue Einfügen muss ja dann für alle Nachfolger ebenfalls wieder passieren. Somit springt der Algo aus der linearen Laufzeitkomplexität heraus.
Der vorherige Algo wird einen Knoten mehrfach in die Liste aufnehmen, und die Reste (die Nachfolger des wieder aufgenommen Knotens) müssen neu updated werden....usw.
Ich glaube, es beeinträchtigt nicht, dass der Algo. das richtige Ergebnis liefert.
Aber mit deinem vervollständigten Algo kann man noch besseres Ergebnis erzielen und in dem Sinne ist es vielleicht vergleichbar mit dem Longst Path Algo. oder?
Auf jeden Fall bedanke ich mich für Eure Mühe und Zeit.
viele Grüsse
Burkut
Hallo burkut,
Es schien mir irgendwie komplizierter als den Algo von herbivore. Besonderes ist die topologische Sortierung.
so schwer ist die nun auch nicht. Siehe Digraphen topologisch sortieren. Die Methode SortTopological kommt mit rund 25 echten Codezeilen aus.
herbivore
Hi nochmal,
dass Knoten _gleichzeitig _mehrmals in der Queue sind
Da hast du natürlich Recht 🙂 Das muss nicht.
Aber mehrmals über die Zeit hinweg (nicht gleichzeitig) müsste schon - der Reihenfolge der äußeren Schleife wegen.
Aber gut, dann sind wir uns da ja alle einig 😉
Der Algorithmus, der die Knoten in topologisch sortierter Reihenfolge durchgeht, ist aber dennoch effizienter im Sinne der asymptotischen Laufzeit.
noch besseres Ergebnis erzielen
Korrekt arbeiten tun beide.
und in dem Sinne ist es vielleicht vergleichbar mit dem Longst Path Algo. oder?
Alle geposteten Algos sind schon sehr nah an der Wiki-Implementierung dran.
Der Unterschied steckt eben lediglich im Durchgehen der Knoten.
a) Bei Herbivore haben wir eine variable Queue mit unsern zu besuchenden Knoten, wo immer wieder die Knoten reingepackt werden, die nochmal überprüft werden müssen.
b) Bei Wiki werden die Knoten einmalig in topologisch sortierter Reihenfolge durchlaufen, was garantiert, dass ein bereits besuchter Knoten nicht nochmal geupdatet werden muss (da er ja eben topologisch vor den anderen dran war)
Das ist der einzige Unterschied.
Nun zu meinem ergänzten Algo:
Im Gegensatz zum Ausgangsalgo lege ich nur dann neue Knoten in die Menge der zu besuchenden rein, wenn dieser keine eingehenden Kanten mehr hat. Der alte Algo hatte sie stets reingepackt.
Der Vorteil ist nun: so lange es noch eingehende Kanten gibt, wird dieser Knoten ja eh nochmal später als Nachfolger betrachtet werden. Also warum jetzt schon in die Queue werfen? Später werden wir ihn eh nochmal sehen.
Und erst, wenn wir vom letzten Vorgänger kamen (if(Inc[kn] == 0)), dann werfen wir den Knoten rein. (Deshalb das mitzählen der IncomingEdges)
Und das ist eben auch genau das selbe wie erst topologisch sortieren und dann den Wiki-Algo anwenden. Nur eben in einem Schritt. (Die Algos selbst sind von der Struktur nämlich ähnlich und somit prädestiniert, vereint zu werden)
Schau dir mal TopSort von herbivores Link an. Hat strukturelle Ähnlichkeiten mit unseren hier geposteten Algos. Auch dort gibts diese Mitzählung der eingehenden Kanten (wie bei mir) und wir starten mit den Knoten die keine eingehenden Kanten haben (wie bei herbivore)
Also: alles im Grunde das selbe, nur im Detail etwas anders 😁
beste Grüße
zommi
hallo Euch beiden,
ich danke Euch. Es hat mir viele geholfen.
Gruss
Burkut