Bellman-Ford im Wiki verletzt eigene Invariante

tmuecksch
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 123
Registriert: 19. Apr 2013 10:51

Bellman-Ford im Wiki verletzt eigene Invariante

Beitrag von tmuecksch »

Hallo liebe Kommilitonen,
heute habe ich mich mit dem Bellman-Ford auseinandergesetzt und muss sagen, dass mich der Wiki-Eintrag sehr verwirrt.

So steht in der Invariante, dass nach \(i\geq0\) Iterationen \(M^i (v,w)\) die Länge eines kürzesten \((v,w)\)-Pfades mit max. \(i+1\) Kanten enthält.

Die Induktionsbasis initialisiert \(M^0\). Der Induktionsschritt aber befasst sich in der Iteration \(i\) mit der Matrix \(i+1\), sodass in der Iteration \(i=1\) die Matrix \(M^2\) verarbeitet wird. Das steht aber im Widerspruch zur Invariante, da diese aussagt, dass \(M^i (v,w)\) also in diesem Fall \(M^1 (v,w)\) zu bestehen hat.

Habe ich da was falsch verstanden oder ist das ein Fehler?

URL: http://wiki.algo.informatik.tu-darmstad ... llman-Ford

Vielen Dank im Voraus
Tobias
Zuletzt geändert von tmuecksch am 8. Sep 2013 17:32, insgesamt 1-mal geändert.

Seldon
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 119
Registriert: 19. Apr 2012 18:12

Re: Bellman-Ford im Wiki verletzt eigene Invariante

Beitrag von Seldon »

Ich würde dir da zustimmen. Der Fehler ist wohl in Zusammenhang mit einer Korrektur eines Fehlers, der in diesem Post beschrieben wird, entstanden. Mein Vorschlag: Alle Indizes nach unten setzen (da das hier schon für Verwirrung sorgte) und die Induktionsvariante abändern in:

For all \(v,\,w\in V\), we set \(M_i(v,w):=\min\left\{M_{i-1}(v,u)+L(u,w)\,|\,u\in V\right\}\).
(Note that \(M_{i-1}(v,w)+L(w,w)=M_{i-1}(v,w)\) is one of the arguments over which the minimum is taken, so the right-hand side is identical to \(\min\left\{M_{i-1}(v,w),\min\left\{M_{i-1}(v,u)+L(u,w)\,|\,u\in V\right\}\right\}\).)


Bei Auxilliary Data dann noch an mehrere Matrizen anpassen:

Distance-valued \((n\times n)\) matrices \(M_0, M_1, \cdots, M_{n-1}\), where \(n=|V|\). The eventual contents of \(M_{n-1}\) will be returned as the result of the algorithm. (stimmt das mit n-1?)

Man könnte sich bei der Gelegenheit dann auch L ganz sparen und alles auf \(M_0\) beziehen.

Kija G
Erstie
Erstie
Beiträge: 17
Registriert: 22. Apr 2013 18:03

Re: Bellman-Ford im Wiki verletzt eigene Invariante

Beitrag von Kija G »

Würde es dann nicht zu einem Widerspruch mit der Invariante führen, wenn man die Induktion so abändert?
Speziell für die Induktionsbasis, also i = 0, hätten wir M^0(v,w):=min{M^(−1)(v,u)+L(u,w)|u∈V}.

Und eine M^(-1) existiert ja nicht.

Seldon
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 119
Registriert: 19. Apr 2012 18:12

Re: Bellman-Ford im Wiki verletzt eigene Invariante

Beitrag von Seldon »

Der Induktionsschritt greift doch erst bei i = 1, oder? Die Induktionsbasis arbeitet nur mit L.

tmuecksch
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 123
Registriert: 19. Apr 2013 10:51

Re: Bellman-Ford im Wiki verletzt eigene Invariante

Beitrag von tmuecksch »

Seldon hat geschrieben:Der Induktionsschritt greift doch erst bei i = 1, oder? Die Induktionsbasis arbeitet nur mit L.
So verstehe ich das auch :!:

tmuecksch
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 123
Registriert: 19. Apr 2013 10:51

Re: Bellman-Ford im Wiki verletzt eigene Invariante

Beitrag von tmuecksch »

Seldon hat geschrieben:Distance-valued \((n\times n)\) matrices \(M_0, M_1, \cdots, M_{n-1}\), where \(n=|V|\). The eventual contents of \(M_{n-1}\) will be returned as the result of the algorithm. (stimmt das mit n-1?)
Da der Algorithmus in dieser Ausführung \(n-1\) mal Iteriert, dürfte das so korrekt sein.


Kleine Bemerkung/Frage am Rande. Es gilt \(L=M_0 = M_1\), da \(M_0\) so initialisiert wird, dass es "den Graphen repräsentiert" => also Pfade der Länge 1 enthält, was für \(M_1\) ja dann auch gilt. Seht Ihr das auch so?

Seldon
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 119
Registriert: 19. Apr 2012 18:12

Re: Bellman-Ford im Wiki verletzt eigene Invariante

Beitrag von Seldon »

tmuecksch hat geschrieben: Kleine Bemerkung/Frage am Rande. Es gilt \(L=M_0 = M_1\), da \(M_0\) so initialisiert wird, dass es "den Graphen repräsentiert" => also Pfade der Länge 1 enthält, was für \(M_1\) ja dann auch gilt. Seht Ihr das auch so?
Dann wäre die Invariante verletzt - \(M_i\) soll ja Pfade mit höchstens i+1 Kanten enthalten, also \(M_1\) Pfade mit höchstens 2.

tmuecksch
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 123
Registriert: 19. Apr 2013 10:51

Re: Bellman-Ford im Wiki verletzt eigene Invariante

Beitrag von tmuecksch »

Seldon hat geschrieben: Dann wäre die Invariante verletzt - \(M_i\) soll ja Pfade mit höchstens i+1 Kanten enthalten, also \(M_1\) Pfade mit höchstens 2.
Du hast Recht! Asche auf mein Haupt -.- Danke für den Augenöffner!

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Bellman-Ford im Wiki verletzt eigene Invariante

Beitrag von Prof. Karsten Weihe »

tmuecksch hat geschrieben:Hallo liebe Kommilitonen,
heute habe ich mich mit dem Bellman-Ford auseinandergesetzt und muss sagen, dass mich der Wiki-Eintrag sehr verwirrt.
Ich habe den Eintrag leicht abgeändert und hoffe, dass die Verwirrung damit ausgeräumt ist. :oops:

Nach meinem Verständnis war die Verwendung von \(i\) im Induction Step inkonsistent mit der sonstigen Verwendung von \(i\) im Wiki: Fälschlich hat die \(i\)-te Iteration \(M^{i+1}\) aus \(M^i\) berechnet. Nun ist es konsistent: \(M^i\) wird aus \(M^{i-1}\) berechnet.

Geklärt?

KW

Antworten

Zurück zu „Archiv“