Hallo
Kann mir jemand zu dem folgendem Helfen oder sagen bei wem ich nachfragen könnte.
Problem:
Ich habe n 3D Objekte(rechteckig) die in m Raum(rechteckig) untergebracht werden sollen.
Die 3D Objekte haben Eigenschaften wie
- Länge
- Breite
- Höhe
- Gewicht in kg
- stapelbar (ja/nein)

Ziel ist es alle n Objekte auf m Räumen so zu verteilen, dass
1. alle Objekte in die Räume hineinpassen
2. Gewicht im Raum gleich verteilt

Später ist noch denkbar, dass x <= n Objekte zusammen in einem Raum untergebracht werden müssen.

Danke für Eure Hilfe

Hallo!

Ich geh nach deiner Beschreibung mal davon aus, dass es immer eine solche Lösung gibt, dass alle Räume "gleich schwer" sind.
Also ich würde es mal so machen, dass ich in nem Array (oder ner Liste oder in was auch immer) alle n Objekte halte und zwar aufsteigend sortiert nach dem Gewicht. Dann solltest du das Gewicht, das in jeden Raum rein muss (nennen wir es r) ausrechnen (Alle Gewichte zusammenzählen und durch m teilen). Dann gehst du in deinem Array hinten los und gehst nach vorne.
Das oberste Objekt packst du gleich mal in einen Raum (sagen wir, dieses Objekt hätte das Gewicht g) und löscht es aus deinem Array. Jetzt gehst du dein Array weiter nach vorne durch, bis du an einem Objekt bist, dessen Gewicht g2 <= r - g. Sollte g2 = r - g sein, packst du dieses Objekt auch in den Raum * (und löscht es aus dem Array) und bist mit dem ersten Raum fertig. Sollte g2 < r - g sein, packst du das Objekt auch in den Raum * (und löscht es aus dem Array), gehst den Array weiter nach vorne durch und füllst den Raum so lange mit Objekten, bis du eben das Gewicht r erreicht hast. Dann machst du diese Schritte genauo mit dem nächsten Raum (also wieder mit dem schwersten Objekt anfangen).

Das wird so aber nur funktionieren, wenn es auch immer eine Lösung gibt, dass die Räume genau gleich schwer sind!



MrSaint


EDIT: * achso, du musst natürlich immer noch aufpassen, dass die Objekte auch in den Raum noch reinpassen!

Möglich, dass dein Problem np-vollständig ist. Klingt irgendwie ähnlich wie das Rucksackproblem. In dem Fall kann man wohl sagen, dass es keinen effizienten Algorithmus gibt, um das Problem zu lösen.

Sehe ich auch so. Das Problem lässt sich auf einen Raum reduzieren. Weiterhin wird es weniger komplex, wenn man die Kisten auf einfache Zahlen reduziert, die in der Kombination eine bestimmte Summe nicht überschreiten sollen. Dann haben wir das 0/1 Rucksackproblem, das NP-Vollständig ist. Wenn man die Kisten zerschnippeln kann, ist es mit BruteForce zu lösen, so nur durch stures Rumprobieren.

PS: Falls du nicht das absolute Optimum finden willst, sondern nur eine "gute Lösung" innert nützlicher Frist, eignen sich eventuell "bioinspirierte Methoden"; z.B. Evolutionäre Algorithmen (Keywords: Bioinspired Computation, Evolutionary Strategies)

Also ich denke der Algorithmus, den ich oben beschrieben habe sollte auf jeden Fall funktionieren... Natürlich hat er was von BruteForce ( ) und er ist auch bestimmt nicht der Schnellste, aber falls es sicher eine Lösung gibt, sollte er diese auch finden.. denke ich zumindest Seht ihr das anders?


MrSaint

EDIT: ich bin in meiner "Theoretischen Informatik" leider noch nicht so weit, dass ich wüsste, was np-Vollständigkeit ist, aber in nem halben Jahr kann ich dann vielleicht da auch mitreden

NP-Vollständigkeit bezeichnet eine Klasse von Optimierungsproblemen. Man hat also eine Menge von Dingern und will irgendwie ein Optimum finden. Du kannst Folgendes machen:
Suche einfach irgend eine Lösung, dafür eignet sich BruteForce mit ein bisserl Backtracking ganz gut. So. Jetzt hast Du also eine Belegung, die hinhaut. Wenn Dir das nicht reicht, dann nimmst Du irgendeine Kiste irgendwo raus und versuchst die, woanders unterzubringen. Wenn es nicht klappt, nimmst du noch eine Kiste irgendwo raus und versuchst die Beiden, wieder irgendwo unterzubringen. So, irgendwann hast Du eine *andere* Lösung gefunden. Vielleicht ist die ja 'besser'? Super, dann nimmst Du die und fängst von Vorne an. So findet dein Verfahren immer mal wieder eine bessere Lösung und Du kannst jederzeit abbrechen, wenn Du zufriende bist.

