Algorithmus: Optimale Kombination von verschiedenen Längen

[Jonelmeier]

Hi,

ich habe eine Frage an alle Algorithmus-Freaks unter euch:

Situation: Ich habe eine Menge verschiedener Längen (von 16cm bis 68cm, Werte können mehrfach auftreten).

Problem: Ich möchte die einzelnen Längen so kombinieren, das ich möglichst viele 100cm Längen bekomme (± 2cm). Es dürfen 2 bis 4 Elemente aus der Grundmenge verwendet werden.

Hintergrund: Es geht um Granitblöcke, aus denen jeweils möglichst genau 100cm lange Treppenstufen zusammengesetzt werden sollen, ohne die Blöcke zu zerschneiden. Auf dem Papier, durch knobeln und ausprobieren existiert bereits eine Lösung, jedoch würde es mich reizen dieses Problem algorithmisch (allgemeiner) zu lösen, u.A. um z.B. die Länge der Stufen oder die Anzahl der zulässigen Blöcke variieren zu können, ohne neu knobeln zu müssen.

Vielleicht kann mir ja jemand einen kleinen Denkanstoß liefern.

Gruß Jonas

[fox67]

Ich würde so beginnen das du dir eine Klasse machst die zwei Variablen enthält Id und Länge. Und dann eine Procedure die mit dem Block mit der Id 1 anfängt und die Länge jedes Blockes einzeln zuder Länge des einen Blockes dazu addiert ergibt es dann bei zwei Blöcken die Länge 100 werden beide Ids in einer Liste gespeichert. Dann wird das selbe gemacht mit block 2 und so weiter zum Schluss wird dann das ergebnis aus der Liste ausgelesen.
Gruß Arni

[bernerbaer]

Algo bei Wikipedia Eindimensionales_Zuschnittproblem oder wikipedia Verschnittplanung

[fox67]

Meine Methode klappt aber nur wenn du die Zahl vorgibst wie viele Blöcke zusammengewürfelt werden können. Deshalb ist sie für dich wahrscheinlich eher unpraktisch

[Jonelmeier]

Der Artikel über das Eindimensionale Zuschnittproblem klingt interessant, leider ist mir die theoretische Definition zu hoch, ich bräuchte eine Pseudo-Implementierung des Algorithmus.

Ich bin noch auf das Behälterproblem gestoßen, welches aber in diesem Fall keine optimalen Ergebnisse liefert:

Code:

Sortiere die Objekte nach absteigendem Länge
Füge die Objekte der Reihe nach ein,
    sodass jedes in den ersten Behälter gegeben wird, in dem noch genug Platz ist.
    Falls in keinem der bereits geöffneten Behälter genügend Platz ist, öffne einen neuen.

Auch die Variante Best Fit Decreasing des Behälterproblems verhält sich ähnlich.

[bernerbaer]

ich habs nicht näher angeschaut aber vielleicht ist ja das etwas:
delphiforfun

[Aphton]

edit: ..

[Panthrax]

Mathematische Sicht: Man kann es als ein lineares Gleichungssystem ausdrücken und dann mit dem Simplex-Verfahren lösen. Allerdings: Die Gleichungen, welche die Kombinationen der Einzelstücke zur Ziellänge ausdrücken, müssen selbst algorithmisch gefunden werden; und, das Simplex-Verfahren ist wahrscheinlich nicht mal eben implementiert.

Mir ist kein Lösungsweg eingefallen ohne einen Zwischenschritt mit einem anderen Algorithmus (hier das Finden der Kombinationen).

Praktische Sicht: Der Computer ist fleißig, einfaches Durchprobieren tut's vielleicht auch? Das ist aber vielleicht auch nicht mehr im Sinne des Erfinders?

Wie gesagt, eine gezielt-algorithmisch-mathematische Lösung ist nicht so einfach -- wegen der Mathematik und der Implementierung. Das soll aber nicht entmutigen! Es bleibt noch eine (vielleicht nur hypothetische) Frage: Ich nehme auch an, dass die Zahl verfügbarer Längenstücke begrenzt ist, oder werden die erst zugeschnitten?

