Beste Kombination zur Auffüllung einer Liste

[Volker Z.]

Hallo,

die vorgeschlagene Lösung ist nicht zielführend. Wenn Deine Listen - wie im Beispiel - 3elementig sind und Du das vorgeschlagene lineare Gleichungssystem mit mehr als drei Vektoren (Listen) - die alle ungleich (0, 0, 0) sind - lösen möchtest, dann wirst Du eine unendliche Anzahl an Lösungen erhalten (vier oder mehr Vektoren aus dem R3 sind immer linear abhängig).

Die Aussage

Zitat:

[...] (wie man leicht sieht, gibt es bei Dir keine, wenn statt [3, 2, 4] zb [5, 2, 4] das Ziel wäre, weil 3a+4d = 5 nicht lösbar ist) [...]

ist falsch. (3, 2, 0) + 2 * (0, 0, 2) + 0 * (0, 0, 1) + 0,5 * (4, 0 , 0) = (5, 2, 4)

Du musst schon alle möglichen Listenkombinationen suchen. Soll heißen: Suche Lösungen für die Gleichungssysteme A1x = b, A2x = b, ..., Anx = b. Für alle Ai, für die eine Lösung existiert dann die Kosten berechnen.

Wenn die Listen 3elementig sind könntest Du die Determinante berechnen. Ist die Null gibt es keine Lösung. Wenn:

Code:

    (a11 a12 a13)
A = (a21 a22 a23), dann Det (A) = a11a22a33 -a11a23a32 - a12a21a33 + a12a23a31 + a13a21a32 - a13a22a31
    (a31 a32 a33)

Sorry, leider kann ich die Indizes nicht tiefstellen.

Gruß

[Valle]

Hallo Volker,

ich habe jetzt 'ne ganze Weile versucht mit der Lösung weiter zu kommen, konnte damit aber höchstens das Problem in kleinere Probleme zerschlagen, die ich zwar alle lösen könnte, allerdings alles nicht schön.

Problem scheint zu sein, dass es sich nicht um ein überbestimmtes, sondern um ein unterbestimmtes Gleichungssystem handelt. Das algorithmisch zu lösen ist nicht mehr ganz so einfach.

gammatester hat schon Recht mit seiner Aussage, dass es für die 5 keine Lösung gibt. Denn er schrieb vorher, dass nur ganzzahlig positive Multiplikatoren erlaubt sind. Unter dieser Vorraussetzung gibt es eine endliche Anzahl an Lösungen. Allerdings hilft mir das leider doch nicht so viel weiter wie erhofft.

Liebe Grüße,
Valentin

[gammatester]

Zitat von Volker Z.:

(3, 2, 0) + 2 * (0, 0, 2) + 0 * (0, 0, 1) + 0,5 * (4, 0 , 0) = (5, 2, 4)

Also für mich ist 0.5 keine ganze Zahl, aber wenn Du meinst...

[Volker Z.]

Hallo,

Zitat von gammatester:

Zitat von Volker Z.:

(3, 2, 0) + 2 * (0, 0, 2) + 0 * (0, 0, 1) + 0,5 * (4, 0 , 0) = (5, 2, 4)

Also für mich ist 0.5 keine ganze Zahl, aber wenn Du meinst...

Sorry, habe Deine Nebenbedingung überlesen.

Gruß

[Uwe Raabe]

Die Aufgabestellung hat gewisse Ähnlichkeiten mit dem Rucksack-Problem, bei dem möglichst viele Dinge in den Rucksack gepackt werden sollen ohne ihn zu überfüllen. Die Unterschiede sind

a) die Dinge (Listen) sind in beliebiger Anzahl verfügbar
b) der Rucksack soll ganz voll sein

In diesem Fall bietet sich eine kombinatorische Lösung an. Dabei wird eine Liste in den Rucksack aufgenommen und der daraus resultierende Status überprüft. Ist der Rucksack noch nicht voll, mache ich einfach so weiter. Andernfalls habe ich entweder eine Lösung gefunden (Rucksack ist genau voll) oder der Rucksack ist überfüllt. In beiden Fällen muss ich die zuletzt eingepackte Liste wieder herausnehmen und nehme mir die nächste Liste. Bin ich nun bei der letzten Liste angekommen, nehme ich alle Vorkommen dieser letzten Liste raus. die dann "oberste" Liste nehme ich auch heraus und verfahre so, als ob der Rucksack voll gewesen wäre. Das ganze Spiel geht solange weiter bis ich nur noch Elemente der letzten Liste im Rucksack habe.

