Fragen zu Kapitel 4

[yourmaninamsterdam]

Hallo,

ich poste mal die Fragen zu Kapitel, die bei mir noch offen sind, hier, damit jeder was von den Antworten hat, sollten welche auftauchen!

1. (S. 142) Wie kommt man darauf, dass die Yen-Variante nur n/2 Durchläufe braucht?
2. (S. 143) Ist die Deque-Variente eine Modifikation des Bellman-Ford-Algorithmus (oder eher eigenständig)? Falls ja, wie würde man das in den Algorithmus einfügen?
3. (S. 144) Was ist unter permanent gelabelten Knoten in Label-Correcting-Algorithmen zu verstehen?
4. (S. 144) Mit welchem Verfahren entdeckt man Zyklen in O(n)? Verstehe ich richtig, dass der Vorteil der Methode darin besteht, dass man nicht erst am Ende des Algorithmus (z. B. nach n-1 Durchläufen bei Bellman-Ford) testen kann, sondern schon zwischendurch?
5. (S. 146) Woher kommt das n² in der Laufzeit? Wegen allen Knotenpaaren?

Grüße
Artjom

[Andi]

Ich habe auch noch eine: Auf Folie 109 steht "Label setting algorithms are applicable only to directed acyclic graphs (DAGs) OR to graphs with non-negative arc lengths". Jedoch ist auf Folie 133 schon ein Beispiel angegeben für einen DAG wo Dijkstra nicht funktioniert, oder?

[Arki]

Hallo,

ich poste mal die Fragen zu Kapitel, die bei mir noch offen sind, hier, damit jeder was von den Antworten hat, sollten welche auftauchen!

1. (S. 143) Ist die Deque-Variente eine Modifikation des Bellman-Ford-Algorithmus (oder eher eigenständig)? Falls ja, wie würde man das in den Algorithmus einfügen?

So wie ich das verstanden habe, gibt es im Endeffekt zwischen FIFO Label-Correcting und Bellman-Ford keine nennenswerten Unterschiede. Die Dequeue-Variante ist im Endeffekt eine Modifikation des FIFO Label-Correcting Algorithmus. Dein CORRECT sieht etwas anders aus, da du ja - je nach Situation - Knoten an den Anfang oder das Ende der Queue stellst.

[*] (S. 144) Was ist unter permanent gelabelten Knoten in Label-Correcting-Algorithmen zu verstehen?

Die Knotenlabels sind während der Ausführung des Algorithmus *nicht* permanent. Sie werden erst in Iteration n-1 zu permanenten Knotenlabels.

[*] (S. 144) Mit welchem Verfahren entdeckt man Zyklen in O(n)? Verstehe ich richtig, dass der Vorteil der Methode darin besteht, dass man nicht erst am Ende des Algorithmus (z. B. nach n-1 Durchläufen bei Bellman-Ford) testen kann, sondern schon zwischendurch?

Du kannst natürlich on-the-fly testen. Das ist dann möglich, wenn du C (maximaler Wert über alle Kantenkosten) kennst, denn ein kürzester Weg kann ja aus nicht mehr als n-1 Kanten bestehen. Ergo hast du nen positiven (negativen) Zyklus, wenn das Distanzlabel d(v) > nC bzw. d(v) < -nC wird.

[*] (S. 146) Woher kommt das n² in der Laufzeit? Wegen allen Knotenpaaren?[/list]

Du führst Bellman-Ford für jeden Knoten v \in V aus.

Grüße,
Markus

[Arki]

Ich habe auch noch eine: Auf Folie 109 steht "Label setting algorithms are applicable only to directed acyclic graphs (DAGs) OR to graphs with non-negative arc lengths". Jedoch ist auf Folie 133 schon ein Beispiel angegeben für einen DAG wo Dijkstra nicht funktioniert, oder?

Ich stimme dir zu. Dijkstra kann natürlich auch auf DAGs versagen, wenn negative Kantenkosten im Spiel sind.

[Stille]

Ich habe auch noch eine: Auf Folie 109 steht "Label setting algorithms are applicable only to directed acyclic graphs (DAGs) OR to graphs with non-negative arc lengths". Jedoch ist auf Folie 133 schon ein Beispiel angegeben für einen DAG wo Dijkstra nicht funktioniert, oder?

