Trippel-Algorithmus

mal eine Frage zum Trippel-Algorithmus, anhand der Übungsaufgabe.
https://www.fernuni-hagen.de/BWLQUAM/assets/uebung/b8520301.pdf

D1 und Q1 bekomme ich ohne Probleme aufgestellt.

aber dann fangen meine Probleme an.

Kann mal jemand erklären wie das geht?

Gruß!
Sigi

Siggi
D2 und Q2 sind hier zufällig gleich D1 und Q1,deshalb erkläre ich von D2 aus.
Was sagen denn die Elemente der Matrix aus?Das Element in der 3.Zeile und 1.Spalte,
die 6 also bedeutet,daß der Weg
von Knoten 3 zu Knoten 1 momentan 6 beträgt.Bei D2 steht Knoten 2
jetzt im Blickpunkt;man fragt sich,ob die einzelnen Wege
(also auch der Weg von 3 nach 1) über das Nutzen von Knoten 2
verkürzt werden können.Dazu ist die 2.Spalte und die 2.Zeile
eingerahmt.Schau Dir,Siggi,jetzt mal den Weg von Knoten 3 nach Knoten
1 genau an.Wenn man von Knoten 3 zuerst nach Knoten
2 geht(das ist die eingerahmte 3) und dann weiter geht von Knoten 2
nach Knoten 1(das ist die eingerahmte 2) dann kommt man
auch zum Zielknoten 1 und jetzt beträgt der Weg nicht 6 sondern 5
Also ändert man in der neuen Matrix D3 dieses Element von 6 zu 5.
In der Q-Matrix muß man entsprechend auf dem Weg von Knoten 3
nach Knoten 1 den letzten Knoten vor dem Zielknoten 1
von 3 ändern in 2.Denn man geht ja 3-2-1,also ist Knoten 2 der letzte
vor dem Zielknoten 1.Das ist ja Inhalt der Q-Matrix,
daß man nicht nur die kürzesten Entferungen zwischen den Knoten hat(siehe D-Matrix),
sondern gleichzeitig auch die genauen
Wege parat hat(eben die Q-Matrix).
Nach diesem Schema geht man nun vor.
Die Matrizen D2 und Q2 stimmen übrigens deshalb mit D1 und Q1 überein,
weil offenbar kein einziger Weg über die Zuhilfenahme
des Knotens 1 verkürzt werden konnte.Bei D3 und Q3 sieht es schon anders aus.
Ist der Tripel-Algorithums jetzt etwas klarer geworden?

nochmals
Übrigens kommt immer dann,wenn eine Verbesserung möglich war,ein kleiner Pfeil in die Matrix,
damit man sieht,an welcher Stelle auch eine Änderung in der Q-Matrix vorgenommen werden muß.
Gibt es keine Pfeile,dann bleibt alles wie gehabt.

William,

ich habs grundlegend begriffen.
Wobei meine Lösung vom Lehrstuhl abweicht und ich noch nicht genau weiß wieso.


Jetzt stellt sich die Herausforderung mit dem Bellman - Siehe neue Frage.

Gruß!
Sigi

Siggi
Deine Zweifelsfälle hast Du doch in Violett markiert,oder?
Also ein Fehler löst sich in Luft auf,denn Du hast in D1 einfach falsch abgeschrieben.Statt im Feld 13 die 5 zu lassen,hast Du 6 geschrieben.
Es ist nämlich duch den Knoten 4 keine Verbesserung des Weges 13 möglich.
(Schau übrigens Dir den Graphen selbst an!Der WEg 1-4-3 ist sinnlos!)

Beim zweiten "Fehler",also bei Q3 in der Zelle 51 zweifelst Du die 2 an und möchtest eine 4 haben.
Aber es gibt keinen Automatismus,daß,wenn der Knoten 4 eine Verbesserung bewirkt hat,daß in Q
immer eine 4 eingetragen wird.Schau Dir auch hier den Graphen an!
Statt von 5 nach 1 über den Weg 5-2-1(Länge 7) zu gehen,gehst Du jetzt 5-4-2-1(Länge 6).
Du BENUTZT den Knoten 4,aber die 2 ist IMMER NOCH letzter Knoten vor dem Zielknoten 1.

William schrieb:

Moin,Siggi
Deine Zweifelsfälle hast Du doch in Violett markiert,oder?

