AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Programmierung allgemein Algorithmen, Datenstrukturen und Klassendesign Algorithmus: Optimale Kombination von verschiedenen Längen

Algorithmus: Optimale Kombination von verschiedenen Längen

Ein Thema von Jonelmeier · begonnen am 24. Mär 2012 · letzter Beitrag vom 26. Mär 2012
Antwort Antwort
Seite 1 von 2  1 2   
Jonelmeier

Registriert seit: 27. Sep 2007
Ort: Hamburg
96 Beiträge
 
Delphi XE Starter
 
#1

Algorithmus: Optimale Kombination von verschiedenen Längen

  Alt 24. Mär 2012, 22:00
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
  Mit Zitat antworten Zitat
fox67

Registriert seit: 6. Okt 2010
Ort: 72661 Grafenberg
181 Beiträge
 
Turbo Delphi für Win32
 
#2

AW: Algorithmus: Optimale Kombination von verschiedenen Längen

  Alt 24. Mär 2012, 22:23
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
  Mit Zitat antworten Zitat
bernerbaer
(Gast)

n/a Beiträge
 
#3

AW: Algorithmus: Optimale Kombination von verschiedenen Längen

  Alt 24. Mär 2012, 22:30
Algo bei Wikipedia Eindimensionales_Zuschnittproblem oder wikipedia Verschnittplanung
  Mit Zitat antworten Zitat
fox67

Registriert seit: 6. Okt 2010
Ort: 72661 Grafenberg
181 Beiträge
 
Turbo Delphi für Win32
 
#4

AW: Algorithmus: Optimale Kombination von verschiedenen Längen

  Alt 24. Mär 2012, 22:34
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
  Mit Zitat antworten Zitat
Jonelmeier

Registriert seit: 27. Sep 2007
Ort: Hamburg
96 Beiträge
 
Delphi XE Starter
 
#5

AW: Algorithmus: Optimale Kombination von verschiedenen Längen

  Alt 24. Mär 2012, 22:43
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.
  Mit Zitat antworten Zitat
bernerbaer
(Gast)

n/a Beiträge
 
#6

AW: Algorithmus: Optimale Kombination von verschiedenen Längen

  Alt 24. Mär 2012, 23:15
ich habs nicht näher angeschaut aber vielleicht ist ja das etwas:
delphiforfun
  Mit Zitat antworten Zitat
Benutzerbild von Aphton
Aphton

Registriert seit: 31. Mai 2009
1.198 Beiträge
 
Turbo Delphi für Win32
 
#7

AW: Algorithmus: Optimale Kombination von verschiedenen Längen

  Alt 24. Mär 2012, 23:27
edit: ..
das Erkennen beginnt, wenn der Erkennende vom zu Erkennenden Abstand nimmt
MfG

Geändert von Aphton (25. Mär 2012 um 15:41 Uhr)
  Mit Zitat antworten Zitat
Panthrax

Registriert seit: 18. Feb 2005
286 Beiträge
 
Delphi 2010 Enterprise
 
#8

AW: Algorithmus: Optimale Kombination von verschiedenen Längen

  Alt 25. Mär 2012, 01:45
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?
"Es gibt keine schlimmere Lüge als die Wahrheit, die von denen, die sie hören, missverstanden wird."
  Mit Zitat antworten Zitat
Horst_

Registriert seit: 22. Jul 2004
Ort: Münster Osnabrück
116 Beiträge
 
#9

AW: Algorithmus: Optimale Kombination von verschiedenen Längen

  Alt 25. Mär 2012, 11:43
Hallo,

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
  Mit Zitat antworten Zitat
bernerbaer
(Gast)

n/a Beiträge
 
#10

AW: Algorithmus: Optimale Kombination von verschiedenen Längen

  Alt 26. Mär 2012, 17:37
... 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.

... 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.
  Mit Zitat antworten Zitat
Antwort Antwort
Seite 1 von 2  1 2   

Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 08:32 Uhr.
Powered by vBulletin® Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2021 by Daniel R. Wolf