Das ist eine allgemeine Aussage, die nicht speziell auf den Standard-Dijkstra zu beziehen ist. Konkret gemeint ist hier eine Variante, die die Knoten in der Reihenfolge einer topologischen Sortierung betrachtet, und einen Knoten erst dann permanent labelt, wenn er keine noch nicht betrachtete eingehende Kante mehr hat. Das Verfahren funktioniert so ähnlich wie in Aufgabe 4.1 längste Wege in Linearzeit mithilfe der topologischen Sortierung berechnet werden. Und die existiert eben nur auf DAGs.

[yourmaninamsterdam]

So wie ich das verstanden habe, gibt es im Endeffekt zwischen FIFO Label-Correcting und Bellman-Ford keine nennenswerten Unterschiede. Die Dequeue-Variante ist im Endeffekt eine Modifikation des FIFO Label-Correcting Algorithmus. Dein CORRECT sieht etwas anders aus, da du ja - je nach Situation - Knoten an den Anfang oder das Ende der Queue stellst.

Der Bellman-Ford-Algorithmus verwendet gar keine Queues... Genausowenig die CORRECT-Prozedur.
Das ist auch der Grund, warum ich die FIFO- und Deque-Varienten eher für Implementierungen des modifizierten Label-Correcting-Algorithmus halte und nicht direkt für Varienten des Bellman-Ford-Algorithmus'. Die Folien sind diesbezüglich nur etwas seltsam angeordnet.

Die Knotenlabels sind während der Ausführung des Algorithmus *nicht* permanent. Sie werden erst in Iteration n-1 zu permanenten Knotenlabels.

Der Satz will also, wenn ich das zusammenfassen darf, sagen: "Nach der Durchführung eines Label-Correcting-Algorithmus" hat jeder Knoten v einen ausgezeichneten Knoten pi(v)."

Du kannst natürlich on-the-fly testen. Das ist dann möglich, wenn du C (maximaler Wert über alle Kantenkosten) kennst, denn ein kürzester Weg kann ja aus nicht mehr als n-1 Kanten bestehen. Ergo hast du nen positiven (negativen) Zyklus, wenn das Distanzlabel d(v) > nC bzw. d(v) < -nC wird.

Ich habe da gerade nochmal drübergelesen und das kann man so nicht sehen...
Die Schranken nC sind sinnvoll und können jederzeit getestet werden, wenn man ein Label updatet. Das hat aber mit dem Erkennen negativer Zyklen nichts zu tun ("We can *also* stop ...").
Die behauptung steht, man könne in O(n) auf Existenz negativer Zyklen testen. Wie geht das?

Und damit die Frage nicht untergeht, bislang noch unbesprochen:

1. (S. 142) Wie kommt man darauf, dass die Yen-Variante nur n/2 Durchläufe braucht?

[Arki]

Der Bellman-Ford-Algorithmus verwendet gar keine Queues... Genausowenig die CORRECT-Prozedur.
Das ist auch der Grund, warum ich die FIFO- und Deque-Varienten eher für Implementierungen des modifizierten Label-Correcting-Algorithmus halte und nicht direkt für Varienten des Bellman-Ford-Algorithmus'. Die Folien sind diesbezüglich nur etwas seltsam angeordnet.

Sorry, hab mich da vertan und hätte wohl mal vorher ins Skript gucken sollen. Ich geb dir in diesem Punkt recht.

Ich habe da gerade nochmal drübergelesen und das kann man so nicht sehen...
Die Schranken nC sind sinnvoll und können jederzeit getestet werden, wenn man ein Label updatet. Das hat aber mit dem Erkennen negativer Zyklen nichts zu tun ("We can *also* stop ...").
Die behauptung steht, man könne in O(n) auf Existenz negativer Zyklen testen. Wie geht das?

