Lösungsstrategie Foo #6

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

Lösungsstrategie Foo #6

Beitrag von Nullmann »

Kruskal:
Ist ziemlich einfach.
Die Reihenfolge des Einfügens ist angegeben und entspricht so auch die Reihenfolge der angegebenen Kanten. Bedeutet, man muss einfach nur alle Kanten von oben nach unten in die Menge der ausgewählten Kanten hinzufügen.
Würde das Hinzufügen einer Kante einen Kreis bilden, also ist der Knoten bereits Teil des Baumes, wird die Kante verworfen, also nicht ausgewählt. (Wenn man nicht vorher nachdenken will, kann man die Kante auch einfach hinzufügen und schauen, wo sich die neue grüne Kante befindet)
Am Ende fügt man alle Knoten, die durch grüne Kanten einen Baum bilden, in eine Menge ein. Einfach auf den Graphen schauen. (Tipp: Zuerst die großen Bäume hinzufügen, dann muss man beim Drag 'n Drop nicht so viel scrollen)

Hinweis: Es wurde berichtet, dass das Verschieben von Knoten, wenn sie schonmal in einer Menge waren, zu Bugs führen kann (Duplikation etc). Deshalb ist diese Methode gut, da man, wenn man alles richtig macht, nichts verschieben muss (Wie es der Algo an sich mit der Verbindung von Mengen macht). Falls man sich vertan hat ist es dann doch ratsamer, die Menge zu löschen anstatt Knoten zu verschieben.

Sicherheit:
Gibt es nicht direkt. Lediglich Iterationsschritt = Anzahl ausgewählter und verworfener Kanten. Bzw. Anzahl Knoten - 1 = Anzahl ausgewählte Kanten.
Helfen beide aber nicht direkt, weil diese durch die Anzahl der verworfenen Kanten im Vergleich zu dem Iterationsschritt variieren können.



Prim:
Kann sein, dass ich das komplett anders mache als andere. So finde ich die Aufgabe aber ziemlich einfach.

Zuerst alle Buchstaben von a bis j in Q schreiben.
Von dem Startknoten ausgehend die niedrigste Kante suchen
- diese in die ausgewählten Kanten hinzufügen
- die dazugehörigen Knoten löschen (Beide Knoten schon gelöscht? Dann darf die Kante nicht hinzugenommen werden!)

Dies wird im Prinzip immer weiter geführt, natürlich mit immer mehr Knoten, also einem wachsenden grünen Baum. Bis der gewünschte Iterationsschritt erreicht wurde.

Besonderheiten:
1) Wenn zwei Kanten die gleiche Gewichtung haben, wird die Kante gewählt, dessen Zielknoten lexikographisch niedriger ist. Die Kante j->a mit Gewichtung 3 wird einer Kante b->c mit Gewichtung 3 vorgezogen.
2) Besitzt ein Knoten mehrere, gleich gewichtete Kanten von dem grünen Baum aus, wird die Kante genommen, dessen Ausgangsknoten früher in den Baum aufgenommen wurde!

Sicherheit: Am Ende sind i Kanten in der Menge und i + 1 Knoten (Buchstaben) wurden aus Q gelöscht!

Ende:
Wir haben aber noch eine unsortierte Q.
Deshalb schreibe ich mir alle noch in Q verbleibenden Knoten auf ein Blatt Papier und notiere mir zu jedem, wie die kürzesten Strecken zu einem grünen Knoten sind. Danach (und ggf. lexikographisch) wird Q dann sortiert.
(Diesen Schritt müsste man laut Algo theoretisch jede Iteration machen. Da diese aber zu viel Arbeit ist und uns nur die momentan kürzeste Kante interessiert und alle anderen egal sind, reicht auch obiges, visuelles Verfahren. Weiß man während des Algos ziwschendurch nicht weiter, kann man natürlich trotzdem diesen Schritt anwenden!)

Sheldon
Erstie
Erstie
Beiträge: 20
Registriert: 23. Apr 2015 17:08

Re: Lösungsstrategie Foo #6

Beitrag von Sheldon »

Ende:
Wir haben aber noch eine unsortierte Q.
Deshalb schreibe ich mir alle noch in Q verbleibenden Knoten auf ein Blatt Papier und notiere mir zu jedem, wie die kürzesten Strecken zu einem grünen Knoten sind. Danach (und ggf. lexikographisch) wird Q dann sortiert.
Was wäre eigentlich, wenn die Größe des Graphen es zulässt, dass sich nach der geforderten Anzahl an Iterationsschritten Knoten in Q befinden, welche keinen unmittelbar "grünen" Nachbarknoten besitzen? Muss dann beim nachträglichen Sortieren einfach der kürzeste Weg zu dem nächstgelegenen grünen Knoten über mehrere Kanten hinweg gewählt werden?

Gruß Sheldon

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

Re: Lösungsstrategie Foo #6

Beitrag von Nullmann »

Dann wird in unserer Liste einfach unendlich eingetragen - und wie gewohnt alle Knoten mit unendlich untereinander lexikographisch sortiert :)
Edit: Wenn man sich das Video zu Prim anschaut, in der Q in jeder Iteration komplett geupdatet wird (wie es eine konkrete Implementation auch machen würde), sieht man genau solche Fälle.

Alexj1988
Mausschubser
Mausschubser
Beiträge: 69
Registriert: 23. Sep 2011 00:28

Re: Lösungsstrategie Foo #6

Beitrag von Alexj1988 »

Nullmann hat geschrieben:Dann wird in unserer Liste einfach unendlich eingetragen - und wie gewohnt alle Knoten mit unendlich untereinander lexikographisch sortiert :)
Edit: Wenn man sich das Video zu Prim anschaut, in der Q in jeder Iteration komplett geupdatet wird (wie es eine konkrete Implementation auch machen würde), sieht man genau solche Fälle.

Was die konkrete Implementierung auch macht ;)

Antworten

Zurück zu „Archiv“