Prim

mProg
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 147
Registriert: 25. Apr 2015 00:10

Prim

Beitrag 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?

NonStop
Mausschubser
Mausschubser
Beiträge: 73
Registriert: 18. Apr 2015 19:15

Re: Prim

Beitrag 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?

mProg
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 147
Registriert: 25. Apr 2015 00:10

Re: Prim

Beitrag 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

robtothein
Mausschubser
Mausschubser
Beiträge: 57
Registriert: 1. Aug 2014 13:33

Re: Prim

Beitrag von robtothein »

Ich verlink euch mal einen Beitrag, wo es ganz gut beantwortet wurde. :)

/viewtopic.php?f=561&t=32997
VG,
robtothein

Jannis
Mausschubser
Mausschubser
Beiträge: 63
Registriert: 15. Apr 2015 17:10

Re: Prim

Beitrag 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

mProg
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 147
Registriert: 25. Apr 2015 00:10

Re: Prim

Beitrag 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?

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

Re: Prim

Beitrag 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

robtothein
Mausschubser
Mausschubser
Beiträge: 57
Registriert: 1. Aug 2014 13:33

Re: Prim

Beitrag 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
Dateianhänge
Unbenannt.png
Unbenannt.png (53.11 KiB) 867 mal betrachtet
VG,
robtothein

mProg
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 147
Registriert: 25. Apr 2015 00:10

Re: Prim

Beitrag von mProg »

Danke. Jetzt ist es vollkommen verständlich :)

NonStop
Mausschubser
Mausschubser
Beiträge: 73
Registriert: 18. Apr 2015 19:15

Re: Prim

Beitrag 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

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

Re: Prim

Beitrag 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"!

NonStop
Mausschubser
Mausschubser
Beiträge: 73
Registriert: 18. Apr 2015 19:15

Re: Prim

Beitrag 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 :)

Antworten

Zurück zu „Archiv“