Seite 1 von 1

Prim

Verfasst: 16. Sep 2015 16:04
von mProg
Ich habe die folgende Aufgabe gehabt:
https://foo.algo.informatik.tu-darmstad ... 4ed1fc67b5
Hier verstehe ich eins nicht: Ich habe die Kante (b,f) mit dem Wert 4 gewählt, aber die Lösung war (c,f) mit dem Wert 4. Beide Kanten haben den Wert 4. Und wenn ich mich nicht irre, ist (b,f) lexiographisch vor (c,f). Warum ist dann (c,f) die richtige Lösung?

Re: Prim

Verfasst: 16. Sep 2015 16:08
von NonStop
Habe genau das gleiche Problem.
Hier ist Versuch 1:
Bild
Habe gewählt (a,d), die Musterlösung lautet:
Bild

Versuch 2:
Bild
Habe gewählt (a,i), die Musterlösung lautet:
Bild

Habe ich etwas falsch verstanden, oder funktioniert Prim auf foo-Plattform falsch?

Re: Prim

Verfasst: 16. Sep 2015 16:28
von mProg
Weiß ich auch nicht. Habe auch andere Kommilitonen gefragt, aber die waren auch ratlos. Leider antwortet hier keiner. Bzgl die anderen Fehler kriege ich auch keine Rückmeldung

Re: Prim

Verfasst: 16. Sep 2015 16:34
von robtothein
Ich verlink euch mal einen Beitrag, wo es ganz gut beantwortet wurde. :)

/viewtopic.php?f=561&t=32997

Re: Prim

Verfasst: 16. Sep 2015 16:39
von Jannis
Jetzt hat zwar jemand schon einen Link geposted, da meine Antwort aber schon fertig ist, schicke ich sie einfach trotzdem ab :roll:

Bezüglich OP:

So wie ich das sehe liegt das daran, dass die Notation bei Foo leider etwas uneindeutig ist.
An sich ist es recht einfach: Wie du nach Induktionsschritt 1 siehst, ist hier bereits K1(f) = 2 gesetzt. D.h. der kürzeste Abstand von einem bereits erledigten Knoten zu f ist 2. Gemeint ist hier die Kante (c,f) - das steht bei der Foo-Notation leider nicht dabei.

Im 2. Schritt wird dann die Kante (j,b) statt (c,f) genommen, da b lexikographisch vor f kommt.
Hier wird es aber interessant: Nach diesem Schritt wird der Abstand zum Knoten f nicht aktualisiert, da die Länge von (b,f) = 2 nicht kürzer ist, als der bisher gespeicherte Abstand K(f) = 2.

Somit ist dann im 4. Schritt natürlich auch (c,f) genommen, da diese Kante ja sozusagen "zuerst entdeckt" wurde und keine daraufhin gesehene Kante zu f hin echt kürzer war.

Kann natürlich auch falsch sein, aber so hatte ich bis jetzt immer die Prim-Aufgaben bearbeitet. Ich hoffe ich konnte weiterhelfen

Re: Prim

Verfasst: 16. Sep 2015 16:54
von mProg
Danke für die Antwort und den Link. Aber ich denke ich habe hier einen Widerspruch
https://foo.algo.informatik.tu-darmstad ... 66ba60cf93
Hier fangen wir mit dem Knoten i an. Die Kante i-d hat den Wert 7, deshalb wird in Schritt 1 e-i mit Wert 6 genommen, in 2 a-e mit Wert 1, in 3 e-g mit Wert 1, und jetzt kommts: Obwohl wir in Schritt 1 i-d mit Wert 7 hatten, nimmt foo in Schritt 4 b-g mit Wert 7, also gleicher Wert und i-d war schon von Anfang da, aber der nimmt den neuen Knoten mit b-g? Wieso passiert nun das?

Re: Prim

Verfasst: 16. Sep 2015 17:36
von Nullmann
Ich verlinke hier erstmal zu meiner Lösungsstrategie zu Prim, die man sich durchlesen sollte: viewtopic.php?f=561&t=32741

