Member since Nov 2011
58 posts
|
![]()
Subject: AK 24.2.11 - Aufgabe 6 (Graphen) Dijkstra/Stack
Hallo,
ich hab mal noch ne Frage zu der AuD-Altklausur vom 24.2.11 zur Aufgabe 6 (Graphen): Man soll da einfach den Dijkstra anwenden, was eigentlich auch kein Problem ist, was ich aber im moment noch nicht versteh is der dazugehörige Stack. in meiner Lösung aus dem Vorbereitungskurs steht folgendes: Stack beim 1.Durchlauf: A Stack beim 2.Durchlauf: C, B Stack beim 3.Durchlauf: G, B Stack beim 4.Durchlauf: B, D, F Stack beim 5.Durchlauf: E, D, F Stack beim 6.Durchlauf: D, F Stack beim 7.Durchlauf: F, H Stack beim 8.Durchlauf: H, K Stack beim 9.Durchlauf: K, Z Stack beim 10.Durchlauf: Z Frage: Bei einem Stack wird ja immer von oben runtergenommen/aufgelegt, wieso wird zwischen 3. und 4. Durchlauf einfach D,F hinter B angefügt ? (Genau so ist es nach dem 7. bzw 8. Durchlauf mit H bzw K) Vielen Dank schonmal! |
Member since Jan 2012
18 posts
|
![]()
So wie ich das verstehe wird der Stack z.B. nach dem 3. Durchlauf, nach Entfernung angelegt.
Also in dem Fall die größte F mit 19. -> Stack: F D mit 15 Stack: D, F (D also auf F) B mit 9: B, D, F Knoten B ganz oben, wird als nächstes Betrachtet. Bei gleichen Entfernungen z.B. im 3. Durchlauf wird eben der ältere Knoten zuerst auf den Stack gelegt. Deshalb Stack: G, B. Also wird G als nächstes verwendet (jüngere Knoten). Den Stack hätte man bei der Aufgabe garnicht aufschreiben müssen oder? Es geht ja in dem Fall nur darum, welchen Knoten man bei gleichen Entfernungen zuerst bearbeitet. |
Member since Dec 2008
337 posts
|
![]()
Dijkstra verwendet eine Priority Queue und keinen Stack.
|
Member since Nov 2011
58 posts
|
![]()
In reply to post #2
Ah danke jetzt versteh ich des! Hab sowas schon vermutet als ich die anderen Graphenaufgaben gerechnet hab...
Ob man den jetzt hinschreiben soll war mich auch nich ganz klar, ist aber glaub ich nur zur Verdeutlichung in den Übungen besprochen worden. Ich seh das Thema damit als erledigt an! |
Member since Nov 2011
58 posts
|
![]()
In der Aufgabenstellung steht: "Setzen Sie für die noch zu bearbeitenden Orte einen Prioritätsstapel (Stack: bei gleicher Entfernung wird der jüngere Knoten gewählt) ein." |
Member since Dec 2008
337 posts
|
![]()
Dann gratuliere ich dem Aufgabenverfasser(n) zur erfolgreichen Verwirrungsstiftung.
Ich habe zwar noch nie etwas von einem Prioritätsstapel gehoert, aber die Bemerkung dass "bei gleicher Entfernung [...] der jüngere Knoten gewählt" wird legt nahe das der Aufgabensteller eine Prioritaetswarteschlange meint. |
Member since May 2011
452 posts
|
![]()
Bei einer Piroritätswarteschlange wird der ältere Knoten gewählt (bei gleicher Distanz) also ist das Prioritätsstack hier schon so gewollt (ganz davon abgesehen, ob es sowas gibt oder nicht)
|
Member since Oct 2011
189 posts
|
![]()
dachte grad schon ich wüsste nicht mehr wie ne prioritätswarteschlange geht nach dem ich den Kommentar von Mich gelesen hatte. |
Member since Dec 2008
337 posts
|
![]()
In reply to post #7
Stimmt, sorry das habe ich ueberlesen. Wichtig ist hier jedoch trotzdem das eine Priorisierung vorgenommen wird. Am Ergebnis aendert die Wahl des Elements welches man im Falle gleicher Distanz entnimmt aber nichts, sowohl aber am Loesungsweg. Insofern ist die Aufgabe fies, weil a) kein Standard Dijkstra und b) missverstaendlich formuliert. Man haet auch einfach Schreiben koennen "Verwenden sie eine Priority Queue die im Falle von gleicher Distanz den juengeren Key zurueckliefert". Was das mit dem Stack hier soll ist mir jedenfalls raetselhaft. |
Member since Feb 2012
34 posts
|
![]()
nein, weil eine Priority Queue sich mal eben dadurch definiert, dass sie im Zweifel den _älteren_ Key zurückliefert. Also muss es ein Priority Stack sein. Der Aufgabensteller hätte auch einfach mal eine Priority-Blubb definieren können (als ADT zum Beispiel, Transferaufgabe!), solange es keine namenskollision mit "PriorityQueue" (oder anderen Strukturen) gibt >_> |
Member since Dec 2008
337 posts
|
![]()
Meiner Meinung nach haette es zumindest die Verwirrung des OPs verhindert wenn dort LIFO Priority Queue gestanden haette anstatt Priority Stack.
Im uebrigen wo ist definiert das eine Priority Queue den aeltern zurueck liefert[1]? Ich finde nur Definitionen die es zwar implizieren aber explizit nur zusichern dass man die hoechste Prioritaet bekommt. Deshalb bleibe ich dabei Prioritaetsstack ist nicht nur nicht gebraeuchtlich sondern auch irrefuehrend. [1] m.E. ist diese FIFO Eigenschaft z.B. bei einer naiven Implementierung mittels Heap schon nicht mehr gegeben: 1, 1', 1'', 2 nacheinander in Heap => 2, 1, 1'', 1' , entnehme highest => 1', 1, 1'', noch mal highest => 1' sollte aber wegen FIFO Eigenschaft 1 sein. |
Datenschutz |
Kontakt
Powered by the Unclassified NewsBoard software, 20150713-dev,
© 2003-2011 by Yves Goergen