square: Ein Optimierungsproblem

und eine Aufforderung zum Mitmachen

gegeben:
ein Quadrat der Kantenlänge n und n-1 Quadrate der Kantenlängen 1,2,...,n-1

gesucht:
eine Anordnung von kleinen Quadraten in dem Quadrat der Kantelänge n, so dass eine möglichst große Fläche überdeckt wird. Jedes kleine Quadrat darf nur einmal verwendet werden.

Für die Kantenlängen 2,3,4,...,14 ist die Lösung 1,n-1 die optimale, aber schon für n=15 gibt es eine bessere Lösung mit einer überdeckten Fläche von 204 von 225. Die einfache Lösung liefert 14*14 + 1*1 = 197. Bei größeren Kantenlängen, z.B. 50, wird die Lösung noch wesentlich komplexer.

Diese Aufgabe ist ein spezielles 2-dimensionales Rucksackproblem (engl.: knapsack). Es ist NP-vollständig, d.h. für wachsende Größe des Quadrates steigt die Rechenzeit für eine optimale Lösung mindestens exponentiell.

Dieses Problem eignet sich deshalb gut zum Austesten unterschiedlicher Suchstrategien: z.B. vollständige Suche mit möglichst frühem Abschneiden der Suchbäume, heuristische Verfahren, constraint-basierte Verfahren (mit clp(FD) oder eclipe) oder Genetische Algorithmen.

Beispiel

In dem Archiv square.tar.gz ist ein Beispiel für die Lösung dieses Optimierungsproblems enthalten. Es arbeitet als einfaches client/server Programm.

Der client (square.tcl) implementiert die graphische Benutzungsschnittstelle, er ist vollständig mit Tcl/Tk implementiert, er ist in der Lage, verschiedene Suchprogramme (server) aufzurufen.

Zwei Suchprogramme sind bisher implementiert: square-0 ist ein Minimalprogramm, es liefert immer die triviale Lösung (für n immer n-1,1). Die Aufrufkonventionen können hieran aber einfach abgelesen werden, ein Testaufruf: square-0 15

square-1 ist ein besseres Suchprogramm: es führt eine vollständige Suche durch. Es plaziert die Quadrate immer in Ecken, nie in eine freie Fläche, und versucht, den Suchbaum möglichst früh zu kappen. Es arbeitet bis zu einer Kantenlänge n=50 in annehmbarer Zeit, darüber hinaus wird es sehr schnell unbrauchbar. Dieses Programm ist in Prolog erstellt (--> SWI Prolog). Ein Testaufruf square-1 15 zeigt, daß für n=15 eine bessere, als die triviale Lösung existiert.

Hier sind viele Verbesserungsmöglichkeiten denkbar, wer noch ein C oder OOP Programm zu erstellen hat, kann hier interessante Optimierungsstrategien ausprobieren. Wenn die (sehr einfachen) Aufrufkonventionen eingehalten werden, kann das Optimierungsprogramm ohne Änderung mit dem GUI-Programm square.tcl zusammenarbeiten.

Aufrufkonventionen

  • Der Programmname des Suchprogramms muss auf das Muster square-[0-9A-Za-z]+ passen, d.h. der Programmname muss mit square- beginnen und aus beliebigen Buchstaben und Ziffern gebildet werden. Die Namen square-0 und square-1 sind schon belegt.

  • Das Programm wird mit

    square-<name> <größe>

    aufgerufen, also mit einem Parameter, dieser muss eine ganze Zahl größer als 1 sein.

  • Das Programm enthält keine weiteren Eingaben.

  • Das Programm schreibt auf die Standardausgabe (für C: stdout) die folgenden Informationen, jede Information besteht aus genau einer Zeile, nach Ausgabe einer Zeile wird immer der Ausgabepuffer geleert (für C: fflush(stdout)).

    Jede Zeile bildet genau ein Tcl-Kommando, daß von dem GUI-Programm ausgeführt wird:

    1. Version {<Programmname und Version>}

      der Name und die Version des Suchprogramms in geschwungenen Klammern

    2. pro gefundener Lösung eine Zeile in dem Format:

      Solution <covered> {<size+position> ... }

      mit

      <size+position> = {<size> <x> <y>}

      Mit diesem Kommando kann also immer die augenblicklich beste Lösung angezeigt werden. <covered> gibt die überdeckte Fläche dieser Lösung an, es folgt in geschwungenen Klammern eine Liste von Quadraten, diese einzelnen Einträge bestehen aus drei Werten: der Größe des Quadrates, der X- und Y- Koordinate der Ecke, die sich am dichtesten am Punkt (0,0) befindet. Schließende und öffnende geschwungene Klammern müssen durch einen Zwischenraum getrennt sein.

      Das zu überdeckende Quadrate wird durch die Punktemenge

      {(0,0),(0,1),...,(0,n-1)
      ,(1,0),(1,1),...,(1,n-1)
      ,...,...,...
      ,(n-1,0),(n-1,1),...,(n-1,n-1)
      }

      dargestellt.

    3. als letzte Zeile

      BestSolution <size> <covered>

      dieses Kommando wird am Ende der Suche ausgegeben, <size> ist die Kantenlänge des Quadrates, also der Programmparameter, <covered> gibt die überdeckte Fläche an.

