Obwohl einige Aufgaben nicht schwieriger aussehen als andere, bereiten sie manchen Computerprogrammen große Schwierigkeiten. Wir erwarten eine Lösungszeit innerhalb von Sekunden, erhalten aber auch nach einer Stunde noch keine einzige Lösung. Wohlgemerkt sprechen wir durchaus von lösbaren Aufgaben, die auch eine vergleichbar große Anzahl von Lösungen haben
Wir wollen uns das Problem an einem Beispiel und dem Lösungsversuch mit dem PolySolver anschauen.
Aufgabe 11: Rechteck 15x15 mit U-förmigem Loch der Breite 13
Im 15x15-Quadrat bleiben 15 Elementarquadrate durch Hexominos unbelegt, wie wir bereits bei den Aufgaben 3-7 aus den Aufgaben für Hexominos (Nr. 1-10) gesehen haben. Diesmal formen wir aus den 15 überzähligen Elementarquadraten ein U-förmigem Loch der Breite 13 (im Bild schwarz) und versuchen den verbleibenden Platz mit den Hexominos zu füllen. Obwohl der PolySolver normalerweise weniger als 10 Sekunden für eine derartige Aufgabe benötigt, wird hier so schnell keine Lösung gefunden. Zwischendurch sieht der Zustand beispielsweise folgendermaßen aus:
Wenn keine Steine mehr einzufügen gehen, macht das Programm Backtracking. Dabei werden die zuletzt eingefügten Steine wieder entfernt und es wird anders versucht, die jetzt größeren Lücken zu füllen.
Wo ist das Problem? Schauen Sie sich die Größe der beiden verbliebenen Restflächen an: Diese betragen 11 (oben) bzw. 13 (unten). Diese lassen sich nicht mit Steinen der Größe 6 füllen, auch wenn man einige Steine herausnimmt und umsortiert. Man müsste mindestens soviel Steine herausnehmen, so dass die beiden Restflächen verschmelzen. Erst dann hat man wieder eine Chance. Wenn man die beiden dünnen Lücken unten am rechten und linken Rand aber gleich zu Beginn des Lösungsprozesses verschließt, kommt man beim klassischen Backtracking in vertretbarer Zeit nie wieder dahin zurück. Deshalb löst der PolySolver dieses Geduldspiel nicht.
Welcher zusätzliche Schritt würde hier helfen? Wir könnten aufpassen, dass auftretende Restflächen immer ein Vielfaches von 6 als Größe besitzen und sonst sofort abgebrochen und mit dem Backtracking begonnen wird. Dieser zusätzliche Schritt wird Volumentest genannt (weil er analog auch für dreidimensionale Probleme funktioniert) und ist ist bei einigen Solvern implementiert. Bei Polycube [1] gibt es auf der Kommandozeile den Parameter -v, und -v10 schaltet beispielsweise den Volumentest ein, sobald die Restfläche kleiner als 10 Steine groß ist. Mei mops.exe kann man im Menü Pack ein Häkchen bei Void Check setzen, um den Volumentest einzuschalten. Danach finden beide Programme wie erwartet Lösungen innerhalb Sekunden.
Aufgabe 12: Rechteck 33x7 mit Loch der Größe 7x3 in der Mitte
Hier ist die Situation analog zur Aufgabe 11: Das 33x7-Rechteck wird durch das große leere Rechteck in der Mitte nur durch zwei dünne Verbindungen (diese haben hier die Breite 2) oben und unten zusammengehalten. Wenn diese geschlossen werden und nicht auf die Größe der verbleibenden Restflächen geachtet wird, landet man schnell in einer Sackgasse. Mit dem Volumentest gibt es aber kein Problem.
Bei dieser Aufgabe ist nicht klar, ob der Volumentest hilft. Aber ein einfacher Versuch zeigt: Ohne Volumentest findet Polycube so schnell keine Lösung, mit Volumentest geht es blitzschnell.
Keine Kommentare:
Kommentar veröffentlichen