Algotithmus zur optimalen Platzausnutzung?

Hallö,
ich habe ein kreatives Problem das mich noch in den Wahnsinn treiben wird...ich weiß es genau -.-
Also man nehme einen Raum mit vordefinierte Größe wasweißich 20 Felder breit mal 50 Felder hoch. So jetzt habe ich mehrere Objekte mit unterschiedlicher Größe die ich auf möglichst wenige solcher Räume verteilen möchte. Also zb
Objektart 1: 20,10
Objektart 2: 10,20
Objektart 3: 10,25
Habe dann fleissig Objekte und möchte diese wie gesagt auf möglichst wenige Räume aufteilen um so den Platz möglichst optimal auszunutzen und wenige Räume kaufen/mieten zu müssen....
Jemand einen Ansatz? Gibts da was?

Meines Wissens nach ein NP-Problem:
de.wikipedia.org/wiki/Karps_21_NP-vollst%C3%A4ndige_Probleme
de.wikipedia.org/wiki/Mengenpackungsproblem
de.wikipedia.org/wiki/Rucksackproblem
Aber ohne Gewähr...

Du meinst Fläche oder? Ein Raum hätte drei Dimensionen. Was spricht gegen eine einfache Tiefensuche? Bei der größe des Problems, sollte das doch hinhauen.

Ja ich meine Flächen. Mit Raum meinte ich keine dreidimensionalen Raum, der Ausdruck war wohl schlecht gewählt.
Was ist eine Tiefensuche?

Im Prinzip läuft es darauf hinaus, alle Möglichkeiten systematisch auszuprobieren und dabei einen Suchbaum auf zu bauen. Wenn man entlang der Kanten und Knoten des Baums möglich zuerst die äusseren Blätter besucht, kommt läuft es auf eine Tiefensuche hinaus, wenn man den Lösungsbaum gleichmäßig durchsucht, ist es eine Breitensuche (Djkstra). Wenn Du es hinbekommst, eine Mindesflächenverbrauch für Deine Objekte abschätzen zu können, dann könntest Du auch einen A* benutzen, das ist eine spezielle Breitensuche, die schneller zu einem Ergebnis findet, wenn die Abschätzung brauchbar ist.
Ein bischen Teorie zu Grafen findest Du hier boost.org/doc/libs/1_35_0/libs/graph/doc/graph_theory_review.html.

Ja ne das ist die Brachiallösung.. klar alle Möglichkeiten durchprobieren und dann schaun welche am wenigsten Kosten hat geht natürlich. Ist aber irgendwie nicht so schön
Es muss doch irgendeine schöne Lösung geben XD

Naja, Du kannst bei der Tiefensuche natürlich immer da abbrechen, wo Du dein derzeitiges Minimum überschreitest. Und A* wäre eine Lösung, die halt auch noch etwas besser läuft.
Ansonsten verwendet man für solche Probleme wohl mit genetischen Algorithmen. So etwas habe ich aber noch nie gemacht.

> genetischen Algorithmen
Genetischer Algorithmus ist für diese Art von Problem nahezu unbrauchbar.

Original von TheUndeadable
Genetischer Algorithmus ist für diese Art von Problem nahezu unbrauchbar.

Doch! ;-)

Habe mir ein paar Gedanken gemacht.
Mit einer rein örtlichen Abbildungsvorschrift wirst du keinen großen Erfolg mit einem genetischen Algorithmus haben, führst du allerdings eine Abbildung über vom Genotypen auf dem Phänotypen auf, der die Steine tetrisartig einfallen lässt, so könnte ein genetischer Algorithmus (genauer gesagt eher EA) durch aus Erfolg haben.
Ziel muss es sein eine Abbildung mit hoher Kausalität und Stetigkeit zu finden.
Es könnte einen Tick schneller als eine Tiefensuche sein, es besteht aber die Gefahr, dass man bei einer schlechten Parameterwahl in einem lokalen Minimum hängen bleibt.