Also ein Fehler löst sich in Luft auf,denn Du hast in D1 einfach falsch abgeschrieben.Statt im Feld 13 die 5 zu lassen,hast Du 6 geschrieben.
Es ist nämlich duch den Knoten 4 keine Verbesserung des Weges 13 möglich.
(Schau übrigens Dir den Graphen selbst an!Der WEg 1-4-3 ist sinnlos!)

Zum Vergrößern anklicken....

Hallo William,
Ja die violett markierten Felder zweifel ich an.
Danke das war ein Übertragungsfehler.
Grins das war ja mein Problem - daß es sinnlos ist der Eintrag.

William schrieb:

Beim zweiten "Fehler",also bei Q3 in der Zelle 51 zweifelst Du die 2 an und möchtest eine 4 haben.
Aber es gibt keinen Automatismus,daß,wenn der Knoten 4 eine Verbesserung bewirkt hat,daß in Q
immer eine 4 eingetragen wird.Schau Dir auch hier den Graphen an!

Zum Vergrößern anklicken....

Ja das stimmt - es gibt keinen Automatismus - aber eine Logik. Und ich hab meinen Fehler gefunden.
Zum Schema
Ich habe eine Veränderung in Q3 an der Stelle 5,1. Ich muß dann in Q2 an der Stelle 3,1 schauen ob du den Ursprungswert (Null oder 3) noch hast oder nicht. Ist der Ursprungswert noch eingetragen dann trägst du in Q3 an der Stelle 5,1 die 4 ein. Wurde der Ursprungswert verändert trägst du den Wert aus Q2 in Q3 ein.

Der Fehler war bei meiner Lösung - ich habe in der falschen Zeile (also 2) in Q2 gesucht und hatte die 2 und 0 als Ursprungswert angenommen und nicht in der 3. Zeile mit den Ursprungswerten 0 und 3.

Dann stimmt das auch mit meinen Wegen.

ich möchte gerne das Thema noch einmal aufgreifen.

wie die Distanzmatrix bestimmt wird ist mir klar, auch wie sich diese verändert.

Allerdings habe ich Schwierigkeiten beim Aufstellen der Wegematrix. Wi der William schon geschriben hat, gibt es wohl keinen Automatismus. Aber laut Siggi eine Logik.

Leider kann ich diese nicht finden 😉

Was ich wohl erkenne, ist, dass lediglich die q Elemente geändert werden, bei denen die Summer der Wege d besser (kürzer) ist als der momentane Weg.
Problematisch wird es für mich dann, wenn ein bereits geänderter Weg nochmal geändert wird. Wie kann ich ohne den Graphen zu betracgten nun erkennen, ob der Vorgängerknoten bleibt oder ob er die Zahl der letzten Matrix bekommt?

Ganz konkret:
Seite 64, Matrix D6

Sowohl <4,1> als auch <4,2> konnten unter Berücksichtigung des Umwegknotens 5 kürzer bestimmt werden.
Bei <4,1> ist der Vorgängerknoten nun 5 und bei <4,2> bleibt er 3

Wie kann ich so etwas logisch sehen, ohne den Graphen zu betrachten?

Gruß

Zu D^(6) hätte ich auch mal ne Frage. Es führen doch alle Wege in den einzelnen Zeilen zu zulässigen Lösungen außer Zeile 3 und Zeile 2 ist die optimale Lösung? Ist das immer so, dass wenn in der letzten Matrix In einer Zeile der gleiche Wert auftaucht die Lösung nicht zulässig ist?

addupTheFactors,

gerne helfe ich, wo ich kann. Leider verstehe ich deine Frage nicht ganz. Ich versuche aber mal D^(6) und Q^(6) zu erläutern, vielleicht löst es dein problem. Wenn nicht, dann sag nochmal genau, wo es zu haken scheint.

nach Durchlauf des Algorithmusses gibt D^(6) die kürzeste Entfernung von jedem Knoten zu jedem beliebigen anderen Knoten an. Z.B. hat der kürzeste Weg von Knoten 3 zu Knoten 5 die Länge 11. Das kannst du D^(6) entnehmen. von Knoten 4 zu Knoten 2 ist der kürzeste Weg 21. Okay?

