Algorithmus von Warshall

[julia1997]

Hallo!

Kann mir jemand helfen?

 

[julia1997]

Bei a) hätte ich mir gedacht, dass Berta und Anton vielleicht nicht die gleiche Reihenfolge haben, und es trotzdem immer auf das gleiche herauskommt. Aber b) kapiere ich irgndwie nicht? welches n ist gemeint?

 

[mrBrown]

Vermutlich das N aus Satz 5.13

 

[julia1997]

;-)

 

[mrBrown]

Weist du jetzt, welches N gemeint ist?

 

[julia1997]

Ja aber ich verstehe trotzdem nicht genau was es zu bedeuten hat.. Steht N für die ganze Zeile?

 

[mrBrown]

Steht N für die ganze Zeile

Nein, es ist ja N=A am Anfang der Schleife

 

[julia1997]

N ist die Anzahl der Elemente und A die Matrix?

 

[mrBrown]

N ist die Anzahl der Elemente und A die Matrix?

A ist die Matrix, ja. Und was ist wohl N, wenn N=A ist?

 

[julia1997]

Kopie der Matrix

 

[mrBrown]

Genau

 

[julia1997]

deswegen braucht man N am Ende, damit man beim nächsten Schritt wieder mit der "neuen" Matrix arbeiten kann?

 

[mrBrown]

Ja, ob man es aber überhaupt braucht ist ja die Frage

 

[julia1997]

Das letzte A=N braucht man also nicht, wenn du so fragst haha

 

[julia1997]

beim Algorithmus geht man ja die Zeilen und Spalten durch und am Ende wird einfach das neue A nochmal überschrieben und dass braucht es nicht unbedingt

 

[mrBrown]

Passiert denn noch irgendwas sinnvolles, wenn man nur das letzte A=N weg lässt?

 

[julia1997]

Nein eig nicht oder? Die erste Schleife läuft weiter

 

[mrBrown]

Mit der ersten Schleife hat das allerdings nicht viel zu tun

 

[julia1997]

Ich wüsste nicht was dann noch passieren sollte

 

[stg]

In Algorithmus 5.13 wird nur in der Kopie von A geschrieben und erst, wenn "alles fertig berechnet" wurde, werden alle Änderungen wieder nach A geschrieben.
Wenn du direkt in A schreibst, dann ist der Wert, der dort ursprünglich stand, weg.
Die Frage ist nun, ob du eventuell in einem späteren Schleifendurchlauf noch einmal den Wert brauchst, der ursprünglich dort stand, oder aber, ob es wichtig ist, dass der neue Wert schon dort steht und nicht mehr der alte.
Ist das nicht der Fall, so ist die Lösung von Anton natürlich "besser", in Hinblick darauf, dass sie mit hal so viel Speicher auskommt.
Das letzte A = N in 5.13 kannst du natürlich nicht einfach weglassen, sonst ist A nach dem Algorithmus ja immer noch unverändert.

 

[julia1997]

Vielen vielen vielen Dank!

 

[julia1997]

Nochmal kurz zu Aufgabe a: es ist egal wo die Werte in der Matrix stehen, das ist mir klar. Aber wo ist die Stelle in der Definition mit der Wahlmöglichkeit? Man könnte j und i vertauschen?

 

[julia1997]

also es ist egal, ob man spalten oder zeilenweise vorgeht

 

[mrBrown]

Ja, das ist egal