Ich geh mal doof da ran...
* Ermittel die freien Felder und hau sie in ein Array
* Ermittel die Menge der freien Felder
* Erzeuge eine Zufallszahl zwischen 0 und der Obergrenze des Arrays
* Entferne das Feld aus dem Array und verwende es
Einfach, leicht umzusetzen, relativ schnell.
Lustig wird es, wenn du noch Bedingungen stellst wie
* Starte nicht im Umkreis von N Felder zu Spielern mit X Punkten
* Starte nur in bestimmten Gebieten
So... einfach und doof Jetzt ihr
Edith...
Rucksackproblem scheint korrekt zu sein. Ei dann war ich zu doof

* Ermittel die freien Felder und hau sie in ein Array
* Ermittel die Menge der freien Felder
* Erzeuge eine Zufallszahl zwischen 0 und der Obergrenze des Arrays
* Entferne das Feld aus dem Array und verwende es
Einfach, leicht umzusetzen, relativ schnell.

Einfach leicht und vollkommen am Thema vorbei XD sorry aber ich erkenne den Zusammenhang nicht?
> Ermittel die freien Felder?
Was denn für freie Felder? Meinst du die benötigten Räume in denen wir Platz optimal nutzen wollen? Ja witzig das ist ja die eigentlich Hauptaufgabe die eben das Problem darstellt
> Ermittel die Menge der freien Felder?
ja und jetzt gleich nochmal Oo bidde?
> Erzeuge eine Zufallszahl zwischen 0 und der Obergrenze des Arrays?
Du denkst zu sehr in Programmiersprachen, einfach gesagt wilst du ein Objekt aus der Liste der Objekte die platziert werden sollen auswählen, ok.
> Entferne das Feld aus dem Array und verwende es
Ja "verwende es" drückt es schon aus...nur wo und wie ist die Frage XD einfach zufällig alle Elemente in die Räume pumpen resultiert garantiert in absoluter Ineffizient weil überall Lücken sind die entstanden sind weil das nächste Element zu groß für die Lücke war und somit ein neuer Raum dazugekommen ist.
Der Witz der Aufgabe besteht ja eben darin möglichst wenig Raum zu beanspruchen
@Rucksackproblem
finde ich wenig passend da es ja nicht darum geht einen Raum möglichst effektiv zu packen sondern möglichst wenig Räume zu beanspruchen um alle Pakete zu verstauen.
Genetische Algorithmen muss ich mich erstmal reinlesen bevor ich was brauchbares sagen kann..

Original von Macavity
Der Witz der Aufgabe besteht ja eben darin möglichst wenig Raum zu beanspruchen

Dir kann hier keiner richtig konkrete Hilfe geben, bei den paar Halbsätzen, mit denen Du Dein Problem beschrieben hast.

Mit brute force ist das Problem nicht realistisch lösbar.
Allerdings ist die grundsätzliche Fragestellung (2D-Objekte plazieren) im Bereich der "normalen" PC-Games häufig anzutreffen.
Dabei geht es meist darum, Texturschnipsel möglichst effizient auf vorgegebene Kachelgrössen zu verteilen.
Stichworte für Google wären "Texture Packing" und u.U. auch "Texture Atlas" (TA ist zwar eigentlich was anderes, hat das Packing aber als Teilproblem zu lösen).

Dir kann hier keiner richtig konkrete Hilfe geben, bei den paar Halbsätzen, mit denen Du Dein Problem beschrieben hast.

