Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
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!
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.
Dijkstra verwendet eine Priority Queue und keinen Stack.
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!
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.“
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.
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)
dachte grad schon ich wüsste nicht mehr wie ne prioritätswarteschlange geht nach dem ich den Kommentar von Mich gelesen hatte.
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.
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 >_>
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.