[Horst_]

Hallo,

Zitat von bernerbaer:

ich habs nicht näher angeschaut aber vielleicht ist ja das etwas:
delphiforfun

Das sieht ja gut aus, ist leider die Umkehrung des Problems.
Ich habe nur 1 m Stücke und brauche 4 von 68 cm,... 7 von 17 cm ...
Wie bekommt man da die Unschärfe von 100 +- 2 cm rein.
Vielleicht mit integer Rechnung und der Angabe der möglichen Länge und mit Kosten pro cm = konstant
Treppe.txt sieht so aus:
5 verschiedene Ausgangslängen
6 verschiedene Ziellängen

Code:

5 6 2
PARTS
   Length   # Required
    67.00   4
    57.00   4
    41.00   4
    32.00   4
    25.00   4
    17.00   7

STOCK
   Length   Cost
   102.00    102.00
   101.00    101.00
   100.00    100.00
    99.00    099.00
    98.00    098.00

Mit dem Ergebnis:

Code:

 --- Optimal Integer Solutuion ---
Pattern(1)  Stock length:     99,00  Needed: 4
   Order length:  67,00  Number cut from each stock piece:     1
   Order length:  32,00  Number cut from each stock piece:     1
   Unused from each stock piece 0,00
Pattern(2)  Stock length:     98,00  Needed: 4
   Order length:  57,00  Number cut from each stock piece:     1
   Order length:  41,00  Number cut from each stock piece:     1
   Unused from each stock piece 0,00
Pattern(3)  Stock length:     99,00  Needed: 0
   Order length:  41,00  Number cut from each stock piece:     2
   Order length:  17,00  Number cut from each stock piece:     1
   Unused from each stock piece 0,00
Pattern(4)  Stock length:     98,00  Needed: 0
   Order length:  32,00  Number cut from each stock piece:     2
   Order length:  17,00  Number cut from each stock piece:     2
   Unused from each stock piece 0,00
Pattern(5)  Stock length:    100,00  Needed: 1
   Order length:  25,00  Number cut from each stock piece:     4
   Unused from each stock piece 0,00

Das sieht doch nicht schlecht aus.

Gruß Horst

[bernerbaer]

Zitat von Horst_:

... Das sieht ja gut aus, ist leider die Umkehrung des Problems.

Ich habe mir das Programm mal ganz kurz angeschaut und verstehe nicht weshalb es eine Umkehrung deines Problems sein sollte. So wie ich es verstehe, erfüllt es doch _fast_ genau deine Anforderungen, Du hast Blöcke mit einer Seitenlänge von 100cm und willst aus diesen Blöcken möglichst optimal die bestellten Längen herausschneiden, und genau das macht das Programm.

• Du hast Blöcke mit 100cm Länge (= Längeneintrag bei "Available stock size")
• Du hast bestellt Stücke zu x, y, z, ... cm Länge (Eintrag bei "Ordered Size" -> Size)
• Du hast die erforderliche Anzahl der bestellten Stücke [Eintrag bei "Ordered sizes" unter "Nbr required"

Das Programm gibt dir nun aus, wieviele Blöcke du benötigst und zeigt dir die Aufteilung der Blöcke an.

Zitat von Horst_:

... Wie bekommt man da die Unschärfe von 100 +- 2 cm rein.

Was meinst du genau mit Unschärfe? Ist damit der Schnittverlust gemeint?

Ich habe mir den Source des Programmes nicht angeschaut, aber wenn Du den dahinterliegenden Algorithmus findest und verstehst, sollte es "relativ" einfach sein für jeden Schnitt einen Schnittverlust hinzuzufügen. Alternativ, kannst du ja allenfalls eine Sicherheitsmarge bei der Blocklänge eingeben, also zb Statt 100 cm für die Blocklänge zb 98cm.

Oder ist damit die unterschiedliche Breite der einzelnen Blöcke gemeint?

Dann erfüllt, so wie ich es sehe, das Programm deine Anforderungen bereits, du kannst in der Liste der verfügbaren Blöcke unterschiedliche Blöcke mit unterschiedlichen Längen erfassen.