Algorhitmus Entwicklung zu den Gefälleplatten

[scripper]

Hi,

vielleicht haben einige von euch schon mein ersten Thread gelesen der zur Ideensammlung meines Problemes diente.
Für alle die das nicht gemacht haben Hier noch mal der Link.

Wir sind zu der erkenntniss gekommen, dass der Algorhitmus wohl das Hauptproblem ist. Nun möchte ich ein wenig konkreter werden und anfangen einen Algorhitmus zu entwickeln der mein Problem löst. Dazu hab ich mich mal mit dem Rucksack problem beschäftigt. Nun, die Texte zum Rucksackproblem die man in Google findet behandeln das Problem meistens nur mit ein beziehung des Volumens oder des Gewichts. Bei meinem Problem spielt die Form aber noch eine große Rolle. Ich fang einfach mal mit dem Pseudecode den ich mir so gedacht habe an und hoffe ihr ergänzt was euch einfällt.

Problemdefinition: Wie verteile mach ich aus den Platten (Quader) die Zielplatten (Quader mit einer Schrägen) mit mäglichst wenig Verschnitt.

Mäglicher Lösungsweg: Ich denke das sinnvollste wird hier Iteration sein also einfach alle Objektekonstalitionen ausprobieren und die mit dem wenigsten Verschnitt ausgeben.

Pseudocode:

1. Als erstes sollten die Werte auf ihr Zulässigkeit geprüft werden. Also ob es überhaupt möglich ist aus den Platten die Zuschnitte zu erstellen
2. Als ersten Optimierungsschritt wird die Fläche optimiert normalerweiße ist die Fläche des Zuschnittes gleich der Fläche der Orginalplatte. Falls nicht wird die Platte zugeschnitten und ein Schnittplan ausgegeben
3.Nun wird die Dicke optimiert:
3.1 Als erstes sollte man ausprobieren ob eine Platte durch bespielsweiße 2 oder 4 oder mehr beschnitte Komplett ausgenutzt werden kann.
3.2 Dannach sollten die restlichen Platten aufgeteilt werden. Das sollte wie folgt ablaufen
3.3 Er versucht in welche Platten die erste Zielplatte passt
3.3.1 Dann versucht er die erste Platte mit der zweiten in die erste passende ganze Platte
3.3.2 wenns passt versucht er die erste, die zweite und die dritte
3.3.3 wenns passt noch die vierte dazu usw. bis der maximal wert erreicht ist und speicher den verschnitt
3.3.4 dannach macht er den gleichen Vorgang nochmal mit der nächsten Platte die gültig für den ersten Verschnitt war
...
3.4 Sobald er die ganzen Werte überprüft hat versucht er das gleiche mit der zweiten usw. bis alle Platten untergebracht sind
3.5 Am Ende werden die Werte verglichen und die besten Ergebnisse heraus gesucht.
3.6 Dann werden die Werte und die entsprechenden Schnittpläne ausgegeben

So, ich hoffe mal ein paar von euch interessieren sich für dieses Projekt und helfen mir ein bisschen, den Ihr wisst ja ein guter Pseudecode ist die Grundlage für ein guten Algorhitmus
und ein guter Algorhitmus ist die Grundlage für ein gutes Programm :wink:
Ich bin dankbar für jeden Ratschlag, verbesserungsvorschlag, Erfahrung und Idee. Vielleicht findet einer von euch ja auch noch ein Text zum Rucksackproblem der die Form der objekte noch berücksichtigt.

MfG Scripper

 

[wranger]

Moin,

zum besseren Verständnis würde ich dich bitten die Platten noch mal näher zu beschreiben. Was sind denn Gefälleplatten genau. Holz in das eine Schräge gesägt wurde?

Momentan stelle ich mir ein Quader (Breite, Höhe, Tiefe) vor, aus dem 1 - x Gefälleplatten mit unterscheidlichen Maßen, geschnitten werden sollen.

Beispiel:
Quader 1 (1m, 0.7m, 4m)
Quader 2 (1.4m, 1m, 3m)

Platten 1-x sollen jetzt möglichst wenig Verschnitt im Quader 1-x haben?

