Block Layout Algorithmus

Question

Ich bin auf der Suche nach Hilfe bei der Verbesserung eines Algorithmus für die Platzierung von Blöcken von ungeraden Formen. Meine Problemdomäne ist seltsam, aber die beste Analogie für meine Blöcke sind Tetris-Teile, außer dass sie mehr als vier Teile haben können. Die Blöcke bestehen immer noch aus nur rechten Winkeln, aber sie können lang und verwinkelt sein, sie können verzweigen usw.

Ich versuche mehrere große beliebig geformte Blöcke auf kleinstem Raum anzuordnen (ich weiß, eine Bin-Packung Problem), aber meine aktuelle Lösung sieht hässlich aus. Ich platziere im Grunde einen, dann brute den Rest, indem ich versuche, sie am Ursprung meines Rasters zu platzieren und sie dann langsam in verschiedene Richtungen zu schieben, bis sie nicht mehr kollidieren. Es ist nicht langsam, aber es macht keinen Versuch, Stücke gut zu passen, so dass sie nicht den gesamten Raum verschwenden.

Das einzige, was ich mir vorstellen kann, ist, die Blöcke nach Größe zu sortieren, die größte zuerst zu platzieren und dann die kleinste am Ende in die verbleibenden Löcher zu stecken. Aber es gibt sicherlich Möglichkeiten, die nach hinten losgehen können.

Gibt es irgendwelche Heuristiken oder Näherungsalgorithmen, die mir hier helfen können?

Die Ergebnisse aussehen würde, etwa wie folgt:

Auch vielleicht meine Gravatar verschenkt, dass dieser Mega Man verwandt ist ...

Answer 1

Diese (polyomino Form-Verpackung) im Allgemeinen scheint ein nichttriviales mathematisches Problem zu sein, und ich werde Sie auf das Fachwissen einiger anderer verweisen, die daran gearbeitet haben. Dieser Typ hat eine Reihe von Polyomino-Beispielen auf seiner Website, wo andere Lösungen einreichen können. Er hat auch Solver-Software in Java:

http://gp.home.xs4all.nl/Site/Polyomino_Solver.html.

http://gp.home.xs4all.nl/PolyominoSolver/downloadsolver.htm

Es gibt auch einige Algorithmen für diese geschrieben von Stephen Montgomery-Smith, die umfassender zu sein scheinen als die oben (es gelöst einige Probleme, die nicht auflösbar damit waren) schließlich machte es in ein xscreensaver (löst in Echtzeit und cool zum Ansehen!). Der folgende Screenshot vom Bildschirmschoner zeigt nur Formen bis zu Pentominos, aber er funktioniert bei allgemeinen Formen mit allgemeinen Containern.

http://www.math.missouri.edu/~stephen/software/

Ich bin nicht sicher, ob entweder diese Software die beste Anpassung von polyominoes annähert für Löcher zu ermöglichen. Aber es ist auf jeden Fall "entscheidbar" in dem Sinne, dass Sie sicher zusätzliche 1x1 Polyominoes in Ihre Lösung einfügen können und sehen, ob es ein passendes Ergebnis finden kann, dann entfernen Sie die 1x1 Stücke, um das Ergebnis zu erhalten.

Für Ihre Anwendung kann es effizienter sein, nach hinten zu arbeiten. Alle diese Algorithmen weisen eine Komplexität in der Anzahl von Einheitszellen in jedem Block auf. Ein guter Weg, um Ihre Blöcke auszulegen, wäre, sie als "Unterteilungen" in größeren Zellen zu betrachten, so dass ein 3x3-Quadrat in Ihrem Block einem 1x1-Quadrat in einer skalierten Version entspricht. Packen Sie dann die Blöcke mit leerem Platz, so dass sie alle aus den größeren Blöcken bestehen, führen Sie den Algorithmus aus und entfernen Sie den zusätzlichen Platz. Dies wird nicht nur viel schneller ausgeführt, sondern erzeugt auch den Abstand zwischen den Blöcken, die Sie benötigen.