AK 24.2.11 - Aufgabe 6 (Graphen) Dijkstra/Stack

Forum: Bachelor › Algorithmik › Algorithmen und Datenstrukturen

NeubauMa

Member since Nov 2011

58 posts

2012-02-21, 14:32 #1

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.

Member since Jan 2012

18 posts

2012-02-21, 15:12 #2

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	2012-02-21, 15:27 #3 +0 +0 Dijkstra verwendet eine Priority Queue und keinen Stack.

NeubauMa Member since Nov 2011 58 posts	2012-02-21, 15:29 #4 In reply to post #2 +0 +0 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	2012-02-21, 15:31 #5 +0 +0 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	2012-02-21, 15:43 #6 +0 +0 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	2012-02-21, 16:32 #7 +0 +0 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	2012-02-21, 16:41 #8 +0 +0 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

2012-02-21, 17:17 #9

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

2012-02-22, 13:06 #10

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

2012-02-22, 13:37 #11

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.

Go to forum

Datenschutz | Kontakt