Shortest Paths by Repeated Squaring

lkbaerenfaenger
Mausschubser
Mausschubser
Beiträge: 44
Registriert: 13. Mär 2012 12:44

Shortest Paths by Repeated Squaring

Beitrag von lkbaerenfaenger »

Hallo,

ich habe eine Anmerkung und zwei Fragen zum o.g. Algorithmus:

:arrow: Im Wiki-Eintrag wird unter Auxiliary Data eine Matrix \(M_{0}\) genannt, die nie wieder erwähnt/gebraucht wird. Dann kann man sie auch weglassen...

:?: Mir ist aufgefallen, dass - im Gegensatz zu Bellman-Ford - generell nur auf einer Matrix \(M\) gearbeitet wird. Es gibt keine Matrix \(M^{i}\) für jede Iteration. Das bringt aber folgendes Problem mit sich: Angenommen, wir sind in Iteration i = 4. Für \(M(v,u)\) wird ein neuer Distanzwert ausfindig gemacht, basierend auf einem Pfad mit i+1 = 5 Kanten. Nun widmen wir ins - immernoch in Iteration 4 - dem Matrixeintrag \(M(v,w)\). Wie sich herausstellt ist die folgende Distanz kleiner als der bisherige Wert: \(M(v,u) + M(u,w)\), d. h. \(M(v,w)\) wird überschrieben. Problem: Bereits \(M(v,u)\) basiert auf einem Pfad mit maximaler Kantenzahl (i+1). Demzufolge muss der Distanzwert \(M(v,w)\) auf einem Pfad basieren, der mehr als i+1 Kanten umfasst. Damit wäre die Invariante verletzt, oder nicht? Dies könnte man vermeiden, indem man, wie bei Bellman-Ford, eine neue Matrix \(M^{i}\) lediglich aus Werten aus \(M^{i-1}\) und \(M^{0}\) errechnet, und eben nicht nur auf einer einzigen Matrix \(M\) arbeitet.

:?: Ich gehe mal davon aus, dass in der Invariante \(M = M^{2i}\) gemeint ist, und die zusätzliche 0 ein Versehen ist...

Vielen Dank im Voraus + LG,

Lucas

lkbaerenfaenger
Mausschubser
Mausschubser
Beiträge: 44
Registriert: 13. Mär 2012 12:44

Re: Shortest Paths by Repeated Squaring

Beitrag von lkbaerenfaenger »

:?:

JohnSmith
Neuling
Neuling
Beiträge: 5
Registriert: 16. Sep 2013 14:47

Re: Shortest Paths by Repeated Squaring

Beitrag von JohnSmith »

So wie ich es verstanden habe, ist mit \(M_0\) die ursprüngliche Matrix (also \(M\) nach 0 Iterationen) gemeint. Sie wird wohl gebraucht um die Invariante zu formulieren, welche den Inhalt von \(M\) beschreibt.

lkbaerenfaenger
Mausschubser
Mausschubser
Beiträge: 44
Registriert: 13. Mär 2012 12:44

Re: Shortest Paths by Repeated Squaring

Beitrag von lkbaerenfaenger »

In der Invariante wird \(M_{0}\) nicht erwähnt... Aber wenn wir gerade von der Invariante sprechen, was bedeutet \(M^{2i}_{0}\)?

mg_92
Neuling
Neuling
Beiträge: 4
Registriert: 21. Sep 2013 15:25

Re: Shortest Paths by Repeated Squaring

Beitrag von mg_92 »

So wie ich das verstanden habe ist \(M_0\) wichtig, da \(M_0\) den start des algorithmus bildet.
Man potenziert dann in jeder Iteration diese "Startmatrix" mit einem vielfachen von 2.
Konkret würde das bedeuten:

In der ersten Iteration würde man die Matrix \(M = M_0^2\) erhalten.
In der zweiten Iteration die Matrix \(M = M_0^4\) usw.

Also konkret nach einer Iteration i ist \(M = M_0^{2i}\). Daher auch die Invariante.

Edit: Erwähnenswert ist noch das dies nicht die "Normale" Matrix multiplikation ist. Dies wird aber sowohl im Video als auch im Wiki erklärt.

Assax
Windoof-User
Windoof-User
Beiträge: 41
Registriert: 2. Dez 2011 10:38

Re: Shortest Paths by Repeated Squaring

Beitrag von Assax »

In den Videos https://openlearnware.hrz.tu-darmstadt.de/material/2349 wird es so gehandhabt, dass man nach i=3 bei M^8 ist und nicht bei M^2*3 = M^6.
Überall steht aber M^2i anstatt M^2^i, wobei wenn man "repeated squaring" sagt, für mich M^2^i auch mehr Sinn macht...

mg_92
Neuling
Neuling
Beiträge: 4
Registriert: 21. Sep 2013 15:25

Re: Shortest Paths by Repeated Squaring

Beitrag von mg_92 »

Assax hat geschrieben: Überall steht aber M^2i anstatt M^2^i, wobei wenn man "repeated squaring" sagt, für mich M^2^i auch mehr Sinn macht...
Stimmt. wird ja auch so im Video erklärt. Wäre vielleicht besser es im Wiki so aufzuschreiben:

\(M_i = M_{i-1}^2\)

Assax
Windoof-User
Windoof-User
Beiträge: 41
Registriert: 2. Dez 2011 10:38

Re: Shortest Paths by Repeated Squaring

Beitrag von Assax »