MrSaint hat folgendes geschrieben:

Hallo! Ich geh nach deiner Beschreibung mal davon aus, dass es immer eine solche Lösung gibt, dass alle Räume "gleich schwer" sind.

Mhh also bei dem Problem gibt es mindestens zwei Randbedingungen
1. Es müssen alle n Objekte in den m Räumen verstaut sein. Das muß aber nicht unbedingt funktionieren. Sprich es kann auch herauskommen, dass bei Raum m-1 die Länge um 5% überschritten ist. Wäre dann nicht die finale Lösung, aber dennoch eine Fastlösung und besser als gar keine Lösung.
2. Das Gewicht soll innerhalb des Raums verteilt sein, es ist egal ob im Raum m-1 das selbe Gewicht wie in Raum m-2 ist. Ich denke das wurde hier Missverstanden.

Ich habe zwar nicht die große Ahnung von solchen Algorithmen, allerdings ist der Ansatz von BruteForce eher ungeeignet, da die Lösung bei ca. 50 Objekten und 5 Räumen (mittelgroße Menge) zu lange dauern würde. Ein Ansatz mit Heuristik würde eher zum Ergebnis führen, aber ...

Aber dennoch Danke für Eure Hilfe

Hallo,

willst Du ein Flugzeug beladen?
Was soll dies

Zitat:

..Heuristik würde eher zum Ergebnis führen, aber ..

bedeuten?

Geht es um Quader, bei der es eine eindeutige Unterseite gibt, sodass man diese nicht durch aufrechtstellen in den Raum hineinzwaengen kann?
Nicht stapelbar bedeutet also , dieser Quader muss als oberster stehen oder vielleicht zusaetzlich: muss auf dem Boden stehen?
Wenn man stapeln moechte, sollten es moeglichst grossflaechige unten, sein oder viele gleicher Hoehe, die man aneinander anordnen kann-> muessen diese >dicht< gestapelt werden um etwas darauf zu stellen, falls ein grosses nicht stapelbares obenauf kommen soll und nur die Eckpunkte unterstuetzt?

Gewicht gleichmaessig verteilt: soll also die Bodenpressung innerhalb des Raumes in etwa gleich gross sein, oder der Schwerpunkt moeglichst tief in der Mitte des Raumes, um ein Kippen zu verhindern?

Gruss Horst

Moderiert von raziel: Doppelposting entfernt.

Horst_H hat folgendes geschrieben:

Hallo, willst Du ein Flugzeug beladen?

Nein, es geht hier eher um Kisten die in einen Container gestaut werden sollen

Zitat:

Was soll dies ..Heuristik würde eher zum Ergebnis führen, aber .. bedeuten?

Ich hatte mit einem alten Arbeitskollegen gesprochen der sich mit Algorithmen auskennt und der hat mir gesagt, dass ein Lösungsansatz mit Heuristik arbeiten könnte da eine Lösung mit BruteForce zu lange dauern würde.

Zitat:

Geht es um Quader, bei der es eine eindeutige Unterseite gibt, sodass man diese nicht durch aufrechtstellen in den Raum hineinzwaengen kann?

Ja siehe oben

Zitat:

Nicht stapelbar bedeutet also , dieser Quader muss als oberster stehen oder vielleicht zusaetzlich: muss auf dem Boden stehen?

Ja

Zitat:

Wenn man stapeln moechte, sollten es moeglichst grossflaechige unten, sein oder viele gleicher Hoehe, die man aneinander anordnen kann-> muessen diese >dicht< gestapelt werden um etwas darauf zu stellen, falls ein grosses nicht stapelbares obenauf kommen soll und nur die Eckpunkte unterstuetzt?

Also wie das gestapelt wird ist eigentlich egal. Natürlich sollte es nicht so aussehen, dass ein kleines unten steht und ein grosses oben drauf also wie ein 'T'. Alles andere ist egal solange alle Objekte in den Raum passen

Zitat:

Gewicht gleichmaessig verteilt: soll also die Bodenpressung innerhalb des Raumes in etwa gleich gross sein, oder der Schwerpunkt moeglichst tief in der Mitte des Raumes, um ein Kippen zu verhindern?

Wenn der Raum an einem Seil hochgehoben werden würde sollte er nicht dramatisch kippen. Genauer - wenn ein Kran den Container anhebt sollte der Container nicht dramatisch kippen. In Hamburg gleichen die Kräne das Ungleichgewicht aus, aber das kann man von dem Zielhafen in China oder Afrika nicht unbedingt erwarten.

Gruss Thomas und Danke für deine Antwort