Oo was hab ich dir denn getan? Mit Ausnahme deines letzten Beitrags fand ich deine Beitrage zusammen mit denen von TheUndeadable sehr hilfreich. Daher gehe ich davon aus das mein Beitrag durchaus verständlich war.
Gegenüber MrMarco war mein Post sicher nicht sehr nett, aber sein Beitrag war ist auch ein absolutes Rätsel -.-
Um es nochmal hoffentlich klarer zu formulieren, ich denke ich habe ein gutes Beispiel gefunden: Anzeigen.
Ich habe 5000 Anzeigen in meiner Datenbank, die haben die abwechslungsreichsten Maße sind jedoch alle rechteckig. Also mal 10x10 cm mal 20x35cm etc etc.. Die Frage ist wieviel Blatt Din A4 brauche ich um all diese Anzeigen drucken zu können. Nachdem ich auch noch auf die Bäume Acht geben will bin ich daran interessiert möglichst wenig Blätter zu verbrauchen, bzw möglichst wenig offene Leerstellen in der Endkomposition zu haben.
Eine Möglichkeit ist die Masse der Anzeigen nach Größe zu sortieren und dann eins nach dem anderen zu nehmen, schauen wo es rein passt und auf die Brachialmethode einfach jede Kombination auszuprobieren. Dabei kann man natürlich halbwegs mitdenken, also zb "Ok ich hab schon eine Lösung mit insamt 400 Blättern, bei dem aktuellen Lösungsweg bin ich bei 380 Stück Papier und es sind noch über 1000 Anzeigen übrig => Zweig abbrechen und nächsten Zweig nehmen."
Texture Packing schau ich mir mal an.

Kommt es dir dabei darauf auch an, dass du die Rechtecke auf mehrere Arten legen kannst; oder könnte man das Problem auch mit einfachen Zahlen "simulieren"?
Soll heißen würde folgendes deiner Aufgabenstellung entsprechen:
Man hat mehrer Zahlen von 1-10 und mehrere Boxen, in denen zb. bis zur Summe 30 alles reinpasst. Wieviel Boxen brauche ich und wie ist die Aufteilung der Zahlen?
Oder echt wie das Beispiel mit dem DIN A4 (da gehts ja auch nicht drum den Fläscheninhalt annährend komplett auszunutzen und evt die Anzeigen dafür zu teilen)?
EDIT: Wäre ein Kreuzworträtsel-Generator nicht eigentlich genau dass was du brauchst? Also in angepasster Version (Die haben ja immer Rechtecke mit 1 mal X und du X mal Y). Ich würde mir an deiner Stelle einfach mal z.B. bei Sourceforge nen paar Sachen ankucken (hab jetzt nicht gekuckt obs da was gibt; aber so als Idee)

Original von Macavity
Oo was hab ich dir denn getan?

Gar nichts, ich habe das aber auch nirgends geschrieben.
Bei Deinem Problem ist ein sortieren nach Größen und dann platzieren der Größten Elemente wahrscheinlich eine gute Idee. Wenn bereits mehr als ein Rechteck plaziert ist, wird es sich nicht al zu viele, sinnvolle Möglichkeiten geben, ein nächstes Rechteck zuplatzieren. Wenn Du um alle bereits plazierten Rechtecke ein Rechteck spannst und diese Fläche zuzüglich der Fläche, des größten, verbliebenen Rechtecks mal der Anzahl der verblienden Rechtecke nimmst, hast Du vielleicht sogar eine ganz gute Heuristik für einen A*.
Ich würde eine große, imaginäre rechtwinkelige Begrenzung nehmen (z.B. den ersten Quadranten eines karthesischen Koordinaten Systems). Dort gibt es für das erste Element genau eine Ecke, wo man das größte Rechteck auf zwei unterschiedlich Weisen plazieren kann. Durch das Plazieren dieses ersten Rechtecks, entstehen zwei neue Ecken, in die man die nächsten Rechtecke plazieren kann. Ich könnte mir z.B. vorstellen, dass man eine Liste von freien Ecken führt, in die man beim Plazieren eines Rechteckes neue Einträge macht und die belegte Ecke entfernt.

Wie? Was? Ich bin angeflamt worden? Hu?
Ne, mal ehrlich... ich war absolut panne an dem Abend und mehr als nur neben dem Thema.
Und um mich zu verärgern gehört mehr dazu

