Not logged in. · Lost password · Register

NeubauMa
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!
This post was edited 2 times, last on 2012-02-21, 14:35 by NeubauMa.
F5
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.
This post was edited on 2012-02-21, 15:13 by F5.
Mich
Member since Dec 2008
337 posts
Dijkstra verwendet eine Priority Queue und keinen Stack.
NeubauMa
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!
NeubauMa
Member since Nov 2011
58 posts
Dijkstra verwendet eine Priority Queue und keinen Stack.

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."
Mich
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.
ri31hoky
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)
bewi1992
Member since Oct 2011
189 posts
Quote by ri31hoky:
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.
Mich
Member since Dec 2008
337 posts
In reply to post #7
Quote by ri31hoky:
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)

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.
DrunkenMan
Member since Feb 2012
33 posts
Quote by Mich:
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 >_>
Mich
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.
This post was edited on 2012-02-22, 13:40 by Mich.
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