Prim: Mehrere Kanten mit gleichem Gewicht - welche wählen?

headhumper
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 118
Registriert: 13. Aug 2009 21:25

Prim: Mehrere Kanten mit gleichem Gewicht - welche wählen?

Beitrag von headhumper »

Die Musterlösung wählt als nächste Kante (d,f), warum? (b,j) hat das gleiche Gewicht und kommt in der Sortierung früher.
Ich war/bin mir nicht sicher, wie "Hinweis: Die Menge V ist chronologisch Sortiert und wird auch in dieser Reihenfolge durchlaufen." zu verstehen ist.
Heißt das eventuell, dass zuerst die Kanten mit dem geringsten Gewicht genommen werden, die an einem Knoten hängen, der möglichst früh hinzugefügt wurde?

Edit: Aber das macht irgendwie auch keinen Sinn, denn b war der Startknoten... :?
prim.PNG
prim.PNG (232.75 KiB) 920 mal betrachtet
Zuletzt geändert von headhumper am 16. Jul 2015 00:52, insgesamt 1-mal geändert.

Alexj1988
Mausschubser
Mausschubser
Beiträge: 69
Registriert: 23. Sep 2011 00:28

Re: Prim: Mehrere Kanten mit gleichem Gewicht - welche wähle

Beitrag von Alexj1988 »

http://wiki.algo.informatik.tu-darmstadt.de/Prim

V ist eine Menge und daher eigentlich unsortiert. Aus gründen der Berechenbarkeit(Arbeitsspeicher) wird V als Liste behandelt, wobei V chronologisch sortiert ist.

aka es wird die Kante genommen, die für (v,w) als letztes die bedingung im Induktion step erfüllt hat genommen (aus dem vorherigen Induktion step.

mfg Alex

headhumper
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 118
Registriert: 13. Aug 2009 21:25

Re: Prim: Mehrere Kanten mit gleichem Gewicht - welche wähle

Beitrag von headhumper »

Dann verstehe ich es immer noch nicht...

Startknoten war f
c ist der jüngste Knoten

Jetzt wird im nächsten Schritt aber (a,d) gewählt und nicht (b,c) :?:
prim2.PNG
prim2.PNG (249.79 KiB) 909 mal betrachtet

Alexj1988
Mausschubser
Mausschubser
Beiträge: 69
Registriert: 23. Sep 2011 00:28

Re: Prim: Mehrere Kanten mit gleichem Gewicht - welche wähle

Beitrag von Alexj1988 »

headhumper hat geschrieben:Dann verstehe ich es immer noch nicht...

Startknoten war f
c ist der jüngste Knoten

Jetzt wird im nächsten Schritt aber (a,d) gewählt und nicht (b,c) :?:
prim2.PNG
Ok, da fehlt ein weiterer hinweis. Wird sofort erledigt. (Q wird ist nach Kantengewicht sortiert und bei gleichen Kantengewichten Chronologisch)

Schau am besten auch mal in die Musterlösung, da werden alle Mengen, Warteschlangen etc angegeben.

mfg Alex

Nullmann
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 139
Registriert: 21. Apr 2015 20:59

Re: Prim: Mehrere Kanten mit gleichem Gewicht - welche wähle

Beitrag von Nullmann »

Es ist immer nur wichtig, zu welchem Knoten die Kante geht! Egal, von welchem diese ausgeht.
Bei deinem ersten Beispiel: d->f und b->j; f kommt im Alphabet vor j
Bei deinem zweiten Beispiel: d->a und c->b; a kommt im Alphabet vor b

Wenn man sich momentan nicht sicher ist, welcher Knoten als nächstes abgearbeitet werden muss, kann man alle restlichen Knoten durchgehen und schauen, was die momentan kürzesten Wege zu dem grünen Baum ist. Ergibt sich dann die Situation wie oben, dass zwei Knoten die gleiche Gewichtung haben, wird der lexikographisch kleinere Knoten genommen.

headhumper
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 118
Registriert: 13. Aug 2009 21:25

Re: Prim: Mehrere Kanten mit gleichem Gewicht - welche wähle

Beitrag von headhumper »

Ah, ok! Aber was soll dann der "Hinweis: Die Menge V ist chronologisch Sortiert und wird auch in dieser Reihenfolge durchlaufen." sagen?
An welcher Stelle kommt die chronologische Sortierung ins Spiel :?:

(Oder sollte da ein anderes Wort als "chronologisch" stehen?)

Alexj1988
Mausschubser
Mausschubser
Beiträge: 69
Registriert: 23. Sep 2011 00:28

Re: Prim: Mehrere Kanten mit gleichem Gewicht - welche wähle

Beitrag von Alexj1988 »

headhumper hat geschrieben:Ah, ok! Aber was soll dann der "Hinweis: Die Menge V ist chronologisch Sortiert und wird auch in dieser Reihenfolge durchlaufen." sagen?
An welcher Stelle kommt die chronologische Sortierung ins Spiel :?:

(Oder sollte da ein anderes Wort als "chronologisch" stehen?)

Ups da sollte lexikographisch hin :oops:

mfg Alex

headhumper
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 118
Registriert: 13. Aug 2009 21:25

Re: Prim: Mehrere Kanten mit gleichem Gewicht - welche wähle

Beitrag von headhumper »

"Fremdwörter sind Glückssache"? :lol:

Dann ist jetzt hoffentlich alles geklärt, danke für die schnelle Hilfe :idea:

Alexj1988
Mausschubser
Mausschubser
Beiträge: 69
Registriert: 23. Sep 2011 00:28

Re: Prim: Mehrere Kanten mit gleichem Gewicht - welche wähle

Beitrag von Alexj1988 »

headhumper hat geschrieben:"Fremdwörter sind Glückssache"? :lol:

Dann ist jetzt hoffentlich alles geklärt, danke für die schnelle Hilfe :idea:
Frage mich immer noch wieso ich chronologisch geschrieben habe :/

Stan23
Neuling
Neuling
Beiträge: 2
Registriert: 2. Okt 2014 00:09

Re: Prim: Mehrere Kanten mit gleichem Gewicht - welche wähle

Beitrag von Stan23 »

Ich hab hier noch einen anderen Fall:

Mit welcher Begründung wird hier (b,e) und nicht (e,i) gewählt?
Ebenfalls die lexikographische Sortierung zwischen b und i? Ich kann mich dran erinnern, dass das nicht immer passte...

Gruß,
Stan
Dateianhänge
hc_018.jpg
hc_018.jpg (46.41 KiB) 762 mal betrachtet

Alexj1988
Mausschubser
Mausschubser
Beiträge: 69
Registriert: 23. Sep 2011 00:28

Re: Prim: Mehrere Kanten mit gleichem Gewicht - welche wähle

Beitrag von Alexj1988 »

Stan23 hat geschrieben:Ich hab hier noch einen anderen Fall:

Mit welcher Begründung wird hier (b,e) und nicht (e,i) gewählt?
Ebenfalls die lexikographische Sortierung zwischen b und i? Ich kann mich dran erinnern, dass das nicht immer passte...

Gruß,
Stan

Wie gesagt ins wiki schauen was im induction step passiert. Da kommt nämlich raus, das die Kante am Anfang gewählt wird die in der voriteration bestimmt wurde. (Und dabei wird V durchlaufen)

Stan23
Neuling
Neuling
Beiträge: 2
Registriert: 2. Okt 2014 00:09

Re: Prim: Mehrere Kanten mit gleichem Gewicht - welche wähle

Beitrag von Stan23 »

Danke! :)

