Prim

[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]

Habe genau das gleiche Problem.
Hier ist Versuch 1:

Habe gewählt (a,d), die Musterlösung lautet:


Versuch 2:

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


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

[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]

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

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

[Jannis]

Jetzt hat zwar jemand schon einen Link geposted, da meine Antwort aber schon fertig ist, schicke ich sie einfach trotzdem ab

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]

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]

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]

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

[mProg]

Danke. Jetzt ist es vollkommen verständlich

[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.

[Nullmann]

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]

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