Autor Beitrag
Pr0g3r Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 44

Win XP
Turbo Pascal, Delphi 5&7, Ti-Basic
BeitragVerfasst: Di 25.05.10 16:25 
Könnte ich die schleife nicht endlos laufen lassen und Zmax einfach ignorieren/rauslassen?
Hidden
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 2242
Erhaltene Danke: 55

Win10
VS Code, Delphi 2010 Prof.
BeitragVerfasst: Di 25.05.10 16:58 
Hi :)

Du könntest mit einem Timer zur Anschauung die Genauigkeit(also ZMax) immer weiter schrittweise erhöhen.

Wenn du die Optimierungslösung aber für irgendwas anwenden willst, musst du wohl oder übel irgendwann aufhören :lol: Du kannst dein Geld schließlich auch nicht einfach immer weiter anlegen, nur weil es immer mehr wird :nixweiss:

lg,

_________________
Centaur spears can block many spells, but no one tries to block if they see that the spell is a certain shade of green. For this purpose it is useful to know some green stunning hexes. (HPMoR)
Pr0g3r Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 44

Win XP
Turbo Pascal, Delphi 5&7, Ti-Basic
BeitragVerfasst: Di 25.05.10 17:13 
Kann ich nicht in der Abbruchsbedingung festlegen, wann er aus der Schleife raus soll?
Hidden
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 2242
Erhaltene Danke: 55

Win10
VS Code, Delphi 2010 Prof.
BeitragVerfasst: Mi 26.05.10 01:53 
Hi :)

Das Ganze soll ja in nachvollziehbar kleinen Schritten ablaufen, daher dachte ich an einen Timer. Die Anzahl der Berechnungen pro Sekunde könnte ja dann exponentiell bis polynormal zunehmen.

Eine Schleife muss in jedem Fall in regelmäßigen Abständen die Prozedur Application.ProcessMessages; enthalten, sonst reagiert das Anwendungsfenster nicht mehr.

Meine Lösung:
ausblenden volle Höhe 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:
type
  TForm1 = class (TForm)
    BtnStart: TButton;
    BtnAbort: TButton;
    TmrCalc: TTimer;
    procedure BtnStartClick(Sender: TObject);
    procedure BtnAbortClick(Sender: TObject);
    procedure TmrCalcTimer(Sender: TObject);
  private
    FStartzeit: TTime;
    FIterationsPerSecond: Integer;
    FIterationsTodo: Extended;
    procedure ContinueCalculation;
  {..}
  end;

implementation

{..}

procedure TForm1.BtnStartClick(Sender: TObject);
begin
  BtnStart.Hide;
  FStartzeit := Now;
  TmrCalc.Enabled := true;
  BtnAbort.Show;
end;

procedure TForm1.BtnAbortClick(Sender: TObject);
begin
  BtnAbort.Hide;
  TmrCalc.Enabled := false;
  BtnStart.Show;
end;

procedure TForm1.TmrCalcTimer(Sender: TObject);
const MaxItarations = Sqrt(MaxInt);
begin
  FIterationsPerSecond := Sqr(Second(Now - FStartzeit));
  FIterationsTodo := FIterationsTodo + FIterationsPerSecond * TmrCalc.Interval / 1000;
  if IterationsTodo > MaxIterations then begin
    FIterationsTodo := 0;
    FStartzeit := Now;  //Neustart, Rechnung zu schnell geworden.
  end;
  while FIterationsTodo > 0 do begin
    ContinueCalculation;
    FIterationsTodo := FIterationsTodo - 1;
    Application.ProcessMessages;
  end;
end;

_________________
Centaur spears can block many spells, but no one tries to block if they see that the spell is a certain shade of green. For this purpose it is useful to know some green stunning hexes. (HPMoR)
Thorsten83
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 191
Erhaltene Danke: 1



BeitragVerfasst: Mi 26.05.10 10:55 
Naja, der Fall dass du gaaaanz viele Items hast ist ja auch relativ easy zu lösen ;)

Das DP kommt dabei aber auch schon längst an seine Grenzen, da der Speicherbedarf ja bei O(OPT(I)*n) liegt...

Habt ihr euch mal einen FPTAS angeguckt?

Ansonsten kann man auch über Branch&Bound rangehen...
Pr0g3r Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 44

Win XP
Turbo Pascal, Delphi 5&7, Ti-Basic
BeitragVerfasst: Mi 26.05.10 11:13 
Hi,
Ich zieh mir FPTAS mal rein.
Noch mal zu dem Sinnflutalgorithmus:
Das mit dem Zmax klappt jetzt einigermaßen, aber ich habe zu
Wähle neue Konfiguration C' (ausgehend von C)
Bis jetzt habe ich immer mit einem Greedy oder vom Evolutionsalgorithmus die neue Konfiguration gewählt.
Gibt es noch andere, schönere Sachen für die neue Konfiguration?
Thorsten83
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 191
Erhaltene Danke: 1



BeitragVerfasst: Mi 26.05.10 11:34 
Hmm randomisiert C' wählen mit ||C-C'||_1 = 1?

Irgendwann ist dann ja der "Wasserpegel" so weit gestiegen, dass du in einem lokalen Maximum hängen bleibst,
also könnte man abbrechen wenn <c, C'> <= W für alle C' mit ||C-C'||=1 ist...

Btw. c ist hierbei der Nutzenvektor... ;)

edit:
Nochmal zum Greedy...
(Hoffe mal, dass das noch nicht geschrieben wurde ;))
Im beschränkten Fall kann der beliebig schlecht werden, z.B. bei folgender Instanz:
Der Rucksack hat eine Kapazität von 1, du hast ein Item mit Profit und Gewicht epsilon und beliebig viele Items mit
Gewicht 1-epsilon/2 und Profit 1-epsilon

Das höchste Profit/Gewicht-Verhältnis hat dann das kleine Item, und dazu passt kein anderes mehr...
Für epsilon -> 0 geht dann auch der Profit gegen 0, obwohl 1 möglich wäre...
Pr0g3r Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 44

Win XP
Turbo Pascal, Delphi 5&7, Ti-Basic
BeitragVerfasst: Do 27.05.10 13:55 
FPTAS bedeutet ja einfach nur Nährungsverfahren. Nach denen suchen wir ja für unser Projekt.
Das Sinnflutverfahren funktioniert jetzt endlich ... :)

Das Greedy-Verfahren ist max 50% schlechter als die optimale Lösung. Also sch****.

Kann mir mal bitte wer die Sache mit dem Ameisenalgorithmus erklären, weil im web habe ich keine vernünftige Erklätung gefunden...

//edit: Ich habe das Prinzip zwar verstanden, weiss aber nicht wie ich das auf das Rucksackproblem anwenden soll