Entwickler-Ecke

Algorithmen, Optimierung und Assembler - längenoptimierung


ThunderDragon - Mo 06.06.05 22:48
Titel: längenoptimierung
Hallo.

Ich versuche, eine Längenoptimierung zu Programmieren. Leider finde ich überhaupt keinen Ansatz... Vielelicht kann mir jemand helfen.

Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136:
137:
138:
139:
140:
141:
142:
143:
144:
145:
146:
147:
148:
149:
150:
151:
152:
153:
154:
155:
156:
157:
158:
159:
160:
unit uHaupt;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls, ExtCtrls;

type
  TForm1 = class(TForm)
    GroupBox1: TGroupBox;
    eLaenge: TLabeledEdit;
    Label1: TLabel;
    Label2: TLabel;
    Label3: TLabel;
    eStange1laenge: TEdit;
    eStange2laenge: TEdit;
    eStange3laenge: TEdit;
    eStange4laenge: TEdit;
    eStange5laenge: TEdit;
    eStange1anzahl: TEdit;
    eStange2anzahl: TEdit;
    eStange3anzahl: TEdit;
    eStange4anzahl: TEdit;
    eStange5anzahl: TEdit;
    bRechnen: TButton;
    GroupBox2: TGroupBox;
    eErgebnis: TLabeledEdit;
    Edit1: TEdit;
    procedure bRechnenClick(Sender: TObject);
  private

  public

  end;

var
  Form1: TForm1;
  Schnitte:Array[0..4,0..1of Integer;
  Rest:Array[0..4of Integer;
  Laenge:Integer;

implementation

{$R *.dfm}

Procedure Sortiere2;
Var I,Z:Byte;
    H:Integer;
    K:Integer;
Begin
Z:=0;
  Repeat
  begin
    for I:=0 To 3 Do
    begin
      H:=Schnitte[I,0];
      if H < Schnitte[I+1,0Then
      Begin
        Z:=1;
        // Laengen tauschen
        Schnitte[I,0]:=Schnitte[I+1,0];
        Schnitte[I+1,0]:=H;
        // Anzahl tauschen
        K:=Schnitte[I,1];
        Schnitte[I,1]:=Schnitte[I+1,1];
        Schnitte[I+1,1]:=K;
      end else Z:=0 end// If
    end// I
  Until Z=0;
end;

Procedure Sortiere;
Var I,Z:Byte;
    H:Integer;
    K:Integer;
Begin
  For Z:=0 To 4 Do
  begin
    for I:=0 To 3 Do
    begin
      H:=Schnitte[I,0];
      if H < Schnitte[I+1,0Then
      Begin
        // Laengen tauschen
        Schnitte[I,0]:=Schnitte[I+1,0];
        Schnitte[I+1,0]:=H;
        // Anzahl tauschen
        K:=Schnitte[I,1];
        Schnitte[I,1]:=Schnitte[I+1,1];
        Schnitte[I+1,1]:=K;
      end// If
    end// I
  end//Z
end;

procedure TForm1.bRechnenClick(Sender: TObject);
Var I:Byte;
    Haelfte,Hilf:Integer;
begin
  For I:=0 to 4 do Schnitte[I,1]:=0;
  For I:=0 to 4 do Schnitte[I,0]:=0;

  Schnitte[0,0]:=STrtoint(eStange1laenge.Text);
  Schnitte[1,0]:=STrtoint(eStange2laenge.Text);
  Schnitte[2,0]:=STrtoint(eStange3laenge.Text);
  Schnitte[3,0]:=STrtoint(eStange4laenge.Text);
  Schnitte[4,0]:=STrtoint(eStange5laenge.Text);

  Schnitte[0,1]:=STrtoint(eStange1Anzahl.Text);
  Schnitte[1,1]:=STrtoint(eStange2Anzahl.Text);
  Schnitte[2,1]:=STrtoint(eStange3Anzahl.Text);
  Schnitte[3,1]:=STrtoint(eStange4Anzahl.Text);
  Schnitte[4,1]:=STrtoint(eStange5Anzahl.Text);

  Sortiere2;

  eStange1laenge.Text:= IntToStr(Schnitte[0,0]);
  eStange2laenge.Text:= IntToStr(Schnitte[1,0]);
  eStange3laenge.Text:= IntToStr(Schnitte[2,0]);
  eStange4laenge.Text:= IntToStr(Schnitte[3,0]);
  eStange5laenge.Text:= IntToStr(Schnitte[4,0]);

  eStange1anzahl.Text:= IntToStr(Schnitte[0,1]);
  eStange2anzahl.Text:= IntToStr(Schnitte[1,1]);
  eStange3anzahl.Text:= IntToStr(Schnitte[2,1]);
  eStange4anzahl.Text:= IntToStr(Schnitte[3,1]);
  eStange5anzahl.Text:= IntToStr(Schnitte[4,1]);

  Laenge:=strtoint(eLaenge.text);
  Haelfte:=0;
  Hilf:=0;

  if (Laenge<300or (Schnitte[0,0]>Laenge) then
  begin
    showmessage('Fehler');
  end
  else
  begin
  //Haupt
    if Schnitte[0,0]>(laenge/2then
    begin
      Haelfte:=laenge-Schnitte[0,0];
      Hilf:=Haelfte mod Schnitte[1,0];
      for i:=0 to 4 do
      begin
        if Haelfte mod Schnitte[i+1,0] < Hilf then
        hilf:= Haelfte mod Schnitte[i+1,0];
      end;    // FOR
      edit1.Text:=inttostr(Hilf);
    end;    // IF




  end// IF

end;   // Procedure

end.


MfG

Thunder


Narses - Di 07.06.05 13:07

Moin und :welcome: im Forum!

user profile iconThunderDragon hat folgendes geschrieben:
Leider finde ich überhaupt keinen Ansatz... Vielelicht kann mir jemand helfen.

Du solltest dein Problem vielleicht etwas detailierter darstellen, nur mit "Längenoptimierung" und dem Code blicke ich (und die andern hier vermutlich auch, sonst hätte ja schon jemand geantwortet) nicht wirklich, was du da zu tun versuchst. :wink:

cu
Narses


Spaceguide - Di 07.06.05 19:32

Meinst du vielleicht Run-Length-Encoding?


ThunderDragon - Di 07.06.05 22:05

Ich will aus einer vorgegebenen länge von Stangenrohlingen kleinere Teile ausschneiden, und am Ende soll mir die Benötigte Anzahl von Stangenrohlingen ausgegeben werden.

Vielelciht hilft das hier:
user defined image


Narses - Di 07.06.05 23:29

Moin!

Willst du (irgend)eine Lösung oder die Optimale? Wenn du eine optimierte Lösung haben willst, dann ist das allerdings keine ganz einfache Angelegenheit, da das Problem NP-vollständig ist. Wenn es nicht so viele Permutationen sind, kannste einen Backtracking-Algorithmus verwenden, ansonsten gibt´s da auch spannende Ansätze mit Ameisen (kein Witz -> Travelling-Salesman-Problem! hat Ähnlichkeit mit deinem).

Mach dich mal mit dem Travelling-Salesman-Problem vertraut, der Ansatz sollte auch für dein Problem gültig sein.

cu
Narses


Spaceguide - Mi 08.06.05 00:52

Das Problem ist wohl eher eine Abart von one-dimensional bin packing.