Das ist, wie schon geschrieben, eine Variante des Rucksackproblems, und das ist nunmal NP-schwer. Wenn man annimmt, dass alle deine Blätter gleich groß sind, müsste eigentlich ein zweistufiger Greedy-DP-Ansatz zum Erfolg führen.
Dabei nimmst du einfach das erste Blatt her, und machst es mitttels DP so voll wie möglich (Algorithmen dazu findest du z.B. in der Wikipedia oder in jeder anderen vernünftigem Algorithmenbuch deines Vertrauens). Dann das nächste Blatt und so weiter, bis du alles platziert hast. Ich hab mir vorhin kurz überlegt, warum das zu einem optimalen Ergebnis führen sollte (und das bei guter Laufzeit), aber eben so zwischen Tür und Angel. YMMV.
P.S: Sortieren nach Größen halte ich nicht für schlau. Wird aber auch zum Erfolg führen, vielleicht nicht zum Optimum. Wenn der Suchraum nicht allzu groß ist, ists eh wurscht und ich würde einfach stupide alles durchprobieren, zumal wenn du eh nur einmal suchen willst.

Man hat mehrere Zahlen von 1-10 und mehrere Boxen, in denen zb. bis zur Summe 30 alles reinpasst. Wieviel Boxen brauche ich und wie ist die Aufteilung der Zahlen?

Hm das mit den Zahlen ist mir unklar wie du das meinst oO hört sich wieder so nach Rucksack an also Raum ist 20 mal 40 (bei nem dehnbaren Rucksack also 800 FE) und da dann alles reinpumpen so viel wie möglich ist?
Das geht in meiner Problematik nicht weil die Größen der Objekte fix sind und die Objekte nicht dreh- oder formbar sind. Desweiteren sind auch meine Behälter von statischer Struktur.

Wenn der Suchraum nicht allzu groß ist, ists eh wurscht und ich würde einfach stupide alles durchprobieren, zumal wenn du eh nur einmal suchen willst.

Naja leider ist es durchaus denkbar das der Suchraum ordentlich groß wird, und ich wenn ich nur einemal suchen würde würde sich der Aufwand (auf den es scheinbar hinausläuft) kaum lohnen. Also ja das ganze wird mehr als einmal angewandt werden... leider -.-
DP steht für was genau?

DP steht für dynamische Programmierung. Ist einer der üblichen Ansätze, um ein Rucksackproblem zu lösen. Sollte hier halt in Verbindung mit nem Greedy-Ansatz zum Erfolg führen.

Wenn das Ergebnis hinterher vor menschliche Augen kommt, dürften die Regeln aber sogar noch komplexer werden. Etwa sollen nicht alle Hundefutter-Anzeigen auf die selbe Seite oder immer oben links das gleiche (größte) Objekt platziert sein, weil der Algorithmus so optimiert.
Bei Texturpages dürfte dabei bereits ähnliches dabei sein, denn auch da braucht man ja die Texturschnipsel einzelner Objekte auf möglichst wenig Pages.
Was ich sagen will ist: Überleg, ob es konzeptionell vielleicht noch eine andere Lösung gibt, die ohne aufwändig optimierende Routinen akzeptable Ergebnisse liefert, die spielerisch vielleicht sogar sinnvoller sind.
Um dabei helfen zu können, ist die Problembeschreibung tatsächlich etwas knapp..

Allerdings ;-)
Gegen "das größte oben links" kann man natürlich die berechnete Verteilung bei jeder soundsovielten Seite spiegeln oder doppelt spiegeln (horizontal und vertikal). BEi rechteckigen Seiten sollte das kein Problem sein.
Wenn man noch weitere Bedingungen hat, wie zum Beispiel "nicht alle Hundefutter auf eine Seite" kann man natürlich Ähnlichkeitswichtungen vornehmen und dann das resultierende System lösen. Stichwort Simplexalgorithmus, der ist dann aber schon echt exponentiell statt wenigstens pseudopolynomial wie ein mittels dynamischer Programmierung gelöstes Rucksackproblem.
Wenns dann aber ästhetische Gesichtspunkte hat, würde ich das, wenn machbar, einfahc von Hand machen. Bei 10.000 Seiten einfach in ein Billiglohnland outsourcen