Wiki: Prim

null
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 168
Registriert: 21. Apr 2012 14:58

Wiki: Prim

Beitrag von null »

Hallo zusammen,

mir ist der Induktionsschritt des Algorithmus von Prim in der Wiki nicht ganz klar. Angenommen man habe diesen Graphen:

Bild

Nach der Induktionsbasis gilt:

Q = {v1, v2, v3, v4, v5}
V0 = {s}
kv1 = 2
kv3 = 3
kv2 = kv4 = kv4 = Infinity


Nun bin ich beim Induktionsschritt, der mir aber Probleme bereitet:

1.) Ich nehme den ersten Knoten v aus Q. Da Q ein Heap ist, erhalte ich den Knoten mit dem kleinsten kv. Das ist v1.
2.) e ist laut Vorlesung die Kante von s nach v1.
3.) Für jedes w € V\Vi-1, also w € {v1, v2, v3, v4, v5} wird geprüft, ob eine noch kürzere Kante abgeht. Hier wird kv1 = 1 gesetzt, weil von v1 nur genau eine Kante abgeht, die auch noch kürzer ist.
4.) Ich füge die Kante zwischene e, also diejenige zwischen s und v1, meiner MST Kantenmeneg E hinzu und gleichzeit füge ich w, also v2 zu meiner MST Knotenmenge hinzu.

Das kann doch nicht sein. Ich müsste doch v1 hinzufügen. Es wird aber v2 gespeichert werden. Übersehe ich da etwas? Könnt ihr mir helfen?

Vielen Dank

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Wiki: Prim

Beitrag von Prof. Karsten Weihe »

null hat geschrieben:Nun bin ich beim Induktionsschritt, der mir aber Probleme bereitet:
Gemäß History hat Wiki-User Ruebensaft heute genau zu diesem Punkt Änderungen gemacht. Hat sich Ihr Problem damit gelöst? Ich finde Ihr Problem jedenfalls nicht in der aktuellen Version (meinen Dank an "Ruebensaft"!).

KW

null
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 168
Registriert: 21. Apr 2012 14:58

Re: Wiki: Prim

Beitrag von null »

Hallo,

mit der Wikiänderung macht nun der Eintrag schon mehr Sinn. Trotzdem habe ich noch eine Frage zu folgendem Satz:

"Let e denote the edge stored as information for v in Q"

Aus der Vorlesung weiß ich, dass e wohl die Kante zwischen v und w bezeichnet, doch liest man nur den Wikieartikel, so wird nicht klar, welche Kante gemeint ist.

Außerdem habe ich noch eine Frage dazu:

"Set {v,w} as the new information for w in Q".

Jeder Knoten w, der von dem Knoten v im grünen Bereich erreicht werden kann, erhält nun die Kante e als Information!?

Habe ich das richtig verstanden?

Vielen Dank
null

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Wiki: Prim

Beitrag von Prof. Karsten Weihe »

null hat geschrieben: "Let e denote the edge stored as information for v in Q"

Aus der Vorlesung weiß ich, dass e wohl die Kante zwischen v und w bezeichnet, doch liest man nur den Wikieartikel, so wird nicht klar, welche Kante gemeint ist.
Im Wiki steht bei der Einführung von \(Q\): "... the information is one of the edges of \(G\) that is incident to \(v\)." Schritt 3.1 des Induction step lautet: "Set \(\{v,w\}\) as the new information for \(w\) in \(Q\)." Welche Information fehlt :?:

null hat geschrieben: Jeder Knoten w, der von dem Knoten v im grünen Bereich erreicht werden kann, erhält nun die Kante e als Information!?
Nein, nur jeder dieser Knoten, der die Bedingung \(\ell(\{v,w\})<k_v\) eine Zeile drüber erfüllt. :roll: :wink:

KW

null
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 168
Registriert: 21. Apr 2012 14:58

Re: Wiki: Prim

Beitrag von null »

Hallo,

vielen Dank für die Antwort. Diese hilft mir schon weiter.

Heißt das also, dass e irgendeine Kante ist, an auf der v liegt? Sollte e nicht eine minimale Länge haben?

Vielen Dank

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Wiki: Prim

Beitrag von Prof. Karsten Weihe »

null hat geschrieben: Heißt das also, dass e irgendeine Kante ist, an dessen Ende v liegt.
Nein :!: :roll: :wink:

Die Kante \(e\) ist so gewählt, dass die dritte Invariante erfüllt ist. Dafür wird durch die Abfrage \(\ell(\{v,w\})<k_v\) gesorgt.

KW

null
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 168
Registriert: 21. Apr 2012 14:58

Re: Wiki: Prim

Beitrag von null »

Aber bei der Initialisierung wurde diese Abfrage doch noch nicht gemacht. Trotzdem hat ja wohl jeder Knoten schon eine Information. e wird vor dieser Abfrage, nämlich im 2. Schritt des Induktionsschritts ausgelesen. Was ist denn hier dann e hier im ersten Schritt? Da gab es noch kein l(v,w) < kv

