Not logged in. · Lost password · Register

Gustav
Avatar
Member since Oct 2008
30 posts
Subject: Klausur 2009-10 --- A4
In c) Tabelle 6 von B soll man die neue Distanz von B nach A angeben.

Nachdem A seine Distanztabelle nach B gesendet hat in der die Distanz nach E mit 1 angegeben ist, müsste B doch erkennen, dass es über E kürzer nach A kommt, nämlich mit einer Distanz von 3?
Stimmt da die Musterlösung nicht (diese behält nämlich die Distanz von 5 und den "direkten" Weg nach A), oder verstehe ich hier etwas nicht richtig? Werden weniger Kanten einer kürzeren Distanz irgendwie bevorzugt?

Ich hoffe ich konnte mich verständlich ausdrücken, sonst bitte einfach nachfragen. Vielen Dank!
sotsoguk
AlgoKS Tutor
Member since Nov 2008
470 posts
in der angabe zur c steht dabei,
Knoten A sendet im nächsten Schritt [....] und kein anderer Knoten neue Informationen verschickt
ich habs dann so verstanden dass eben die Information von E B und C nicht bekannt sind. Aber ehrlich gesagt is die Angabe zu der Aufgabe wirklich sehr unverständlich...
klassenerhalt 2014!!
Gustav
Avatar
Member since Oct 2008
30 posts
Hm, interessanter Punkt.
Das heißt, dass der Algorithmus zwar mitbekommt, dass A jetzt günstig nach E kommt, aber eben nicht weiß/versteht, dass das umgekehrt bedeutet, dass E auch günstig nach A kommt und dass er diese Verbindung dafür verwenden kann?
Mago
Member since Sep 2008
619 posts
B kann nicht wissen dass es über E nach A kommt weil es keine Distanzvektoren von E erhält, sondern nur den von A. Du kannst net einfach Informationen dazudichten. Der Distanzvektoralgorithmus ist da eigtl. ziemlich eindeutig...
BastiW
Member since Sep 2008
572 posts
Irgendwie ist die Teilaufgabe a) ja schon nicht eindeutig oder?

Dass bei A zu C der direkte Weg der kürzeste ist, ist klar. Aber bei A zu B ist das doch mit den gegebenen Information nicht eindeutig. Wenns z.b. ne Kante C zu D mit Kosten 1 und D zu B mit Kosten 1 gibt, dann wäre der Eintrag bei B ja 4 C und nicht 5 B. Oder hab ich da einen entscheidenden Hinweis überlesen?^^

Edit: Hat sich erledigt. Man muss sich nur die Einträge in der Tabelle anschauen :)
This post was edited on 2010-09-30, 20:52 by BastiW.
disaster
Member since Oct 2009
33 posts
In reply to post #4
So, mit Blick in den Algorithmus konnte ich das Problem (das ich auch hatte ;)) lösen.

warte bis
- Änderung der Kosten zu Nachbar w (Du ändert sich) oder Erhalt eines Distanzvektors Dw von Nachbar w für alle vV:
- Du(v) = minw{c(u,w)+Dw(v)};

aus den Folien.

B erhält hier Da(e), also die Kosten von A nach E. Allerdings wird für die Berechnung des weges von B nach A der Wert De(a), also von E nach A herangezogen. Diesen hat B ja noch nicht.
Ziemlich fiese Frage :P
Close Smaller – Larger + Reply to this post:
Verification code: VeriCode Please enter the word from the image into the text field below. (Type the letters only, lower case is okay.)
Smileys: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Special characters:
Go to forum
Datenschutz | Kontakt
Powered by the Unclassified NewsBoard software, 20150713-dev, © 2003-2011 by Yves Goergen