852 Kurseinheit 1 Beispiel 3.5

Hey snoopy, stehe vor dem gleichen problem :( bzw krieg ich die wegematrix gar nicht erst hin.. kannst du mir da vielleicht nen tipp geben? klar ist mir mittlerweile, dass oo gleich null ist und das bei i=j i eingetragen wird.. aber der rest ist mir leider immer noch ein rätsel..

gruß,
mareike

duffy81 wrote:

hey snoopy, stehe vor dem gleichen problem :( bzw krieg ich die wegematrix gar nicht erst hin.. kannst du mir da vielleicht nen tipp geben? klar ist mir mittlerweile, dass oo gleich null ist und das bei i=j i eingetragen wird.. aber der rest ist mir leider immer noch ein rätsel..

gruß,
mareike

Hi mareike,
um zb. D^(2) zu errechnen, übernimmst du die 1.spalte und 1.zeile von D^(1). Die bleiben unverändert. Um zb. die 2.zeile bei D^(2) zu errechnen, gehst du wie folgt vor: Bei D^(1) ist x11=15 +x21=unendl. > 0, daher kommt bei D^(2) bei x22= 0 rein. Sprich, man nimmt immer den kleineren wert.
8+15 > 6, daher steht dann bei x32 der wert 6.
8+7 > 0, daher steht dann bei x33 der wert 0.
5+15 < unendl, daher steht dann bei x52 der wert 20.
Ich hoffe, ich konnte es so einigermaßen erklären;)
Vg Snoopy

Snoopy, vielen Dank erstmal! Aber die Matrix, die mir Schwierigkeiten bereitet ist die Matrix Q *G*
LG
Mareike

Ich geh das folgendermaßen an:
Q1: Du prüfst mit Hilfe der Grafik in Abb.3.10 ob Du z.B. von 1 nach 2 kommst, wenn ja, trägst Du den Vorgänger (hier also 1), wenn kein direkter Weg möglich, (z.B. von 4 nach 2) dann trägst Du ne Null ein. Die Diagonale ist auch klar, da Du immer von Knoten 1 zu 1 bzw. 2 zu 2 usw. kommst.

Bei allen nachfolgenden D* wird geschaut, ob Du die Wege verkürzen kannst. Achte hier auf die vorgegebenen Spalten und Zeilen. In der zugehörigen Q-Matrix, wird dann der entsprechende neue Vorgänger angegeben.

Beispiel: Der Weg von Knoten 5 nach Knoten 2.
In D1 kein direkter Weg, daher unendlich und in Q an dieser Stelle 0.
In D2 suchst Du jetzt einen Weg der funktioniert und entdeckst von 5 über 1 nach 2. Macht ne Entfernung von 20 und der Vorgänger von Knoten 2 ist jetzt 1.

usw.

könnte mir von euch vielleicht jemand sagen, wie ich aus der letzten Wegematrix Q(6) hier die kürzesten Wege rauslesen kann?

Vielen Dank und Grüße
Manu

Manu!

Problem inzwischen gelöst?

Falls nicht:
Die Matrix lautet

...... 1 2 3 4 5

1 ... 1 3 1 2 4
2 ... 5 2 1 2 4
3 ... 3 3 3 2 4
4 ... 5 3 1 4 4
5 ... 5 3 1 2 5

in der Q-Matrix sind immer die Vorgänger auf dem kürzesten Weg angegeben.
D.h. Der vorletzte Knoten (Vorgänger!) auf dem kürzesten Weg von 1 nach 5
steht in Zeile 1, Spalte 5, also "4".
Der Weg lautet also (1, ?, ..., ?, 4, 5)
Der Vorgänger der 4 (von 1 nach 4) steht in Zeile 1, Spalte 4, also " 2".
Weg (1, ?, ..., ?, 2, 4, 5)
Der Vorgänger der 2 steht in Z1, S2, also "3"
Weg (1, ?, ..., ?, 3, 2, 4, 5)
Und der Vorgänger von 3 in Z1, S3 ==> "1"
Daraus folgt der Weg (1, 3, 2, 4, 5)

Die Entfernung aus der D-Matrix, Z1, S5 ="18"

Ich hoffe, ich hab's gut erklärt? (und nix falsch gemacht...)

RWS64,

vielen Dank für die super Erklärung! Noch kurz ne Rückfrage, ob ich's auch wirklich verstanden habe:
Wenn ich nun zum Beispiel von 4 nach 2 gehen will - ich gehe in Z4 S2 -> "3", danach in Z4 S3 -> "1", dann in Z4 S1 -> "5", dann Z4 S5 -> "4", dann Z4 S4 -> "4"
=> <4, 5 ,1, 3, 2>.
Dass heißt also von der Zahl, von der ich losgehen will, hier wähle ich die Spalte; danach fülle ich "von hinten" den restlichen weg auf? Die hier entpsrechenden Werte lese ich dann aus der Entfernungsmatrix raus.

Hab ich das so richtig verstanden???

Nochmals vielen Dank und Grüße
Manu

ManuM,

ja, das hast Du so richtig verstanden.

Gruß
Susanne

HI Susanne,

danke dir !!

Grüße
Manu