Sortierungsproblem (?) minimaler Abfall

[Christian G. (Gast)]

Hallo Forum,

ich habe gestern Abend mit einem Freund darüber diskutiert, wie man 
folgendes Problem am einfachsten löst:

Ausgangspunkt ist z.B. ein Stangenmaterial von einer Länge x. Nun möchte 
ich gewisse Länge daraus gewinnen (Y1 - Y10) und das Ganze so, dass 
möglichst wenig Abfall entsteht. Ich hab in Erinnerung, dass es dafür 
eine Abschätzung o.ä. gab. Das Problem dabei ist, dass die Sache mit 
steigender Stückanzahl sehr komplex wäre. Einfachster Ansatz wäre eine 
plumbe Runterprogrammierung einer Aneinanderreihung der Längen mit dem 
Vergleich der Ergebnisse am Ende.

Gibt es dafür keine einfachere Lösung?

Schönen Gruß
Christian

[Karl H. (kbuchegg)]

So was ähnliches hatte ich mal als Aufgabe.
Wenn ich mich richtig erinnere, hab ich ich da im Prinzip "Plumpes 
Runterprogrammieren" in Form eines Backtracking mit einer zusätzlichen 
Heuristik (die langen Teile werden zuerst verteilt, ...) darauf 
angesetzt.

Solche Kombinationssachen laufen sehr oft auf eine Backtracking-Lösung 
raus. Also systematisch alle möglichen Kombinationen durchprobieren.

[Klaus W. (mfgkw)]

Christian G. schrieb:
> Gibt es dafür keine einfachere Lösung?

Einfach und gut wird schwierig.

Generell kommen etliche ziemlich unterscheidliche Ansätze in Frage wie 
bei jeder Optimierungsaufgabe.

Die beste Lösung wird i.d.R. nicht nötig sein und nicht gewünscht, wenn 
sie unerträglich lange dauert.
Dann sind genetische Algorithmen auch immer sehr interessant, aber nicht 
unbedingt einfach umzusetzen.

[Εrnst B. (ernst)]

Christian G. schrieb:
> Gibt es dafür keine einfachere Lösung?

Wenn du eine findest, kriegst du 1.000.000 US-Dollar ;)

http://de.wikipedia.org/wiki/P-NP-Problem
(genauer: http://de.wikipedia.org/wiki/Rucksackproblem)

http://de.wikipedia.org/wiki/Millennium-Probleme

In der Praxis löst man das (wie oben vorgeschlagen) durch Algorithmen, 
die eine "ausreichend gute" Lösung ausspucken, halt nicht unbedingt die 
Beste.

[Paul Baumann (Gast)]

Ich kann mich erinnern, daß wir zu DDR-Zeiten einen Revolver-Dreh-Auto-
maten hatten, der Anschlußstücke für Hydraulikschläuche herstellte und
da ging es auch darum, die Reihenfolge der Teile zu bestimmen, um aus
dem Stangenmaterial die optimale Teileanzahl herauszukriegen.

Das Ding war von einem Prozessrechner gesteuert und darauf lief ein
Programm, was das bewerkstelligte. Gehen geht das also...


Ich habe hier:
http://www.optimierung.ch/Beschrieb.shtml

eine Seite gefunden, wo man sich dieses Problems angenommen hat. 
Vielleict
hilft Dir das.

MfG Paul

[D. I. (Gast)]

Εrnst B✶ schrieb:
> Christian G. schrieb:
>> Gibt es dafür keine einfachere Lösung?
>
> Wenn du eine findest, kriegst du 1.000.000 US-Dollar ;)
>
> http://de.wikipedia.org/wiki/P-NP-Problem
> (genauer: http://de.wikipedia.org/wiki/Rucksackproblem)
>
> http://de.wikipedia.org/wiki/Millennium-Probleme
>
> In der Praxis löst man das (wie oben vorgeschlagen) durch Algorithmen,
> die eine "ausreichend gute" Lösung ausspucken, halt nicht unbedingt die
> Beste.

Für die Hobbyalgorithmiker hier: Das ist kein Rucksackproblem, ...

außerdem fehlen noch Informationen: Ist 6x1m Abfall besser / schlechter 
als 1x6m Abfall? Oder willst du eigentlich nicht einfach die Anzahl der 
benutzten Stangen minimieren?

[Klaus W. (mfgkw)]

Ich sage doch gar nichts von Rucksäcken :-)

[D. I. (Gast)]

Klaus Wachtler schrieb:
> Ich sage doch gar nichts von Rucksäcken :-)

dich habe ich ja auch nicht zitiert ;)

[Εrnst B. (ernst)]

Klaus Wachtler schrieb:
> Ich sage doch gar nichts von Rucksäcken

Ne, das war mein Fehler. Ich wollte die Stangenabschnitte im Rucksack 
mitgehen lassen, und dabei den Wert meines Diebesgutes maximieren ;)

[Klaus W. (mfgkw)]

.. und dann dabei Brotkrümel streuen, um später den Rückweg wieder zu 
finden (back tracking?)

[Läubi .. (laeubi)]

Das ganze hört sich für mich nach dem "Bin packing" Problem an:
http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo24.php
Gibt es auch mit Rechtecken, da geht es aber mehr um eine Fläche, 
eventuell kann man sich da was ausborgen indem man das Problem passend 
transformiert.

Die "Bins" wären dann deine Stangen, das "Gewicht" die gewünschte Länge, 
der übrig gebliebene Platz dein "Abfall", hier gibt es ein Javaapplett 
als Animation: 
http://www-cg-hci-f.informatik.uni-oldenburg.de/~da/iva/baer/start/bin1.html