Platte1 (0.7m, 1m, (2,5m die Seite die auf dem Boden liegt) die Andere, ist ja länger, weil diese Schräg auf die Untere zu läuft. Gar nicht so einfach zu beschreiben , was würde ich jetzt für ein Bild geben !!

Platte 2 ...

Platte 3 ...

War das so gemeint?

MfG
wranger

 

[scripper]

Servus ..

also es handelt sich um Dämmstoffplatten die nach der optimierung auf der einen Seite eine Schräge haben sollen
Ich hab einfach mal zwei beispiel skizzen gemacht zum besseren Verständniss
Also die hier mal eine Skizze einer Orginalplatte:

und daraus soll beispielsweiße das werden

nun wäre es aber auch möglich 2 oder meherere Platten in einer der Orginalplatten unterzubringen und es gibt auch verschiedene Größen von Orginalplatten. Dieser Vorgang soll einfach so optimiert werden das möglichst wenig Verschnitt übrig bleibt.

Entschuldigt diese Skizzen ;-) Zeichnen war noch nie mein Ding

 

[wranger]

Hallo,

ich habe mir zu dem Problem mal folgende Gedanken gemacht:

Gegeben:
x Quader
y Gefälleplatten

Gesucht:
Der Quader der bei einer Teilmenge von y den geringsten Verschnitt hat!

Vorüberlegung:
Ein Quader hat 3 Verschiedene Grundflächen: Draufsicht, Seitenansicht und Frontansicht. Zu jeder dieser Ansichten würde ich eine Liste mit Gefälleplatten erstellen, die dort hinein passen würden. Also zu jedem Quader 3 Listen mit unterschiedlichen y-Konstellationen.

2. Vorüberlegung Algorithmus (einfach)

Quader A Grösse20:
Gefälleplatten in den Grössen : 4,3,7,2,4,5,3,9

20: 4+3+7+2+4 = 20
20: 4+7+2+4+3 = 20 (überspringt 5 da zu gross, läuft aber immer bis zum ende)
20: 4+2+4+5+3 = 18
20: 4+4+5+3 = 16
20: 4+5+3+9 = 20
20: 4+3+9 = 16
20: 4+9 = 13

ende:

20: 3+7+2+4+3 = 19
20: 3+2+4+5+3 = 17
20: 3+4+5+3 = 15
20: 3+4+3+9 = 19
... usw.

20: 7+ ....


MfG
Wranger

 

[wranger]

Hallo,

vielleicht kann euch das noch helfen : http://hss.ulb.uni-bonn.de/ulb_bonn/diss_online/math_nat_fak/2002/schaefer_mike/0098.pdf

Je länger ich nachdenke, um so klarer wird mir, dass sieses Thema meine Gehirnwindungen wohl überbeanspruchen könnte. Noch mal als Tipp: Ich würde das ganze erst mal in 2D ausprobieren.

Also würde ich mir ne Platte zurecht sägen und dazu ein paar Dreiecke und Quader und erst mal wieder anfangen zu puzzeln!

 

[scripper]

Ok ich bins mal wieder ... Erstmal Danke für eure weiter ÜBerlegungen ...
ich hatte nun mal wieder ein wenig zeit mich mit dem Projekt zu beschäftigen und hab einfach mal eine Beispiel rechnung gemacht. Sie ist ein wenig vereinfach. Ich habe die Flächenoptimierung mal weg gelassen.

Gegeben:

Platten 1:
Bezeichnung: P1
Höhe: 80
Breite: 1000
Länge: 1200

Platten 2:
Bezeichnung: P2
Höhe: 120
Breite: 1000
Länge: 1200

Gesucht:

Beschnitt1:
Bezeichnung:S1
Länge: 1200
Breite: 1000
Höhe1: 40
Höhe2: 60

Behschnitt2:
Bezeichnung: S2
Länge: 1200
Breite: 1000
Höhe1: 60
Höhe2: 80

Behschnitt3:
Bezeichnung: S3
Länge: 1200
Breite: 1000
Höhe1: 20
Höhe2: 60

Also ich hab mir folgenden Weg gedacht (Der : soll einsetzen heißen und dahinter kommen immer die Höhenerte der entsprechenden Platten, V sind die Verschnitte)

Einsetzen in Platte1
------------------------------------------------------------------------------
1. S1(40|60):P1(80|80)->V1(40|20) // oder (20|40)
----->S2(60|80):V1(40|20)-> nicht möglich //auch (60|80) in (20|40)
----->S3(20|60):V1(40|20)-> nicht möglich

2. S2(60|80):P1(80|80)->V2(20|0) // oder (0|20)
----->S1(40|60):V1(20|0)-> nicht möglich //auch in (0|20)
----->S3(20|60):V1(20|0)-> nicht möglich