Konkret anhand der Beispieldaten:

L0 = [3, 2, 0]
L1 = [0, 0, 2]
L2 = [0, 0, 1]
L3 = [4, 0, 0]

Lösungsbedingung: [3, 2, 4]

Anfangszustand Rucksack: ()|[0,0,0] { leer }

1. (L0) [3,2,0]
2. (2*L0) [6,4,0] // überfüllt
3. (L0+L1) [3,2,2]
4. (L0+2*L1) [3,2,4] // Lösung
5. (L0+L1+L2) [3,2,3]
6. (L0+L1+2*L2) [3,2,4] // Lösung
7. (L0+L1+L3) [7,2,0] // überfüllt, L3 ist letzte Liste
8. (L0+L2) [3,2,1]
9. (L0+2*L2) [3,2,2]
10. (L0+3*L2) [3,2,3]
11. (L0+4*L2) [3,2,4] // Lösung
12. (L0+3*L2+L3) [7,2,3] // überfüllt, L3 ist letzte Liste
13. (L0+2*L2+L3) [7,2,2] // überfüllt, L3 ist letzte Liste
14. (L0+L2+L3) [7,2,1] // überfüllt, L3 ist letzte Liste
15. (L1) [0,0,2]
16. (2*L1) [0,0,4]
17. (3*L1) [0,0,6] // überfüllt
18. (2*L1+L2) [0,0,5] // überfüllt
19. (L1+L2) [0,0,3]
20. (L1+2*L2) [0,0,4]
21. (L1+3*L2) [0,0,5] // überfüllt
22. (L1+2*L2+L3) [4,0,4] // überfüllt, L3 ist letzte Liste
23. (L1+L2+L3) [4,0,3] // überfüllt, L3 ist letzte Liste
24. (L2) [0,0,1]
25. (2*L2) [0,0,2]
26. (3*L2) [0,0,3]
27. (4*L2) [0,0,4]
28. (5*L2) [0,0,5] // überfüllt
29. (4*L2+L3) [4,0,4] // überfüllt, L3 ist letzte Liste
30. (3*L2+L3) [4,0,3] // überfüllt, L3 ist letzte Liste
31. (2*L2+L3) [4,0,2] // überfüllt, L3 ist letzte Liste
32. (L2+L3) [4,0,1] // überfüllt, L3 ist letzte Liste
33. (L3) [4,0,0] // überfüllt, L3 ist letzte Liste, Ende der Kombinationen

Man kann das noch optimieren, in dem man alle Listen gleich raus wirft, die schon alleine zu einer Überfüllung führen. Dann spart man sich einen Haufen Iterationen.

[BUG]

Das Ganze ist ein (leider ganzzahliges) lineares Optimierungsproblem:
Dass die Kombinationen der Listeninhalte die Zielliste ergeben sollen, entspricht den Nebenbedingungen.
Die Zielfunktion ist der Preis einer solchen Kombination.

Meine erste Herangehensweise wäre eine naive Version des Branch-and-Bound-Verfahren:
Du machst eine Tiefensuche und jede gefundene gültige Kombination ist deine neue obere Preisschranke (wenn besser).
Die Suchstrategie ist vermutlich etwas, wo am einfachsten etwas optimiert werden könnte (siehe Uwe Raabe).
Im Moment fällt mir wenig ein, wie man sinnvoll eine untere Schranke nutzen könnte, aber vielleicht findest du eine gute obere Schranke mit irgendeiner Heuristik.
Außerdem kann man vermutlich eine untere Schranke für den Preis finden, den man von einer unvollständigen Lösung zu einer gültigen braucht. Damit könntest du mit deiner oberen Schranke mehr Branches abschneiden.

Du könntest das Problem aber auch mit jeder beliebigen Lösungsmethode für ganzzahlige lineare Programmierung lösen.

EDIT/OT:
Ich würde gerne mehr zu dem Problem erfahren ... also:
Was wird da modelliert, wie groß sind die Listen und wie viele sind es?
Außerdem wäre es schön, wenn du die Lösung skizzieren würdest, die du dann letztendlich umgesetzt hast.
Es ist interessant zu sehen, wie solche Probleme in der echten Welt gelöst werden.

[Valle]

Hi,

