Prim
Prim
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?
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?
-
- Mausschubser
- Beiträge: 57
- Registriert: 1. Aug 2014 13:33
Re: Prim
VG,
robtothein
robtothein
Re: Prim
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

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
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?
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
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
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
-
- Mausschubser
- Beiträge: 57
- Registriert: 1. Aug 2014 13:33
Re: Prim
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
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

- Dateianhänge
-
- Unbenannt.png (53.11 KiB) 1088 mal betrachtet
VG,
robtothein
robtothein
Re: Prim
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.


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


Re: Prim
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.NonStop hat geschrieben:Und warum wird in diesem Fall die Kante (c,b) und nicht (d,e) gewählt? Der Startknoten ist hier d.
Situation 2 entsteht nur, wenn zwei Kanten den gleichen Knoten "ansteuern"!
Re: Prim
Danke sehr, jetzt klappt es tatsächlich mit PrimNullmann hat geschrieben: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.NonStop hat geschrieben:Und warum wird in diesem Fall die Kante (c,b) und nicht (d,e) gewählt? Der Startknoten ist hier d.
Situation 2 entsteht nur, wenn zwei Kanten den gleichen Knoten "ansteuern"!
