Algorithmus Problem. Rechtecke effizient auf Spielfeld anordnen.

sirbender

Top Contributor
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
 

Anhänge

  • LayoutAlgorithm.png
    LayoutAlgorithm.png
    5,7 KB · Aufrufe: 100

FArt

Top Contributor
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

Top Contributor
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.
 
S

SlaterB

Gast
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 ;)
 

sirbender

Top Contributor
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

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

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

Top Contributor
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.
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
L Klassen Algorithmus für das folgende Problem entwickeln? Allgemeine Java-Themen 30
M Salesman Problem - Bruteforce Algorithmus Allgemeine Java-Themen 23
B Algorithmus - Project Euler Problem 18 Allgemeine Java-Themen 2
C Algorithmus Problem in Minesweeper Allgemeine Java-Themen 5
V Problem mit A* Pathfinder-Algorithmus Allgemeine Java-Themen 2
P Problem mit A*-Algorithmus Allgemeine Java-Themen 12
G Problem mit Algorithmus Allgemeine Java-Themen 3
T Problem RSA-Algorithmus in Java? Allgemeine Java-Themen 2
schegga_B AES-Algorithmus in javax.crypto Allgemeine Java-Themen 3
M Laufzeit des Prim Algorithmus Allgemeine Java-Themen 3
O Newton Algorithmus Java Allgemeine Java-Themen 1
CptK Backpropagation Algorithmus Allgemeine Java-Themen 6
N Google Authenticator Algorithmus (SHA1) Allgemeine Java-Themen 1
gotzi242 Schatzsuche mithilfe eines O(log n) Algorithmus Allgemeine Java-Themen 2
Zrebna Quicksort-Algorithmus - zufälliges Pivot wählen Allgemeine Java-Themen 6
B Algorithmus Warteschlange Ringpuffer wirklich fehlerfrei Allgemeine Java-Themen 8
M Probleme mit Negamax-Algorithmus Allgemeine Java-Themen 29
F Q - Learning Algorithmus Bug Allgemeine Java-Themen 4
M Minmax Algorithmus Verständnisproblem Allgemeine Java-Themen 2
H Rundreise frage (Algorithmus) Allgemeine Java-Themen 18
F KMP-Algorithmus Allgemeine Java-Themen 9
S Algorithmus welcher True-Werte in einem Array findet und auswertet. Allgemeine Java-Themen 5
U Methoden Algorithmus MergeSort String [ ] array sortieren programmieren Allgemeine Java-Themen 17
P MinMax Algorithmus Allgemeine Java-Themen 0
J Abhängigkeit zwischen Rechenzeit und Speicherbedarf in einen Algorithmus Allgemeine Java-Themen 7
K Djikstra-Algorithmus Allgemeine Java-Themen 1
T Minimax/Alphabeta Algorithmus hängt sich auf (?) Allgemeine Java-Themen 2
M Algorithmus zum Zahlen einteilen Allgemeine Java-Themen 8
O Best Practice Hilfe bei Algorithmus gesucht Allgemeine Java-Themen 10
S Algorithmus um Objekte auf einer Flaeche mit gleichem Abstand anzuordnen..? Allgemeine Java-Themen 20
S Rucksackproblem und genetischer Algorithmus Allgemeine Java-Themen 9
L Abbruch des Algorithmus Allgemeine Java-Themen 8
D Input/Output Ausgleichen chemischer Reaktionsgleichungen mit dem Gauß-Algorithmus Allgemeine Java-Themen 2
Messoras A*-Algorithmus integrieren Allgemeine Java-Themen 3
S Buchscan 3D Dewarp Algorithmus - Ansätze Allgemeine Java-Themen 1
B Verteilungs-/Vergabe-Algorithmus mit abhängigen Score-Werten Allgemeine Java-Themen 3
Androbin "Shunting Yard"-Algorithmus Allgemeine Java-Themen 6
N Algorithmus zum bewerten von mathematischen Funktionen Allgemeine Java-Themen 11
O Algorithmus Optimierung Allgemeine Java-Themen 3
Joew0815 Algorithmus - Zahlenfolge in 4 ähnliche Teile aufteilen Allgemeine Java-Themen 0
O Tag Cloud Algorithmus Idee gesucht Allgemeine Java-Themen 2
A Implementierung eines Algorithmus (Farthest Insertion zur Lösung des TSP) in O(n²) Allgemeine Java-Themen 2
C Eclipse Probleme bei selbst erstelltem Algorithmus Allgemeine Java-Themen 2
H Graph-Algorithmus gesucht Allgemeine Java-Themen 21
N Algorithmus durch Workflow Allgemeine Java-Themen 7
M tree-based diff Algorithmus (Code-Vergleiche) Allgemeine Java-Themen 3
S Uhrzeit Algorithmus sale Allgemeine Java-Themen 11
N A*-Algorithmus Allgemeine Java-Themen 5
A Suche Algorithmus zum Erstellen eines planaren Graphen Allgemeine Java-Themen 5
F Methoden Algorithmus zur Gegnerfindung (Turnier) Allgemeine Java-Themen 9
T Algorithmus Graph Allgemeine Java-Themen 10
J Algorithmus gesucht (Stringtransformation) Allgemeine Java-Themen 4
B Algorithmus Krankenhausbelegung Allgemeine Java-Themen 17
S Algorithmus von Dijkstra Allgemeine Java-Themen 2
alex_fairytail OOP Banknoten Algorithmus Teil 2 Allgemeine Java-Themen 13
2 ArrayList aktualisieren Algorithmus Allgemeine Java-Themen 11
alex_fairytail Methoden Banknoten Algorithmus Allgemeine Java-Themen 10
R Codehinweise: Algorithmus Größenvergleich von n Zahlen Allgemeine Java-Themen 5
SuperSeppel13 WTF?! Algorithmus-Geschwindigkeitstest Allgemeine Java-Themen 2
L Algorithmus für kürzesten Weg mit Wegpunkten Allgemeine Java-Themen 21
S Algorithmus um Labyrinth zu erzeugen Allgemeine Java-Themen 6
S Algorithmus um nächst folgende Primzahl zu berechnen Allgemeine Java-Themen 7
C Algorithmus-Hilfe Allgemeine Java-Themen 20
J Algorithmus Längenkombinationen? Allgemeine Java-Themen 7
M Kombinationen über rekursiven Algorithmus berechnen? Allgemeine Java-Themen 10
L Algorithmus für Poker-Hände Allgemeine Java-Themen 7
chik 2 return werte für Greedy-Algorithmus (gelöst) Allgemeine Java-Themen 3
D Abstruse Probleme mit eigenem replace Algorithmus Allgemeine Java-Themen 11
P RC4 Algorithmus Allgemeine Java-Themen 3
D RSA Verfahren - Erweiterter Euklidischer Algorithmus Allgemeine Java-Themen 4
C IBAN und Bic Validieren (Algorithmus) Allgemeine Java-Themen 10
M Wörter Algorithmus Allgemeine Java-Themen 7
M Algorithmus für automatische Zeilenumbrüche Allgemeine Java-Themen 12
K Postleitzahlen Algorithmus Allgemeine Java-Themen 12
T Hilfe bei einem Algorithmus Allgemeine Java-Themen 2
S Stemming-Algorithmus gesucht (z.B. Porter) Allgemeine Java-Themen 2
RoliMG präfix zu infix algorithmus Allgemeine Java-Themen 6
Z A*-Algorithmus - Probleme mit offener/geschlossener Liste Allgemeine Java-Themen 7
S Javaimplementierung des MD5 Algorithmus Allgemeine Java-Themen 2
E Container-Pack-Algorithmus Allgemeine Java-Themen 4
G k nearest neighbor algorithmus Allgemeine Java-Themen 7
C HASH Algorithmus 2 Strings ergeben das Selbe. Allgemeine Java-Themen 2
P Page Rank Algorithmus implementieren Allgemeine Java-Themen 7
minzel Hash-Algorithmus Allgemeine Java-Themen 9
Y komprimierung mittels Huffman-Algorithmus, bit-shifting. Allgemeine Java-Themen 2
K Algorithmus Allgemeine Java-Themen 10
C Algorithmus für Array Allgemeine Java-Themen 9
I Verschlüsselung mit Pwd. - User soll Algorithmus wählen Allgemeine Java-Themen 4
J fällt euch ein Algorithmus ein? Allgemeine Java-Themen 4
S Algorithmus für Sudoku Allgemeine Java-Themen 17
N Euklidischer Algorithmus in Java und keine Terminierung. Allgemeine Java-Themen 7
F Algorithmus für Sortierung gesucht Allgemeine Java-Themen 15
T Algorithmus verbessern Allgemeine Java-Themen 10
U Suche Algorithmus zur bestimmung des längsten Wegs Allgemeine Java-Themen 3
U Ford-Fulkerson Algorithmus gesucht Allgemeine Java-Themen 1
U Dijkstra Algorithmus gesucht Allgemeine Java-Themen 4
D Algorithmus für die Erkennung fehlerhafter Eingaben Allgemeine Java-Themen 4
I hash-algorithmus Allgemeine Java-Themen 9
krgewb Problem mit Umlauten und Eszett bei InputStream Allgemeine Java-Themen 3
Max246Sch Backtracking Problem Box Filler Allgemeine Java-Themen 6

Ähnliche Java Themen

Neue Themen


Oben