@Uwe: Vielen Dank für deine Antwort. Dein Post hilft mir wirklich weiter. Ich versuche gerade, deine Schritte in einen Algorithmus umzusetzen. Allerdings fällt mir dabei auf, dass ich die Regeln in denen du diese Listen durchgehst nicht zu verstehen scheine. Möglicherweise hat sich dort aber auch ein Fehler eingeschlichen. Beispielsweise wird die Kombination L1+L3 gar nicht ausprobiert? Hat das einen algorithmischen Grund, den ich nicht erkenne, oder fehlt einfach was?

@BUG: Sehr interessante Artikel, die ich mir sicher noch genauer anschauen werde. Auf den ersten Blick scheinen die Artikel komplizierter als das Problem selbst zu sein. Da werde ich wohl einfach noch ein paar Semester warten, dann kommt das bestimmt auch im Studium.

Du bekommst gern mehr Details zum Problem, sobald ich es gelöst habe.

Liebe Grüße,
Valentin

[Uwe Raabe]

Da hast du natürlich recht: es fehlen einige Kombinationen. Ich habe da wohl die Iterationen mit und ohne L3 (weil L3 ja eh nicht geht) vermischt. (L0+L3) wäre dann bei 14a und (L1+L3) bei 23a einzusortieren.

Für einen Algorithmus bietet sich ein rekursiver Ansatz an. Später kann man den ja immer noch serialisieren.

Als Datenstruktur für eine Lösung wäre ein array of Integer gut geeignet, in dem die Anzahl der einzelnen Listen vermerkt ist. Ich hab da mal quick and dirty was zusammengeschrieben, das du vielleicht als Basis nehmen kannst. Insbesondere die statischen Arrays wird man wohl durch dynamische ersetzen müssen.

Delphi-Quellcode:

program Project255;

{$APPTYPE CONSOLE}

{$R *.res}

uses
  System.SysUtils,
  System.Math;

type
  TSolution = array[0..3] of Integer;
  TListe = array[0..2] of Integer;

const
  Soll: TListe = (3,2,4);
  Listen: array[0..3] of TListe
       = ((3,2,0), (0,0,2), (0,0,1), (4,0,0));
  Kosten: array[0..3] of Integer = (10, 5, 4, 10);

function CalcKosten(const Solution: TSolution): Integer;
var
  I: Integer;
begin
  Result := 0;
  for I := 0 to 3 do
    Result := Result + Solution[I] * Kosten[I];
end;

procedure WriteIteration(const Solution: TSolution; const Liste: TListe; res: Integer);
var
  I: Integer;
  S: string;
begin
  S := '(';
  for I := 0 to 3 do
    S := S + IntToStr(Solution[I]) + ',';
  S[Length(S)] := ')';
  S := S + '[';
  for I := 0 to 2 do
    S := S + IntToStr(Liste[I]) + ',';
  S[Length(S)] := ']';
  if res = 0 then begin
    S := S + ' Lösung: ' + IntToStr(CalcKosten(Solution));
  end
  else if res > 0 then begin
    S := S + ' überfüllt';
  end;
  Writeln(S);
end;

procedure Iteration(var Solution: TSolution; const Liste: TListe; Index: Integer);
var
  newListe: TListe;
  I: Integer;
  newRes: Integer;
  res: Integer;
begin
  Inc(Solution[Index]);
  for I := 0 to 2 do
    newListe[I] := Liste[I] + Listen[Index, I];
  res := 0;
  for I := 0 to 2 do begin
    newRes := CompareValue(newListe[I], Soll[I]);
    if res <> newRes then begin
      if res = 0 then
        res := newRes
      else if newRes > 0 then
        res := newRes;
    end;
  end;
  WriteIteration(Solution, newListe, res);
  if res < 0 then begin
    Iteration(Solution, newListe, Index);
  end;
  Dec(Solution[Index]);
  if Index < 3 then begin
    Iteration(Solution, Liste, Index + 1);
  end;
end;

procedure Main;
var
  Solution: TSolution;
  Liste: TListe;
  I: Integer;
begin
  for I := 0 to 3 do
    Solution[I] := 0;
  for I := 0 to 2 do
    Liste[I] := 0;
  Iteration(Solution, Liste, 0);
end;

begin
  try
    Main;
  except
    on E: Exception do
      Writeln(E.ClassName, ': ', E.Message);
  end;
  Readln;
end.