edit: Ich möchte einfach nur sagen, dass e nicht immer durch die Abfrage l(v,w) < kv gesetzt ist. Falls dies nicht der Fall ist, so ist e genau die Kante, das v der letzten Iteration mit dem aktuellen verbindet. Das finde ich nicht in der Wiki.

Warum speichern wir eigentlich Vi ab? Vi ist am Schluss sowieso wieder V.

Danke :)
Zuletzt geändert von null am 9. Jul 2012 12:04, insgesamt 1-mal geändert.

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Wiki: Prim

Beitrag von Prof. Karsten Weihe »

null hat geschrieben:Aber bei der Initialisierung wurde diese Abfrage doch noch nicht gemacht.
Muss sie auch nicht, hier kann man die dritte Invariante einfacher erfüllen:

Es ist ja \(V_0=\{s\}\). Das heißt, es lässt sich sehr genau sagen, für welche Knoten \(v\in V\setminus V_0\;\) schon \(k_v<+\infty\) vor der ersten Iteration gilt, nämlich alle, die mit \(s\) durch eine Kante verbunden sind. Und es gibt nur maximal eine Kante , die \(v\) mit Knoten aus \(V_0\) verbindet, nämlich \(\{s,v\}\), also ist \(\{s,v\}\) die als Info zu speichernde Kante.

KW

null
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 168
Registriert: 21. Apr 2012 14:58

Re: Wiki: Prim

Beitrag von null »

Ok. Das passt zu meinem edit-Beitrag, oder? Danke für Ihre Hilfe. Die Information, dass e genau die Kante der v der letzten Iteration mit dem aktuellen ist, falls e nicht expliziet gesetzt worden ist, sollte meines Erachtens noch einmal explizit in der Wiki aufgeführt werden. Auch wenn es so vielleicht schon formal richtig ist.....darauf kommen nicht viele.

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Wiki: Prim

Beitrag von Prof. Karsten Weihe »

null hat geschrieben: Warum speichern wir eigentlich Vi ab?
Wir speichern \(V_i\) nicht, sondern benutzen das Kürzel \(V_i\) nur, um über den Algorithmus zu sprechen. In \(Q\) speichern wir \(V\setminus V_i\) ab.

Nebenbemerkung: Wir könnten genauso gut auch nur diejenigen Knoten \(v\in V\setminus V_i\) abspeichern, für die \(k_v<+\infty\) gilt, damit würde der Algorithmus immer noch funktionieren.

KW

sab
Mausschubser
Mausschubser
Beiträge: 97
Registriert: 28. Okt 2011 08:42

Re: Wiki: Prim

Beitrag von sab »

Prof. Karsten Weihe hat geschrieben:Die Kante \(e\) ist so gewählt, dass die dritte Invariante erfüllt ist. Dafür wird durch die Abfrage \(\ell(\{v,w\})<k_v\) gesorgt.
Edit 2:
Hat sich geklärt.

sab
Mausschubser
Mausschubser
Beiträge: 97
Registriert: 28. Okt 2011 08:42

Re: Wiki: Prim

Beitrag von sab »

Sorry, mir wird es jetzt doch nicht klar: Warum habe ich als Bedingung im Induction Step \(\ell({v,w}) < k_{w}\) und nicht \(< k_{v}\)?

Seldon
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 119
Registriert: 19. Apr 2012 18:12

Re: Wiki: Prim

Beitrag von Seldon »

Der Knoten v ist derjenige, den du gerade aus der Queue herausgenommen hast; es sollen alle restlichen w aus Q bei Bedarf aktualisiert werden (wenn also eine Kante e(v, w) existiert und deren l kleiner als die gespeicherte, einem Knoten zugeordnete Kante).

sab
Mausschubser
Mausschubser
Beiträge: 97
Registriert: 28. Okt 2011 08:42

Re: Wiki: Prim

Beitrag von sab »

Danke, Seldon, du hast gerade einen großen Knoten in meinem Kopf gelöst! So macht alles sind, mir war nicht ganz klar, dass es das \(k_{w}\) aus Q ist. Aber eigentlich steht das implizit in Aux. Data 2. :)

mcdikki
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 117
Registriert: 22. Okt 2007 17:16
Wohnort: Frankfurt

Re: Wiki: Prim

Beitrag von mcdikki »

Ganz einfach weil v nicht mehr in Q ist, sondern schon teil des Ergebnisses und damit kv nicht mehr interessant ist. Wir suchen ja eine Kante {v,w} für fixes v und unbekanntes w. Das heißt wir nehmen v aus Q und bringen w rein bzw. aktualiseren es. Ergo ist l(v,w) < kw interessant.

lg mcdikki

Update: Zu Spät ;-)

Antworten

Zurück zu „Archiv“