In der Fragestunde vor der Klausur wurde gefragt, ob es beim Kernighan-Lin-Algorithmus nicht immer reichen würde, nur die erste Hälfte an Vertauschungen durchzuführen, weil danach das Optimum nicht mehr erreicht werden könnte. Diese Beobachtung wurde wahrscheinlich beim Durchrechnen verschiedener Partitionen gemacht.
Ich habe die Sache mal durchgedacht und bin dazu gekommen, dass es bei Partitionen mit 4 oder weniger Knoten pro Menge wirklich so ist, dass das Optimum innerhalb der ersten Hälfte der Vertauschungen gefunden wird. Bei Partitionen mit 5 oder mehr Knoten pro Menge ist das allerdings nicht mehr so, weswegen der Algorithmus auf jeden Fall bis zuende durchlaufen muss. Ausführlicheres steht in der hier angehängten Datei!
Das ist dann auch die Begründung dafür, warum wir das Durchrechnen bis zuende in den Übungen und in der Klausur verlangen, auch wenn es für die kleinen Beispiele dort eigentlich überflüssig wäre, den Algorithmus bis zuende durchzuführen. Es geht uns darum, dass man einmal nachvollzogen hat, wie er als ganzes abläuft.
(In der Klausur scheint das auch für die meisten kein Problem gewesen zu sein; der Mittelwert der erreichten Punkte von Aufgabe 4 lag bei 12,36 von 14 Punkten...)
Viele Grüße,
Linus
1 mal bearbeitet. Zuletzt am 30.09.2011 13:21 von Linus F..
