Algorithmus Problem. Rechtecke effizient auf Spielfeld anordnen.

[sirbender]

Hi,

ich will Rechtecke verschiedener Groesse auf einer Flaeche anordnen sodass recht wenig 'Zwischenraeume' (in der Grafik schaut der weisse Untergrund durch wo Zwischenraeume entstanden sind) entstehen. Dabei ist muss es nicht die global optimale Loesung sein - falls es sowas ueberhaupt gibt - sondern einfach nur eine recht gute Loesung.

Ich koennte mir zwei Start-Ansaetze vorstellen. Man plaziert ein Rechteck in der Mitte (blau) und ordnet dann irgendwie sinnvoll die anderen Rechtecke iterativ darum an. Das Anordnen ist das Problem.

Ein zweiter Ansatz koennte sein, dass man sich im Klaren wird welche Rechtecke man hat, welche Form und Flaeche diese haben und dann mit einem Algorithmus auf Basis aller Rechtecke das Anordnen durchfuehrt und nicht iterativ wie bei Ansatz1. Auch hier weiss ich nicht so recht wie so ein Algorithmus aussehen koennte.

Ich habe mal ein Beispiel kreirt wie das ungefaehr aussehen koennte: http://www.java-forum.org/attachment.php?attachmentid=1360&stc=1&d=1270542459

Danke,
sb

 

[FArt]

Ein einfacher Algorithmus könnte Backtracking sein. Elemente platzieren, bis es nicht mehr geht (keine Lösung) oder keine Elemente mehr vorhanden sind. Dann die Lösung bewerten (z.B. die größtmögliche, freie, rechteckige Fläche) und die Anordnung merken.
Rekursion: fange in einer Ecke an, mit dem größten Element, danach das nächstgrößere usw. Mit Backtrackings wirst du alle Kombinationen durchlaufen. Nicht vergessen, auch die Orientierung zu wechseln.

 

[sirbender]

Die Flaeche ist nicht begrenzt. Irgendwann gehen die Rechtecke halt aus. Dabei sollte die bedeckte Flaeche

1. recht quadratisch sein (d.h. nicht eine lange Reihe von Rechtecken hintereinander)
2. moeglichst wenig weisse Flaeche entsteht.

Ich haette eigentlich am liebsten einen Algorithmus der einfach immer recht mittelmaessige Ergebnisse liefert und das mit den Rekursionen ersparen.

Was meinst du mit: Nicht vergessen, auch die Orientierung zu wechseln? Die Rechtecke sind eigentlich nicht rotierbar.

 

[SlaterB]

man kann die Rechtecke nicht drehen, aber beliebig durcheinander verschieben?
welche realistische Anwendung steckt denn dahinter oder ist das ein beliebig vorgegebener Parameter des abstrakten Problems?
so wie man alle schrägen Winkel sicher gerne vermeidet 😉

 

[Marco13]

Irgendwas stochastisch angehauchtes wie Simulated Annealing oder Genetische Algorithmen kommt nicht in Frage?

 

[sirbender]

Irgendwas stochastisch angehauchtes wie Simulated Annealing oder Genetische Algorithmen kommt nicht in Frage?

Bei mir kommt alles in Frage solange es schnell geht. Wie gesagt muss das Ergebnis nicht perfekt sein.

Zum Problem: Eigentlich ist es sehr abstrakt aber ich habe mir mal ein relativ sinnvolles Beispiel ausgedacht. Stellt euch z.B. vor ihr habt eine Flaeche. In die Mitte wird ein Moebel-Stueck gestellt und darum weitere Moebel angeordnet. Am besten sollen Sie natuerlich so angeordnet werden, dass moeglichst wenig Platz verschwendet wird.

 

[Marco13]

Klar, so stell' ich die Möbel bei mir im Zimmer auch auf :autsch: 😀

Bei diesen stochastischen Verfahren ist es eben i.a. so, dass man relative schnell relative gute Lösungen bekommt, man sie aber (je nachdem) ggf. belibeig lange laufen lassen kann, und die Lösung immer weiter (aber immer langsamer) verbessert wird. Die Implementierung kann aufwändig sein, kommt stark darauf an wie weit man abstrahiert....

 

[FArt]

Deine Anforderungen in der einen Richtung sind relativ klar: die Gesamtfläche soll möglichst klein sein und möglichst quadratisch... (zweiteres ist ein wenig seltsam, sinnvoller erscheint mir eine Begrenzung in einer oder zwei Dimensionen, aber egal).
Warum willst du dir die Rekursion sparen? Ersetzte sie durch eine Iteration, ist nichts anderes.

Wie sieht es mit den nichtfunktionalen Anforderungen aus? "Möglichst schnell" oder "eine ordentliche, wenn auch nicht optimale Lösung" ist da ein wenig zu schwammig.
Soll der Algorithmus eine Zeit lang laufen und der bis dahin beste Wert verwendet werden (egal wie gut der ist)? Wird eine Grenze für den Verschnitt angegeben, ein Verhältnis, welches nicht überschritten werden darf?

Schau mal bei Wikipedia: Optimierungsprobleme (Mathematik)... da gibt es Algorithmen, die du u.U. adaptieren kannst.