3. S3(40|60):P1(80|80)->V3(60|20) // oder (20|60)
----->S1(40|60):V3(60|20)-> nicht möglich //auch in (20|60)
----->S2(60|80):V3(60|20)-> nicht möglich

Einsetzen in Platte2
--------------------------------------------------------------------------------
1. S1(40|60):P2(120|120)->V1(80|60) // oder (60|80)
----->S2(60|80):V1(60|90)-> Rest(0|0)
--------->Da Rest(0|0) muss noch S3 noch in einer neuen Platte untergebracht werden
--------->S3(20|60):P1(80|80)->Rest(60|20) // Besseres Ergebnis
--------->S3(20|60):P2(120|120)->Rest(100|60)
----->S3(20|60):V1(80|60)-> Rest(0|60) //oder (20|40) noch rest übrig jetzt letze Platte versuchen
--------->S2(60:80):Rest(20:40)-> nicht möglich

2. S2(60|80):P2(120|120)->V2(60|40) // oder (40|60)
----->S1(40|60):V2(60|40)-> nicht möglich // in (40|60) Rest(0|0)
--------->Da Rest(0|0) muss noch S3 noch in einer neuen Platte untergebracht werden
--------->S3(20|60):P1(80|80)->Rest(60|20) // Besseres Ergebnis
--------->S3(20|60):P2(120|120)->Rest(100|60)
----->S3(20|60):V2(60|40)->nicht möglich // in (40|60) Rest(20|0)
--------->S1(40|60):Rest(20|0)->nicht möglich // auch in(0|20)
--------->Da nicht möglich S1 in neuer Platte unterbringen
--------->S1(40|60):P1(80|80)->Rest(40|20) // Besseres Ergebnis
--------->S1(40|60):P2(120|120)->Rest(80|60)

3. S3(20|60):P1(120|120)->V3(100|60) // oder (60|100)
----->S1(40|60):V3(100|60)-> Rest(60|0) //auch in (60|100)->Rest(20|40)
--------->S2(60|80):Rest(60|0)->nicht möglich
--------->S2(60|80):Rest(20|40)->nicht möglich
--------->Daher S2 in neue Platte
----------->S2(60|80):P1(80|80)-->Verschnitt(20|0) //Besseres Ergebnis addiert sich mit oberen Wert
----------->S2(60|80):P2(120|120)-->Verschnitt(60|40) 
----->S2(60|80):V3(100|60)-> nicht möglich //in (60|100)->Rest (0|20)
--------->S1(40|60):Rest(0|20)->nicht möglich
--------->DA nicht möglich, S1 in neue Platte
--------->S1(40|60):P1(80|80)->Rest(40|20) // Besseres Ergebnis addiert sich mit oberem Rest
--------->S1(40|60):P2(120|120)->Rest(80|60)

So nun wird noch das beste Ergebnis rausgesucht in dem man die Rest vergleicht
Hier wäre es:
S1&S2 in P2 ->Verschnitt(0|0)
und S3 in P1 ->Verschnitt(60|40)

So nun muss hab ich die Grundstruktur einer Rechnung mal gemacht, nun muss ich diese noch Dynamisch machen
und in fähigen ProgrammCode umwandeln. Was meint ihr zu der Rechnung, beinhaltet sie Denkfehler oder seht
ihr eine bessere Lösung?? Danke

 

[scripper]

Hier mal noch 2 Bilder um meine Vorgehensweiße klar zu machen:

nur ist mir bei der Zeichnung ein Denkfehler aufgefallen. Man kann nicht mehr als 3 Platten schön unterbringen, da man dannach keine gerade Grundseite mehr hat. Also bei meinem Beispiel, wäre es schwierig noch eine platte in dem Verschnitt unterzubringen oder wie seht ihr das??

 

[wranger]

Man kann nicht mehr als 3 Platten schön unterbringen, da man dannach keine gerade Grundseite mehr hat. Also bei meinem Beispiel, wäre es schwierig noch eine platte in dem Verschnitt unterzubringen oder wie seht ihr das??

Man kann nicht mehr als 2 Platten unterbringen. Ganau an dieser Stelle wird es ja so schwierig.

Wie ordne ich die Platten vernünftig an. Ich würde das auf anhiebt nicht mal so hinbekommen im 2D-Raum, geschwiegen denn dies einem PC beizubringen.