Der Test in O(n) ist auf dem predecessor graph möglich. Der predecessor graph ist ja nicht zwangsweise ein Baum, sondern kann einen gerichteten Zyklus enthalten, nämlich genau dann, wenn wir einen negativen Zyklus im Graphen haben. Warum? Dazu ein kleines Beispiel:
Betrachten wir den Pfad P = 2 --> ... --> 4. Nehmen wir an, dass pi(2) = 4. Das geht nur, wenn wir correct(4,2) ausführen und das passiert wiederum nur dann, wenn d(2) > d(4) + c(4,2) ist. Die Knoten 2 und 4 müssen also auf einem negativen Zyklus 2 --> ... --> 4 --> 2 liegen, damit pi(2) = 4 ist.
Du musst im predecessor graph folglich nach gerichteten Zyklen suchen und das kannst du im Prinzip mit einem modifizierten BFS/DFS tun, wobei den Knoten beim Traversieren des Graphen entsprechende Labels mitgeben werden. Bekanntlich geht das in linearer Zeit.

[yourmaninamsterdam]

Warum es da Zyklen geben kann, ist klar. BFS läuft laut Folien jedoch in O(m), nicht O(n)...

[Stille]

So wie ich das verstanden habe, gibt es im Endeffekt zwischen FIFO Label-Correcting und Bellman-Ford keine nennenswerten Unterschiede. Die Dequeue-Variante ist im Endeffekt eine Modifikation des FIFO Label-Correcting Algorithmus. Dein CORRECT sieht etwas anders aus, da du ja - je nach Situation - Knoten an den Anfang oder das Ende der Queue stellst.

Der Bellman-Ford-Algorithmus verwendet gar keine Queues... Genausowenig die CORRECT-Prozedur.

Ähem, Zeile 4. CORRECT(u,v) ...

Letztlich basiert Bellman-Ford auf dem FIFO Label-Correcting und der Beobachtung 46 (daher gibt es n-1 Iterationen). Die Folien sind hier in der Tat etwas merkwürdig angeordnet, tauchte der Bellman-Ford aber erst nach den Varianten auf, wäre es noch merkwürdiger. Vielleicht sollte man BF hier einfach als zusätzliche Variante sehen.

Das ist auch der Grund, warum ich die FIFO- und Deque-Varienten eher für Implementierungen des modifizierten Label-Correcting-Algorithmus halte und nicht direkt für Varienten des Bellman-Ford-Algorithmus'. Die Folien sind diesbezüglich nur etwas seltsam angeordnet.

Die Knotenlabels sind während der Ausführung des Algorithmus *nicht* permanent. Sie werden erst in Iteration n-1 zu permanenten Knotenlabels.

Der Satz will also, wenn ich das zusammenfassen darf, sagen: "Nach der Durchführung eines Label-Correcting-Algorithmus" hat jeder Knoten v einen ausgezeichneten Knoten pi(v)."

Spätestens dann. Falls bereits früher, ist nicht gesagt, daß der kürzeste Weg über pi(v) führt.

Du kannst natürlich on-the-fly testen. Das ist dann möglich, wenn du C (maximaler Wert über alle Kantenkosten) kennst, denn ein kürzester Weg kann ja aus nicht mehr als n-1 Kanten bestehen. Ergo hast du nen positiven (negativen) Zyklus, wenn das Distanzlabel d(v) > nC bzw. d(v) < -nC wird.

Ich habe da gerade nochmal drübergelesen und das kann man so nicht sehen...
Die Schranken nC sind sinnvoll und können jederzeit getestet werden, wenn man ein Label updatet. Das hat aber mit dem Erkennen negativer Zyklen nichts zu tun ("We can *also* stop ...").
Die behauptung steht, man könne in O(n) auf Existenz negativer Zyklen testen. Wie geht das?

Das steht in der Observation: Wenn CORRECT einen gerichteten Zyklus im Predecessor-Graph generiert, dann hat dieser negative Länge (sonst hätte CORRECT das Update nämlich nicht ausgeführt). Solch einen Zyklus erkennt man in O(n).

Mit der Schranke -nC erkennt man sehr wohl einen negativen Zyklus. Man kann diese Schranke noch verschärfen, indem man alle negativen Kantenlängen aufsummiert.

Und damit die Frage nicht untergeht, bislang noch unbesprochen:

1. (S. 142) Wie kommt man darauf, dass die Yen-Variante nur n/2 Durchläufe braucht?