Q^(6) hingegen verrät einem den Weg für jeden kürzesten Weg von allen Knoten zu allen anderen. Wollen wir also wissen, wie denn nun der kürzeste Weg von Knoten 3 zu Knoten 5 mit der Länge 11 genau ausschaut, dann betrachten wir Q^(6). Man schaut hierfür auf die Stelle q_35 (wegen: Knoten 3 zu Knoten 5): dort steht eine "4", d.h. der unmittelbare Vorgänger auf dem Weg zu 5 ist die 4. Jetzt schaut man einfach bei q_34, welcher denn der unmittelbare Vorgänger von 4 ist, das ist hier der Knoten "2". Weiter gehts, indem man schaut, welcher denn der unmittelbare Vorgänger von 2 ist, hierfür schaut man auf q_32 und findet dort die 3. Damit hat man den Startknoten gefunden und weiß, dass der kürzeste Weg von 3 nach 5 folgende Pfeilfolge ist: <3,2,4,5>. Die Länge ist aus D^(6) bekannt (11!) und mit Blick auf Abb.3.10. Seite 63 kann dies auch nachverfolgt werden.

Fazit: D^(6) gibt die Länge der kürzesten Wege an und Q^(6) verrät einem den Weg, der dafür "gegangen" werden muss. Die Lösung in sämtlichen Matrizen sind immer zulässig aber erst in den letzten Matrizen D^(6), Q^(6) auch optimal!

Ich hoffe, ich konnte helfen

warum so kompliziert erklären => das liest dann sonst keiner 😕 😕 😉

Anbei kurz die Tripel-Logik mit ein paar Sätzen (März 2011):

- Aufstellen D (1) und Q (1) => einfach Entfernungen für D und Knoten für Q eintragen, wo kein unendlich. Wo kein Weg = unendlich 😎

- Erster Lauf => Referenz 1. Zeile und 1 Spalte für Knoten A. Einfach einen Abgleich machen, was ist größer: Summe der Felder oder das jeweilige Element

- Da wo Verbesserung eingetreten ist, da in der Q-Matrix die jeweilige Knoten-Nr. eintragen 😱

- Und so weiter bis zum Schluß => bis D (end) resp. Q (end)

- Dann ablesen => die Zeilen bedeuten "von A etc." / die Spalten " nach A etc.". Also rückwärts ablesen

Ok, das wars dann 😳 😱ops

wie die Distanzmatrix bestimmt wird ist mir klar, auch wie sich diese verändert.
Allerdings habe ich Schwierigkeiten beim der Wegematrix.
Q(1) -> alle unendlich in der Entfernungsmatrix D(1) werden zu Null
Q(2) -> nun muss ich entsprechend der Änderungen der D(2) anpassen
-> wie gehe ich vor wenn nun das Feld schon mal geändert wurde?
z.B.: in Beispiel 3.5 KE1 S.63
in Q(4) müssen Feld 14 und Feld 15 angepasst werden da ein kürzerer Weg in D(4) gefunden wurde
warum wird bei Feld 14 die Änderung von D(3) beibehalten und bei Feld 15 wird auf D(4) geändert?
Q(4) =
13223
02022
33323
00044
53125

hat sich erledigt

Ich hab das alles soweit verstanden. Was mir jedoch nicht klar ist, ist die Angabe der kürzesten Wege. Im letzten Q stehen grundsätzlich alle kürzesten Entfernungen. Wie kann es also sein, dass ich in der Lösung nur 3 Wege angebe wie zum Beispiel 1 nach 5, 3 nach 1 und 5 nach 1 und nicht zum Beispiel 1 nach 4?

FB89,

falls du dich auf Q6 auf Seite 64 beziehst: Es werden immer alle kürzesten Wege beschrieben und dabei die Vorgängerknoten in der Zeile angegeben.
In der 1. Zeile des letzten Q (gibt an, wie du die einzelnen Knoten von 1 aus erreichen kannst) findest du 1,3,1,2,4. Möchtest du jetzt wissen, wie du am schnellsten von 1 zu 5 kommst, guckst du in der 1. Zeile auf die 5. Spalte. Die 4 gibt an, dass der Vorgängerknoten von Knoten 5 - Knoten 4 ist. Dann guckst du wegen Vorgängerknoten 4 in die 4 Spalte und findest Vorgängerknoten 2. In der 2. Spalte findest du (Vorgängerknoten) 3, in der 3. Spalte findest du 1. Der kürzeste Weg von 1 zu 5 ist daher 1,3,2,4,5. Interessierst du dich nicht für den Weg von 1 zu 5 sondern z.B. 1 zu 4, fängst du halt in der 4 Spalte an und findest nach dem gleichen Vorgehen 1,3,2,4.