Komplexitätsaussagen

Das Problem und seine Größe

Ein Affenpuzzle besteht aus einem quadratischen Kartenfeld, dessen Karten passend aneinandergelegt werden sollen.

Die Problemgröße lässt sich hier durch die Anzahl der Karten, die eine Seite des Kartenfeldes bilden, beschreiben. Das zur Abbildung oben gehörende Problem hat demnach die Problemgröße n = 3.

Ein Algorithmus zur Lösung des Affenpuzzles

Ein naiver Algorithmus zur Lösung des Affenpuzzles könnte systematisch alle Kartenkonfigurationen erzeugen und überprüfen:

ALGORITHMUS affenpuzzle(n):
    erzeuge n*n Karten
    erzeuge die Startpermutation der Karten
    SOLANGE die letzte Permutation noch nicht erreicht und noch keine Lösung gefunden ist:
        erzeuge eine Startorientierung der Karten
        SOLANGE die letzte Orientierungen noch nicht erreicht ist:
            erzeuge das Kartenfeld zur Permutation und zur Orientierung
            überprüfe das Kartenfeld
            WENN ok:
                Lösung = Kartenfeld
            erzeuge die nächste Orientierung
        erzeuge die nächste Permutation
    Rückgabe: (Karten, Lösung)

Beachte, dass der hier dargestellte Algorithmus auf vielerlei Weisen verbessert werden kann. Z.B. kann man mit dem Überprüfen aufhören, wenn zwei nicht passende Karten gefunden sind.

Abschätzung des Berechnungsaufwands

Implementiert man den gezeigten Algorithmus, so zeigen bereits Testaufrufe für kleine Problemgrößen, dass man mit sehr langen Laufzeiten rechnen muss. Bereits für die Problemgröße n = 3 verliert man die Geduld, auf ein Ergebnis zu warten.

In Fällen wie diesem, in denen nicht klar ist, wann mit einem Ergebnis zu rechnen ist, empfiehlt es sich, den Berechnungsaufwand genauer zu analysieren und abzuschätzen.

Der Berechnungsaufwand wird hier wesentlich durch die Anzahl der Kartenkonfigurationen bestimmt, die hier systematisch erzeugt und überprüft werden. Mit der Kostenfunktion K(n) beschreiben wir diesen Berechnungsaufwand: K(n) gibt an, wie viele verschiedene Kartenkonfigurationen es bei einer Problemgröße n gibt.

Die Herleitung einer Formel für K(n) soll hier für den Fall n = 3 durchgespielt werden.

Im Fall n = 3 gibt es insgesamt 3*3 = 9 Karten.

Wenn man jetzt eine Kartenreihenfolge bildet, dann gibt es 9 Möglichkeiten für die erste Karte, 8 Möglichkeiten für die zweite Karte, 7 Möglichkeiten für die dritte Karte, ... 2 Möglichkeiten für die achte Karte und schließlich 1 Möglichkeit für die neunte Karte.

Ingesamt können bei 9 Karten also 9*8*7*6*5*4*3*2*1 verschiedene Kartenreihenfolgen (Permutationen) gebildet werden. Mathematiker schreiben auch 9! (gelesen: 9 Fakultät) für das Produkt 9*8*7*6*5*4*3*2*1.

Wenn eine bestimmte Kartenreihenfolge vorliegt, dann können alle 9 Karten in jeweils 4 verschiedenen Weisen ausgerichtet werden. Zu jeder Kartenreihenfolge gibt es also 4*4*4*4*4*4*4*4*4 verschiedene Orientierungen der Karten. Mathematiker schreiben für das Produkt 4*4*4*4*4*4*4*4*4 kurz 4⁹.

Wenn man beide Ergebnisse zusammenfasst, dann ergeben sich im Fall n = 3 insgesamt 4⁹*9! bzw. 4^(3*3)*(3*3)! verschiedene Kartenkonfigurationen.

Wenn man die Überlegungen verallgeinert, so erhält man die Formel:

K(n) = 4(n*n)*(n*n)!

Praktische Anwendbarkeit des Algorithmus

Wir berechnen zunächst einige Werte der Kostenfunktion K(n) = 4^(n*n)*(n*n)!:

T(2) = 6144
T(3) = 95126814720
T(4) = 89862698310039502848000
T(5) = 17464069942802730897824646237782016000000
T(6) = 1756688818283804381631563107501689976914509549544878899200000000
...

Die wenigen Werte zeigen bereits, dass die Funktion K(n) sehr schnell wächst und bereits für kleine n-Werte riesige Funktionswerte liefert.

Wenn man davon ausgeht, dass ein Rechner zur Erzeugung und Überprüfung von 1 Million Konfigurationen 1 Sekunde benötigt, dann besagt der Wert T(3) = 95126814720, dass für ein 3x3-Puzzle im ungünstigsten Fall mehr als 95126 Sekunden (das ist mehr als ein Tag) benögt werden.

Aufgabe 1

(a) Schätze ab, wie lange ein Rechner im ungünstigsten Fall zur Überprüfung eines 4x4-Puzzles (5x5-Puzzles) benötigt. Gehe hier zunächst auch davon aus, dass ein Rechner zur Erzeugung und Überprüfung von 1 Million Konfigurationen 1 Sekunde benötigt.

(b) Die Erfahrung lehrt, dass künftige Rechnergenerationen viel schneller sind. Wie wirkt es sich aus, wenn Rechner 1000mal bzw. 1000000mal schneller sind als in der Hochrechnung oben angenommen wurde?

(c) Warum kann man sagen, dass der Algorithmus praktisch nicht anwendbar ist?

(d) Mache Vorschläge, wie man den naiven Algorithmus verbessern könnte.

Verbesserte Algorithmen

Der oben gezeigte naive Algorithmus zur Bestimmung der Lösung eines Affenpuzzles ist in der Praxis nicht anwendbar. Nur für sehr kleine Problemgrößen erhält man in akzeptabler Zeit ein Ergebnis.

Diese Eigenschaft spiegelt sich im Wachstumsverhalten der Kostenfunktion wider. Die Kostenfunktion K(n) = 4^(n*n)*(n*n)! wächst schneller als jede Exponentialfunktion.

Man kann jetzt versuchen, durch Überlegungen die Anzahl der zu überprüfenden Kartenkonfigurationen zu reduzieren (vgl. auch Affenpuzzle_GeroScholz.pdf).

Verbesserte Algorithmen zeigen dann ein durchaus akzeptables Laufzeitverhalten für Problemgrößen bis n = 5. Mit wachsender Problemgröße zeigen sich aber dieselben Schwierigkeiten wie beim naiven Algorithmus: Die Kostenfunktion wächst so schnell, dass eine geringe Erhöhung der Problemgröße das Laufzeitverhalten explodieren lässt.

Algorithmen mit einer exponentiellen oder noch ungünstigeren (Zeit-) Komplexität gelten als praktisch nicht anwendbar, da nur für kleine Problemgrößen akzeptable Laufzeiten - auch bei künftigen Rechnergenerationen - zu erwarten sind.

Ob es Algorithmen zur Lösung des Affenpuzzles gibt, deren (Zeit-) Komplexität günstiger als exponentiell ist, ist nicht bekannt.