Smith
Mausschubser
Mausschubser
Beiträge: 53
Registriert: 13. Apr 2015 15:45

Re: Prim: Mehrere Kanten mit gleichem Gewicht - welche wähle

Beitrag von Smith »

Ich dachte ich hätte es jetzt verstanden, aber wohl doch noch nicht ganz...
Wieso wird hier nun im nächsten Schritt die Kante b-g ausgewählt und nicht f-j (wird dann als nächstes erst in der Musterlösung gewählt), obwohl f der Startknoten war?
Hatte es jetzt so verstanden, dass die höchste Priorität bei gleicher Pfadlänge sei: welcher Knoten hat den Pfad mit momentan kürzester Länge zuerst gesehen. Dachte dass erst bei gleichen Pfadlängen vom selben Knoten ausgehend dann lexikographisch gewählt wird.
Wo ist der Denk- / Verständnisfehler?
foo6.jpg
foo6.jpg (54.16 KiB) 646 mal betrachtet

Alby407
Mausschubser
Mausschubser
Beiträge: 64
Registriert: 19. Jul 2014 15:40

Re: Prim: Mehrere Kanten mit gleichem Gewicht - welche wähle

Beitrag von Alby407 »

@Smith

g kommt doch vor j im Alphabet! :) Deshalb wird auch Kante b-g bevorzugt.

Smith
Mausschubser
Mausschubser
Beiträge: 53
Registriert: 13. Apr 2015 15:45

Re: Prim: Mehrere Kanten mit gleichem Gewicht - welche wähle

Beitrag von Smith »

@Alby407

Danke für deine Antwort, aber ich denke nicht, dass das so simpel ist.

Ich bestehe mit meiner Herangehensweise nahezu jede Aufgabe. Dabei gehe ich so vor, dass ich mir immer die Kante mit dem aktuell kürzesten Weg merke. Sei dieser der key der Kante, die Knoten a mit Knoten b verbindet. Kommt ein kürzerer Weg durch neue Verbindungen hinzu wird diese gewählt. Diese kürzere Kante verbinde beispielsweise Knoten b und c.
Sind jetzt durch c keine kürzeren Verbindungen hinzu gekommen und der kürzeste Weg ist in a und b gleich, so bevorzuge ich a (also zB a-x vor b-e), auch mehrfach, vor lexikographischer Ordnung, falls mehrere Kanten der selben, kürzesten, Länge von a abgehen.
Erst in dem Falle, dass in diesem Beispiel tatsächlich mehrere Kanten mit kürzester Länge von a abgehen, wird der lexikografisch niedrigste Zielknoten bevorzugt (also a-g vor a-x, aber beide vor b-e).
So habe ich das verstanden.

Was ist daran falsch?
Es scheint fast immer so zu klappen, aber anhand des Screenshots kann ich die Entscheidung in diesem Fall nicht nachvollziehen...

Dass einfach immer lexikografisch ausgewählt wird ist anhand von zahlreichen Versuchen von meiner Seite aus nicht korrekt.

Antworten

Zurück zu „Archiv“