Beste Kombination zur Auffüllung einer Liste

[Valle]

Hi DPler,

ich hab hier ein algorithmisches Problem. Vorschläge zur Verbesserung des Thread-Titels sind aber auch willkommen.

Gegeben ist eine Liste, die zum Beispiel so aussieht:

Code:

[3, 2, 4]

Außerdem ist eine Liste solcher Listen gegeben, zum Beispiel so:

Code:

[3, 2, 0], Kosten 10
[0, 0, 2], Kosten 5
[0, 0, 1], Kosten 4
[4, 0, 0], Kosten 10

Zu jeder dieser Listen aus der letzten Liste existiert eine Art Kosten-Feld. Gesucht sind diejenigen Kombination aus Listen, die aufsummiert die erste Liste ergibt. Davon suche ich dann außerdem die billigste. Die zwei möglichen Kombinationen in meinem Beispiel wären dann übrigens:

Code:

[3, 2, 0] + 2 * [0, 0, 2]

und

Code:

[3, 2, 0] + 4 * [0, 0, 1]

. Die erste Kombination hätte Kosten von 20, die letzte würde 26 kosten. Die erste Kombination ist damit die gesuchte Lösung. (Edit:// Ich sehe gerade dass es noch eine eine weitere mögliche Lösung gibt. Sie ist aber auch nicht billiger und das Beispiel sollte klar sein.)

Mir fehlt da leider schon der Ansatz um auf die möglichen Kombinationen zu kommen. Herausfinden, welches die billigste Alternative ist, kann man ja anschließend nach der Betrachtung aller Möglichkeiten.

Hat jemand einen Tipp? Gibt es dazu ein bekanntes Problem o.ä.? Ich brauche keine fertige Lösung. Nur ein Schubser wäre toll.

Liebe Grüße,
Valentin

[gammatester]

Nur ein paar Hinweise/Überlegungen: Du suchst doch wahrscheinlich positive ganze Zahlen a,b,c,d mit

Code:

a*[3, 2, 0] + b*[0, 0, 2] + c*[0, 0, 1] + d*[4, 0, 0] = [3, 2, 4]

Das ist ein überbestimmtes lineares Gleichungsytem. Wenn es überhaupt Lösungen gibt (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), kannst Du die Kosten errechnen. Ein weiteres Problem sind dann nur noch verschiedene Lösungen mit gleichen Kosten.

Einen Algorithmus kann ich allerdings nicht anbieten.

[Valle]

Zitat von gammatester:

Das ist ein überbestimmtes lineares Gleichungsytem.

Das klingt klasse! Vielen Dank, damit kann ich denke ich arbeiten!

Zitat von gammatester:

Problem sind dann nur noch verschiedene Lösungen mit gleichen Kosten.

Das wird in der Realität vermutlich nicht vorkommen. Falls doch hätte es für meine Anwendung dann keine Relevanz, welche Lösung genommen würde.

Zitat von gammatester:

Einen Algorithmus kann ich allerdings nicht anbieten.

Will ich auch gar nicht. Selbst denken macht mehr Spaß.

Liebe Grüße,
Valentin

[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