Hier wurde anscheinend ein Denkfehler begangen. Meine schon oben verlinkte Antwort findet in dem zuletzt genannten Beispiel von mProg nämlich überhaupt keine Anwendung (Hier ist die Lösung von Foo korrekt). Eventuell hätte ich mich dort besser ausdrücken sollen. Es gibt verschiedene Situationen:

1) Es gibt mehrere Knoten mit den gleichen Kantengewichten, zu verschiedenen Knoten - dann wird derjenige (Ziel-)Knoten genommen, welcher lexikographisch niedriger ist.
Beispiel: Die Kanten a->j und b->g besitzen beide das gleiche Gewicht. Hier wird die Kante b->g hinzugefügt, weil g als Zielknoten lexikographisch vor j liegt.

2) Es gibt einen Knoten, zu dem mehrere, gleich schwere Kanten vom grünen Pfad aus führen. Dann wird die Kante hinzugefügt, dessen Startknoten zuerst in die Ergebnismenge hinzugefügt wurde (d.h. bei der Vereinfachung, wenn man alle Kanten untereinander in E hinzufügt, wird der obere Knoten genommen)
Beispiel: Die Kanten a->j und b->j besitzen beide das gleiche Gewicht. Der Einfachheit halber sei b hier der Startknoten. Dann würde die Kante b->j hinzugefügt werden, weil b zuerst in die Ergebnismenge hinzugefügt wurde.

Bei den obigen Beispielen von NonStop finden vermutlich jeweils Situation 2 statt.

Hoffe es hift,
Nullmann

Re: Prim

Verfasst: 16. Sep 2015 17:42
von robtothein
Du verwechselst zwei Fälle.

Erster Fall(links im Bild): g->b wird vor i->d bevorzugt, weil b lexikographisch kleiner als d.
Zweiter Fall(rechts im Bild): e->b wird vor g->b bevorzugt, weil e zuerst hinzugefügt wurde.

Den zweiten Fall siehst du auch bei e->d und i->d, falls man die Kante g->b ignorieren würde.

Edit: Nullmann war schneller :D

Re: Prim

Verfasst: 16. Sep 2015 18:05
von mProg
Danke. Jetzt ist es vollkommen verständlich :)

Re: Prim

Verfasst: 16. Sep 2015 18:47
von NonStop
https://foo.algo.informatik.tu-darmstad ... 1dc4deecd0

Und warum wird in diesem Fall die Kante (c,b) und nicht (d,e) gewählt? Der Startknoten ist hier d.
Bild
Bild

Re: Prim

Verfasst: 16. Sep 2015 19:01
von Nullmann
NonStop hat geschrieben:Und warum wird in diesem Fall die Kante (c,b) und nicht (d,e) gewählt? Der Startknoten ist hier d.
Weil b lexikographisch niedriger ist als e. Es sind doch zwei verschiedene Knoten, die "angesteuert" werden. Siehe Situation 1 wie bei mir oben und bei meiner ursprünlichen Lösungsstrategie beschrieben, oder der linke Graph bei dem Bild von robtothein.
Situation 2 entsteht nur, wenn zwei Kanten den gleichen Knoten "ansteuern"!

Re: Prim

Verfasst: 16. Sep 2015 20:11
von NonStop
Nullmann hat geschrieben:
NonStop hat geschrieben:Und warum wird in diesem Fall die Kante (c,b) und nicht (d,e) gewählt? Der Startknoten ist hier d.
Weil b lexikographisch niedriger ist als e. Es sind doch zwei verschiedene Knoten, die "angesteuert" werden. Siehe Situation 1 wie bei mir oben und bei meiner ursprünlichen Lösungsstrategie beschrieben, oder der linke Graph bei dem Bild von robtothein.
Situation 2 entsteht nur, wenn zwei Kanten den gleichen Knoten "ansteuern"!
Danke sehr, jetzt klappt es tatsächlich mit Prim :)