Algorithmus zur Schnittoptimierung
-
-
Das Problem des Handlusngsreisenden trifft die ganze Sache meiner Meinung nach nicht. Dieser Algorithmus wird in der Technik eher verwendet, um die Verfahrwege eines Fräsers zu optimieren oder wenn man z.B. 100 Löcher mit bestimmten Koordinaten in ein Blech bohren will und dabei den geringsten Verfahrweg sucht. Wüsste nicht, wie ich das auf mein Problem anwenden sollte.
Das Rucksackproblem ist so eine Sache, hatte das ja auch schon gelesen aber es trifft es glaub ich nicht ganz, weil das Rucksackproblem berechnet, wie man einen Rucksack begrenzter Tragfähigkeit am günstigsten packt. Mein Problem ist jedoch, dass es nicht über den Rucksack hinausschaut. Angewandt auf mein Problem, hieße das ,das der Rechner die Optimalen Längen in eine Stange packt, so dass wenig Verschnitt übrig bleibt. Dies könnte er bei der nächsten Stange wiederholen bis er keine Längen mehr im Container hat. Aber garantiert mir das die optimale Lösung? Und warum arbeiten die meisten handelsüblichen Programme mit dem Guillotine-Algorithmus (was immer das genau sein mag). Hat jemand davon schon mal was gehört?@Jansen
Weiß nit ob ich im Matheforum besser aufgehoben bin. Thematisch sicherlich, aber ist das auch so gut besucht? Entscheide du das, kannst das sicherlich besser einschätzen, wo ich höhere Chancen auf die Lösung meines Problems hab.Gruß Sebastian
-
Du kannst auch kg wegstreichen und dafür m hinschreiben.
Beim Rucksackproblem ist es das Gewicht und bei dir halt die Länge.
Das ist der einzigste Unterschied.
-
Dieser Thread wurde von Moderator/in Jansen aus dem Forum VCL (C++ Builder) in das Forum Mathematik verschoben.
Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?Dieses Posting wurde automatisch erzeugt.
-
Ist das nicht eher BIN-PACKING? Er muß die abzusägenden Stangen in möglichst wenige lange Stangen (die Bins) verpacken. Das Problem ist NP-vollständig, es lässt sich also vermutlich nicht schnell exakt lösen. Es gibt aber Approximationsalgorithmen, denen Du angeben kannst wie weit du maximal von der optimalen Lösung weg sein magst. Je genauer desto größer die Laufzeit. Vielleicht reicht dir ja eine Lösung, die bis auf 5% optimal ist oder so.
-
http://de.wikipedia.org/wiki/Zuschnittsproblem triffts glaub ich ganz gut...
-
D-U-D-E schrieb:
http://de.wikipedia.org/wiki/Zuschnittsproblem triffts glaub ich ganz gut...
Das ist doch das Bin-Packing.
-
Hallo,
kennt Jemand (gute) Open Source implementierungen von einem der beschriebenen Alghortihmen im Wiki-Artikel? Wo könnte ich sowas überhaupt finden abseits von Google?
-
Such mal nach Nemhauser-Ullmann. Oder schreibs dir in fünf Minuten selbst.
-
Im prinzip lässt sich das doch auch als ganzzahlig lineares Optimierungsproblem (linear integer programming) formulieren. Wikipedia hat 'ne Liste für Optimierungssoftware