ein Beispiel-Programmlauf

für n=15 mit square-1 15

Version {Square Puzzle Prolog Search Program $Revision: 1.5 $ $Date: 2008-07-05 08:04:19 $} SearchSolutionsSquare 15 Solution 197 {{14 0 0} {1 14 0} } Solution 204 {{8 0 0} {7 8 0} {6 0 8} {5 6 8} {4 11 7} {3 11 11} {2 8 13} {1 8 7} } BestSolution 15 204

Bestenliste (Stand 11.7.96)

size: 3 covered: 5 from 9 in % 55.56 size: 4 covered: 10 from 16 in % 62.50 size: 5 covered: 17 from 25 in % 68.00 size: 6 covered: 26 from 36 in % 72.22 size: 7 covered: 37 from 49 in % 75.51 size: 8 covered: 50 from 64 in % 78.12 size: 9 covered: 65 from 81 in % 80.25 size: 10 covered: 82 from 100 in % 82.00 size: 11 covered: 101 from 121 in % 83.47 size: 12 covered: 122 from 144 in % 84.72 size: 13 covered: 145 from 169 in % 85.80 size: 14 covered: 170 from 196 in % 86.73 size: 15 covered: 204 from 225 in % 90.67 size: 16 covered: 226 from 256 in % 88.28 size: 17 covered: 260 from 289 in % 89.97 size: 18 covered: 295 from 324 in % 91.05 size: 19 covered: 336 from 361 in % 93.07 size: 20 covered: 362 from 400 in % 90.50 size: 21 covered: 413 from 441 in % 93.65 size: 22 covered: 454 from 484 in % 93.80 size: 23 covered: 501 from 529 in % 94.71 size: 24 covered: 540 from 576 in % 93.75 size: 25 covered: 592 from 625 in % 94.72 size: 26 covered: 640 from 676 in % 94.67 size: 27 covered: 698 from 729 in % 95.75 size: 28 covered: 745 from 784 in % 95.03 size: 29 covered: 805 from 841 in % 95.72 size: 30 covered: 861 from 900 in % 95.67 size: 31 covered: 921 from 961 in % 95.84 size: 32 covered: 983 from 1024 in % 96.00 size: 33 covered: 1046 from 1089 in % 96.05 size: 34 covered: 1107 from 1156 in % 95.76 size: 35 covered: 1181 from 1225 in % 96.41 size: 36 covered: 1243 from 1296 in % 95.91 size: 37 covered: 1322 from 1369 in % 96.57 size: 38 covered: 1394 from 1444 in % 96.54 size: 39 covered: 1476 from 1521 in % 97.04 size: 40 covered: 1551 from 1600 in % 96.94 size: 41 covered: 1634 from 1681 in % 97.20 size: 42 covered: 1714 from 1764 in % 97.17 size: 43 covered: 1801 from 1849 in % 97.40 size: 44 covered: 1882 from 1936 in % 97.21 size: 45 covered: 1977 from 2025 in % 97.63 size: 46 covered: 2065 from 2116 in % 97.59 size: 47 covered: 2153 from 2209 in % 97.46 size: 48 covered: 2240 from 2304 in % 97.22 size: 49 covered: 2350 from 2401 in % 97.88 size: 50 covered: 2462 from 2500 in % 98.48 size: 51 covered: 2551 from 2601 in % 98.08 size: 52 covered: 2648 from 2704 in % 97.93 size: 53 covered: 2747 from 2809 in % 97.79 size: 54 covered: 2862 from 2916 in % 98.15 size: 55 covered: 2981 from 3025 in % 98.55

Wenn eine interessante Lösung gefunden wurde, bitte bei mir melden.

Viel Spaß beim Ausprobieren