Ging nicht unter. Durch die Ordnung der Yen Variante verringert man die Anzahl ungünstiger Updates (nämlich diejenigen, wenn CORRECT(v,w) von einem Knoten v aus für diverse Nachbarn w ausgeführt wird, und der Knoten v selbst erst danach ein Labelupdate erfährt). Wenn im Fall v>w für einen Knoten v CORRECT(v,w) aufgerufen wird, erfuhr der Knoten v bereits im Fall v<w ein (oder mehrere) Updates. Dadurch hat man sich ein (sinnloses) Update gespart, und die Anzahl der notwendigen Iterationen halbiert sich.

So, Feierabend.

[Arki]

Warum es da Zyklen geben kann, ist klar. BFS läuft laut Folien jedoch in O(m), nicht O(n)...

Genau genommen in O(n+m) laut Skript . Zum Problem: Ich denke es geht auch folgendermaßen. Die Knoten im predecessor graph sind zu Beginn nicht gelabelt. Nun startest du bei einem beliebigen Knoten v im predecessor graph. Diesen labelst du mit i. Du gehst dessen predecessor indices entlang und gibst jedem Knoten den du so findest das selbe Label i. Zwei Fälle können auftreten:
(1) Du gehst einen Pfad entlang, wobei du eine Teilmenge von V_{pred} abgehst (die Anzahl der Knoten die du betrachtest hast ist <= n) und stoppst irgendwann bei einem Knoten w mit \(|\delta^{+}(w)| = 0\). Dann führst du die Suche beim nächsten ungelabelten Knoten fort und labelst diesen meinetwegen i+1. Beachte hierbei dass für den ersten Knoten, den wir i gelabelt haben, gilt, dass dieser nicht wieder erreicht werden kann (ebenso wie seine Vorgänger), da er nicht auf einem Zyklus liegt (also betrachten wir die mit i gelabelten Knoten nicht doppelt).
(2) Du gehst einen Zyklus entlang, labelst die Knoten entsprechend und gelangst irgendwann zu einem Knoten, den du bereits mit dem selben Label markiert hast. Du betrachtest also im worst case maximal n+1 Knoten (beim ersten gefundenen Zyklus kannst du ja abbrechen).

Entsprechend viele Kanten gehst du entlang, so dass die Komplexität dieser Suche in O(2n) = O(n) liegt.

Oder überseh ich was?

[yourmaninamsterdam]

Der Bellman-Ford-Algorithmus verwendet gar keine Queues... Genausowenig die CORRECT-Prozedur.

Ähem, Zeile 4. CORRECT(u,v) ...

Ich meine, weder der Algorithmus noch die CORRECT-Prozedur verwendet eine Queue... Man wird allerdings sicher die n-1 Iterationen mit einer jeweils vollen Queue interpretieren können.
Mir scheint, als seien die Varianten einfach nur Varianten des modifizierten Label-Correcting-Algorithmus.

Das steht in der Observation: Wenn CORRECT einen gerichteten Zyklus im Predecessor-Graph generiert, dann hat dieser negative Länge (sonst hätte CORRECT das Update nämlich nicht ausgeführt). Solch einen Zyklus erkennt man in O(n).

Warum ein Zyklus im Vorgängergraph zwangsläuig negative Länge hat, ist klar. Die Frage ist: WIE erkennt man einen Zyklus in O(n)?

Mit der Schranke -nC erkennt man sehr wohl einen negativen Zyklus. Man kann diese Schranke noch verschärfen, indem man alle negativen Kantenlängen aufsummiert.

Das glaube ich ebenfalls gerne, aber wenn ich das richtig verstehe, dann sind a) die Sache mit den Zyklen und b) die Sache mit der Schranke zwei verschiedene Kriterien.

Ging nicht unter. Durch die Ordnung der Yen Variante verringert man die Anzahl ungünstiger Updates (nämlich diejenigen, wenn CORRECT(v,w) von einem Knoten v aus für diverse Nachbarn w ausgeführt wird, und der Knoten v selbst erst danach ein Labelupdate erfährt). Wenn im Fall v>w für einen Knoten v CORRECT(v,w) aufgerufen wird, erfuhr der Knoten v bereits im Fall v<w ein (oder mehrere) Updates. Dadurch hat man sich ein (sinnloses) Update gespart, und die Anzahl der notwendigen Iterationen halbiert sich.

