From: Jan Hoffmann (hoffmann@informatik.uni-muenchen.de)
Date: Mon Jul 07 2003 - 16:18:02 CEST
Ich habe mir heute morgen noch einmal die Musterlösung zur Aufgabe 34
(Kruskal-Alg.) angesehen. In der Übung fand ich das ja alles noch ganz
einleuchtend aber jetzt irgendwie nicht mehr so sehr:
Die Lösung ist zwar ein Beweis der Korrektheit des Alg., aber mit den
Definitionen die Sie da angeben wird das Optimierungsproblem ja einfach
wegdefiniert. Wenn Sie als Lösungsbestandteile nur sichere Kanten zulassen,
hat das doch zur Folge, dass einfach jede mögliche Lösung optimal (also min.
Spannbaum) ist. Ihre Problemstellung ist quasi: Erweitere eine Teilmenge
eines MST zu einem MST. Was soll man da optimieren? Es ist daher auch nicht
sehr aufwendig (und überflüssig) mit greedy-choice und Reflexion d. Lg. die
Optimalität der Lösung nachzuweisen. Denn wenn man nur Lösungsbestandteile
hat, die sichere Kanten sind, kann man nur eine Optimale Lösung (min.
Spannbaum) wählen, egal was man macht.
Sie benutzen die greedy-Auswahl des Alg. nur um z.z. dass die gewählte Kante
sicher ist. Also greedy-Auswahl => Korrekte Wahl eines Lsgsbestandteils. Sie
sollten aber damit eingendlich die Optimalität der Lösung zeigen, was bei
Ihnen aber schon implizit ist.
Wenn Sie jetzt argumentieren, dass das in dem Fall für den Beweis der
Korrektheit keine Rolle spielt, haben Sie natürlich recht. Aber es ist dann
meiner Meinung nach kein Fall mehr bei dem man diesen "Greedy-Formalismus"
anwenden kann.
Um das zu können müsste man auch nicht-optimale Lösungen zu lassen (bzw.
Bestandteile die zu solchen führen) und zeigen, dass durch die greedy-Wahl
eine optimale entsteht. Vielleicht so:
Instanz: (G,w,A) mit A azyklisch
Gesucht: B minimal mit A u B azyklisch
Lsgbestandteile: e aus E mit A u {e} azyklisch
Jetzt müsste man wirklich mit greedy-choice und Reflexion zeigen dass durch
greedy-Wahl B minimal gewähtl wird, also ein min. Spannbaum entsteht......
Das ist aber wieder sehr ungeschickt, da man die Tatsache nicht benutzt, dass
A ja schon ein Teil eines MST ist......
Vielleicht ist die Korrektheit hier sehr viel einfacher ohne den
Greedy-Formalismus zu zeigen!?
Oder nicht??
Gruß Jan
This archive was generated by hypermail 2.1.5 : Mon Jul 07 2003 - 16:25:00 CEST