# Algorithmus Problem. Rechtecke effizient auf Spielfeld anordnen.



## sirbender (6. Apr 2010)

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 (6. Apr 2010)

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 (6. Apr 2010)

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 (6. Apr 2010)

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 (6. Apr 2010)

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


----------



## sirbender (6. Apr 2010)

Marco13 hat gesagt.:


> 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 (6. Apr 2010)

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 (6. Apr 2010)

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.


----------