Intuitiv ist die Sache klar, aber gibt es irgendeinen Grund, auf n/2 Iterationen zu schließen oder ist das einfach so und der Beweis ist in den Folien nicht gegeben?

[Stille]

Ich meine, weder der Algorithmus noch die CORRECT-Prozedur verwendet eine Queue... Man wird allerdings sicher die n-1 Iterationen mit einer jeweils vollen Queue interpretieren können.
Mir scheint, als seien die Varianten einfach nur Varianten des modifizierten Label-Correcting-Algorithmus.

Jain, die Yen-Variante ist ursprünglich eine Modifikation des Bellman-Ford Algorithmus. d'Esopo/Pape verwenden eine Datenstruktur ähnlich der im FIFO Label Correcting Algorithmus. Daher werde ich das Skript nun folgendermassen anordnen. Generic Label-Correcting -> Modified Label Correcting Algorithmus -> FIFO Label Correcting Algorithmus -> Dequeue -> Bellman-Ford -> Yen-Variant. Da leider nur eine Dimension zur Verfügung steht, muß das sequentiell angeordnet sein. Ich hoffe, es wird so zumindest etwas klarer. Alles sind letztlich Varianten des Label-Correcting Algorithmus.

Warum ein Zyklus im Vorgängergraph zwangsläuig negative Länge hat, ist klar. Die Frage ist: WIE erkennt man einen Zyklus in O(n)?

Man folgt einfach den predecessor labels. Wurde doch oben quasi bereits beantwortet.

Das glaube ich ebenfalls gerne, aber wenn ich das richtig verstehe, dann sind a) die Sache mit den Zyklen und b) die Sache mit der Schranke zwei verschiedene Kriterien.

Klar, das sind zwei völlig unabhängige Kriterien, daher auch das "also" in diesem Satz.

Intuitiv ist die Sache klar, aber gibt es irgendeinen Grund, auf n/2 Iterationen zu schließen oder ist das einfach so und der Beweis ist in den Folien nicht gegeben?

Ich habe den Originalartikel heute leider nicht mehr bekommen, hoffentlich aber morgen. Mittlerweile bin ich der Meinung, daß die n/2 Iterationen zwar im "average case" erreicht werden, es jedoch einfache Beispiele gibt, in denen n-1 Iterationen benötigt werden. Ich werde das Skript dementsprechend ändern, sobald ich mir das genauer angesehen habe. Keine Angst, es wird nicht relevant für die Klausur sein.

[Andi]

Warum ein Zyklus im Vorgängergraph zwangsläuig negative Länge hat, ist klar. Die Frage ist: WIE erkennt man einen Zyklus in O(n)?

Kann man nicht argumentieren, dass der Vorgängergraph nur m=n-1 Kanten besitzt. Denn so ist er nach meinem Verständnis definiert (jedem Knoten wird ein Vorgänger eindeutig zugeordnet).

[Stille]

Warum ein Zyklus im Vorgängergraph zwangsläuig negative Länge hat, ist klar. Die Frage ist: WIE erkennt man einen Zyklus in O(n)?

Kann man nicht argumentieren, dass der Vorgängergraph nur m=n-1 Kanten besitzt. Denn so ist er nach meinem Verständnis definiert (jedem Knoten wird ein Vorgänger eindeutig zugeordnet).

Ja, das wurde doch oben von Arki bereits so ähnlich ausgeführt. Im Falle eines Zyklus sind es genau n Kanten.

[marluwie]

Folie 126:
It maintains nC + 1 so-called buckets numbered 0, 1, ... nC + 1. Entweder nC + 2 Buckets oder 0, ..., nC. Sorry, für das Millimeterpissen. Oder liege ich falsch?
Es wird auf Folie 127 wird eine Kleinigkeit verschwiegen. Dadurch, dass man jetzt alles Modulo rechnet, verschiebt sich auch die 0, oder? Wenn ich nach einem Knoten auf einem momentan kürzesten Weg suche, muss ich also die Buckets von d(v) mod C + 1 und nicht von 0 anfangen zu durchsuchen.