www.AlgorithMan.de
Where theory comes alive
2903 KiB
Meine Seminar-Ausarbeitung und -Vortragsfolien vom Hauptseminar exakte Algorithmen (WS2007/08) beim Lehrstuhl für theoretische Informatik (wo ich auch mein Diplom gemacht habe).
Mein Thema war das Minimum Quartet Inconsistency Problem (MQI) welches parametrisierbar ist (der Wikipedia Artikel über parametrisierte Algorithmen stammt übrigens von mir :-) ).
Im Rahmen des Seminars habe ich einen viel kürzeren (Widerspruchs-)Beweis für den Hauptsatz aus dem Paper von Niedermeier und Gramm gefunden und die Laufzeit von \(O(4^k\cdot n+n^4)\) verbessert auf \(O(3,561^k\cdot n+n^4)\).
16 KiB
Die Türme von Hanoi, ohne Ausprobieren mittels Backtracking, sondern mit straight forward bestimmten Verlege-Anweisungen.
Die Idee ist: um n Scheiben von A nach C zu verschieben,
verschiebe n-1 Scheiben von A nach B,
dann eine Scheibe von A nach C,
dann n-1 Scheiben von B nach C.
14 KiB
Ein Programm für das Rucksackproblem, das mit Branch-and-Bound arbeitet.
603 KiB
Ein Programm, das scramble square puzzles löst. Dadurch, dass immer die Position belegt wird, auf die die kleinste Anzahl von Puzzleteilen passt oder das Puzzleteil platziert wird, für das die kleinste Anzahl von Positionen in Frage kommt (jenachdem, was weniger ist), wird der Verzweigungs-Vektor sehr klein gehalten. Ausserdem werden Situationen erkannt und ausgenutzt, in denen mehrere Puzzleteile identisch sind und es werden symmetrische Lösungen vermieden. Das führt zu sehr guten Laufzeiten - in den Beispielen werden nur etwa 300-400 Rekursionen benötigt, obwohl es \((n\cdot 4)^n\) Kombinationen gibt. In den Rekursionsaufrufen werden jeweils \(O(4\cdot n^4)\) Schritte benötigt.
Ich habe auch eine alte Version dazu gepackt, die reines Backtracking verwendet, damit man den Unterschied in den Laufzeiten sehen kann.