Sortierprogramm für Profis
Übersicht
BlitzBasic Allgemein
|
Egon DragonBetreff: Sortierprogramm für Profis |
 Do, Feb 05, 2009 17:52Antworten mit Zitat 
|
|---|---|---|
|
Hi!
Ich hab da ein Problem... Ich hab einen kleinen LKW 400cm x 300cm x 200cm Ich habe Möbelstücke 5 Wandschränke 80cm x 50cm x 50cm 2 Kleiderschränke 180cm x 80cm x 200cm 1 Schuhschrank 120cm x 80cm x 100cm usw... Die Objekte und Maße hab ich jetzt nur als Beispiel genommen, ich bräuchte mal eine Idee wie man ein Sortierprogramm schreiben könnte, welches die Möbelstücke am geschicktesten in den LKW packt. Also dass man da halt um die 30 Quader hat, die geschickt in einen Raum gepackt werden müssen Ich wäre sehr dankbar wenn ihr mir helfen könntet 
Danke! |
||
|
Firstdeathmaker |
Do, Feb 05, 2009 18:33 Antworten mit Zitat
|
|---|---|---|
|
Das ist ein typisches Rucksackproblem, Klasse: NP, d.h. du wirst mehr als linearen Aufwand haben wenn du das Ding lösen möchtest. Der einfachste aber auch längste Ansatz wäre, alle Kombinationen durchzuprobieren.
Wikipedia: Rucksackproblem Das Problem ist ja eigentlich folgendes: Normalerweise würde man die größten zuerst nehmen, und dann immer weiter kleinere hinzufügen. Leider kommt dadurch aber nicht die gewünschte maximale Lösung zustande, da z.B.: Platz = 10 Teilgrößen = 1x8, 3x9 Dabei nur 8/10 ausnutzen würde. Man muss also wohl oder übel alles durchprobieren. |
||
|
www.illusion-games.de
Space War 3 | Space Race | Galaxy on Fire | Razoon Gewinner des BCC #57 User posted image |
||
|
|
Egon Dragon |
Do, Feb 05, 2009 19:55 Antworten mit Zitat
|
|---|---|---|
|
Danke für die schnelle Antwort!
Das geht zwar aber wenn man bei 20 Objekten jede Möglichkeit ausprobieren will dann sind das 20^20 Möglichkeiten! Das ist eine Zahl mit 26 Stellen! Vor dem Komma 
Die Rechenzeiten werden glaub ich zu lang werden... Gibts da nicht ein Algorythmus oder so? Es reicht auch erstmal 2 Dimensional... Also man hat Papier-Rechtecke in verschiedenen Größen und soll die auf möglichst wenige A4 Blätter ordnen... Hat sowas schonmal jemand gemacht? (Ich meine sowas ähnliches programmiert. Nicht Papier ausgeschnitten und sinnlos auf Zettel gelegt  )
|
||
|
BladeRunnerModerator |
Fr, Feb 06, 2009 0:15 Antworten mit Zitat
|
|---|---|---|
| Wenn du dir den geposteten Link richtig anschauen würdest hättest du einen sehr genau erläuterten Algo gefunden. | ||
|
Zu Diensten, Bürger.
Intel T2300, 2.5GB DDR 533, Mobility Radeon X1600 Win XP Home SP3 Intel T8400, 4GB DDR3, Nvidia GF9700M GTS Win 7/64 B3D BMax MaxGUI Stolzer Gewinner des BAC#48, #52 & #92 |
||
|
D2006Administrator |
Fr, Feb 06, 2009 9:06 Antworten mit Zitat
|
|---|---|---|
|
Hm?
Das Rucksackproblem ist doch ein ganz anderes. Da geht es um Gewichte und die Frage, welche Objekte wir überhaupt nehmen. Hier allerdings gibt es eine feste Anzahl an Objekten mit bestimmten Maßen und ein Algorithmus soll die Objekte optimal einsortieren. Ist was ganz anderes, würde ich mal sagen. |
||
|
Intel Core i5 2500 | 16 GB DDR3 RAM dualchannel | ATI Radeon HD6870 (1024 MB RAM) | Windows 7 Home Premium
Intel Core 2 Duo 2.4 GHz | 2 GB DDR3 RAM dualchannel | Nvidia GeForce 9400M (256 MB shared RAM) | Mac OS X Snow Leopard Intel Pentium Dual-Core 2.4 GHz | 3 GB DDR2 RAM dualchannel | ATI Radeon HD3850 (1024 MB RAM) | Windows 7 Home Premium Chaos Interactive :: GoBang :: BB-Poker :: ChaosBreaker :: Hexagon :: ChaosRacer 2 |
||
|
|
BladeRunnerModerator |
Fr, Feb 06, 2009 9:18 Antworten mit Zitat
|
|---|---|---|
| Jain, denn neimand garantiert dir dass die Pakete alle in den LKW passen. Einzig die Gewichtung der einzelnen Objekte anhand ihres Wertes fällt hier eventuell weg, kommt ganz drauf an ob es da bevorzugt zu transportierende Möbelstücke gibt (Es macht zB kaum Sinn die Kleiderkisten zu transportieren bevor man nicht den Schrank in der neuen Wohnung hat.) | ||
|
Zu Diensten, Bürger.
Intel T2300, 2.5GB DDR 533, Mobility Radeon X1600 Win XP Home SP3 Intel T8400, 4GB DDR3, Nvidia GF9700M GTS Win 7/64 B3D BMax MaxGUI Stolzer Gewinner des BAC#48, #52 & #92 |
||
|
Smily |
Fr, Feb 06, 2009 12:47 Antworten mit Zitat
|
|---|---|---|
|
Wenn ich das Problem richtig verstanden habe, geht es einfach darum, viele kisten in verschiedenen größen (z.B. 10x20x10cm, 30x20x20cm, 30x30x10cm) möglichst effektiv in einem großen raum (z.b.200x200cm) unterzubringen.
Ich würde an die Problemlösung herangehen, in dem ich das ganze erstmal auf eine primitivere Ebene herabsenke, da nach der lösung suche, und davon die lösung auf der kompexen ebene ableite. Du könntest dir z.B. - einfach mal testhalber - das gleiche problem, allerdings nur in einem zweidimensionalen raum, konstruieren. Das macht es vlt einfacher eine lösung zu finden. Und diese überträgst du dann einfach in den 3D-Raum. |
||
|
Lesestoff:
gegen Softwarepatente | Netzzensur | brain.exe | Unabhängigkeitserklärung des Internets "Wir müssen die Rechte der Andersdenkenden selbst dann beachten, wenn sie Idioten oder schädlich sind. Wir müssen aufpassen. Wachsamkeit ist der Preis der Freiheit --- Keine Zensur!" stummi.org |
||
SyntaxGast |
Sa, Feb 07, 2009 14:26 Antworten mit Zitat |
|
|---|---|---|
Übersicht
BlitzBasic Allgemein
Powered by phpBB © 2001 - 2006, phpBB Group