Sortierungsproblem (?) minimaler Abfall

Christian G. Gast #2499241
Lesenswert?
• ▲
▼ 
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
Antwort Zitieren Bearbeiten Thread verschieben Thread sperren Anmeldepflicht aktivieren Anpinnen Thread löschen Thread mit anderem zusammenführen Beitrag melden
Karl H. #2499250
Lesenswert?
• ▲
▼ 
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.
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Klaus W. #2499383
Lesenswert?
• ▲
▼ 
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.
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Εrnst B. #2499393
Lesenswert?
• ▲
▼ 
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.
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Paul Baumann Gast #2499491
Lesenswert?
• ▲
▼ 
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
Antwort Zitieren Bearbeiten Löschen Beitrag melden
D. I. Gast #2499753
Lesenswert?
• ▲
▼ 
Ε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?
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Läubi .. Persönliche Seite #2500109
Lesenswert?
• ▲
▼ 
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
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Thread beobachten

Antwort schreiben

Bitte melde dich an, um einen Beitrag zu schreiben.

Bestehender Account

oder

Mit Google-Account einloggen

Noch kein Account?

Die Registrierung ist kostenlos und dauert nur eine Minute.

Jetzt registrieren