Im Video steht witzigerweise auch M^2i aber es wird M^2^i gemacht :lol:
Im wiki jedoch, sieht es sogar so aus wie M^2^i wenn man genau hinguckt ist das i ein wenig höher gesetzt, vielleicht bilde ich mir das auch nur ein...

EDIT:
Source code des Wiki Eintrags: <tex>M=M_0^{2^i}}</tex>, also doch 2^i.

genix
Windoof-User
Windoof-User
Beiträge: 39
Registriert: 16. Okt 2010 13:41

Re: Shortest Paths by Repeated Squaring

Beitrag von genix »

- Ignorieren -

lkbaerenfaenger
Mausschubser
Mausschubser
Beiträge: 44
Registriert: 13. Mär 2012 12:44

Re: Shortest Paths by Repeated Squaring

Beitrag von lkbaerenfaenger »

Max, Du hast mich gerettet. Aber eine kurze Frage noch: Nach meinem Verständnis von Repeated Squaring müsste \(M\) nach zum Beispiel 4 Iterationen über Pfade mit max. 16 Kanten verfügen. Der Invariante zufolge wäre nach 4 Iterationen \(M^{2^{4}} = M^{16}\). Das ist ja schonmal gut! Nun die Frage, wie ist das zu deuten? Im Paths-Artikel im Wiki steht, dass \(M^{i}\) über Pfade mit maximal \(i\) Kanten verfügt. Im Bellman-Ford-Atrikel hingegen heißt es, dass \(M^{i}\) über Pfade mit maximal \(i + 1\) Kanten verfügt? Offensichtlich bezieht sich Repeated Squaring auf die Definition im Path-Artikel, aber warum? Heißt es nicht, es sei eine Bellman-Ford-Variante? Sehr verwirrend...

Assax
Windoof-User
Windoof-User
Beiträge: 41
Registriert: 2. Dez 2011 10:38

Re: Shortest Paths by Repeated Squaring

Beitrag von Assax »

Ja das ist wirklich alles ein wenig verwirrend, aber wenn ich mir das video nochmal angucken, dann sind die bei Bellman-Ford nach i Iterationen bei M^i+1, also z.B nach Iteration 2 hat man M^3 da sind Einträge mit max. i+1 Kanten enthalten, also 3 Kanten, M^3. Das würde dann ja wieder mit repeated Squarin übereinstimmen.

Im Wiki zu Bellman-Ford steht zwar, dass nach I Iterationen M^i Distanzen hat mit max. i+1 kanten, aber im Video befinden die sich irgendwie nach i Iterationen schon bei M^i+1.

Das fängt schon bei i=0 an, im Video steht M^1 = L im Wiki steht M^0 = L...
Man weiß halt nich wirklich welchem von beidem man Glauben schenken soll, da das Wiki ja eigentlich "verbindlich" ist, aber wie im Forum zu sehen finden sich da doch öfter mal Fehler oder sonstiges.

viewtopic.php?f=165&t=28800
Hier ist das Problem auch schon aufgefallen.
Die Änderung zu M^i wurde von unoffizieller Seite gemacht.
Da in der Auxiliary Data schon immer M^1 = L stand, nach der Änderung aber in der Induction Basis M^0 = L, werde ich mich einfach an M^i+1 nach i Iterationen halten, dies stimmt dann auch bei i = 0 mit der Auxiliary Data überein.

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

Re: Shortest Paths by Repeated Squaring

Beitrag von tmuecksch »

lkbaerenfaenger hat geschrieben: Nach meinem Verständnis von Repeated Squaring müsste \(M\) nach zum Beispiel 4 Iterationen über Pfade mit max. 16 Kanten verfügen. Der Invariante zufolge wäre nach 4 Iterationen \(M^{2^{4}} = M^{16}\).
Es heißt doch \(M^{i*2}\) und nicht \(M^{2^{i}}\).

Assax
Windoof-User
Windoof-User
Beiträge: 41
Registriert: 2. Dez 2011 10:38

Re: Shortest Paths by Repeated Squaring

Beitrag von Assax »

tmuecksch hat geschrieben:
lkbaerenfaenger hat geschrieben: Nach meinem Verständnis von Repeated Squaring müsste \(M\) nach zum Beispiel 4 Iterationen über Pfade mit max. 16 Kanten verfügen. Der Invariante zufolge wäre nach 4 Iterationen \(M^{2^{4}} = M^{16}\).
Es heißt doch \(M^{i*2}\) und nicht \(M^{2^{i}}\).
Da ist der Fehler, es heißt tatsächlich \(M^{2^{i}}\), schau mal im Quelltext des Wiki da siehst du es.
Man erkennt kaum, dass das i etwas höher ist.

Siehe:
Assax hat geschrieben:Im Video steht witzigerweise auch M^2i aber es wird M^2^i gemacht :lol:
Im wiki jedoch, sieht es sogar so aus wie M^2^i wenn man genau hinguckt ist das i ein wenig höher gesetzt, vielleicht bilde ich mir das auch nur ein...

EDIT:
Source code des Wiki Eintrags: <tex>M=M_0^{2^i}}</tex>, also doch 2^i.

genix
Windoof-User
Windoof-User
Beiträge: 39
Registriert: 16. Okt 2010 13:41

Re: Shortest Paths by Repeated Squaring

Beitrag von genix »

Habe mal im Internet gesucht, und habe folgendes gefunden: http://karmaandcoding.blogspot.de/2012/ ... eated.html

Hier ist es 2 ^ i.

Antworten

Zurück zu „Archiv“