Kombinatorik-Problem: Optimierte Auswahl von Zutaten

[nachti1505]

Ich werfe mal völlig unqualifiziert den Begriff "Dynamische Programmierung" in den Raum. Nützlich zum Lösen von Optimierungsproblemen, welches eben dieses ja darstellt....

[angos]

Hi,


Vielleicht denke ich nicht weit genug, aber würde es nicht helfen, das Problem so herum anzugehen:

solange noch verfügbare Zutaten > 20 sind, ermittle die am wenigsten vorkommende Zutat und entferne alle Rezepte, welche diese Zutat nutzen.


Gruß
angos

[oki]

Mal eine Idee.

Natürlich kann man alle Kombinationen von 20 Zutaten aus 100 Zutaten bilden. Das sehe ich aber nicht als Sinnvoll an. Unabhängig davon, dass die Ergebnismenge zu groß wird, ergeben sich Kombinationen, die in der Masse auf keins der 2000 Rezepte passen. Damit ist doch die Anzahl der gesuchten Kombinationen viel kleiner.
Mal ein Beispiel.
Eins der 2000 Rezepte benötigt 19 Zutaten. Dan bleibt für den Einkauf doch nur noch eine Zutat übrig. Jetzt muss ich doch nicht alle übrigen 81 Zutaten durchkombinieren, sondern nur die Zutaten suchen, die in den bleibenden 1999 Rezepten enthalten sind. Daruber kann ich eine Statistik setzen, welche eine Zutat am haüfigsten raus kommt. Dann nehme ich das nächste Rezept und mache das gleiche.
Öhm, Tja, wie nun weiter? Die Idee ist aber, dass es eine Reihe von Kombinationen gibt, die eben nicht zu einem Rezept gehören. Es sind ja nur 2000. Somit ist der wesentliche Anteil (ich denke weit über 90% der Kombinationen) nicht relevant.

Die Grundidee ist, dass man das Pferd von hinten aufzäumt und nicht alle Kombinationen 100 zu 20 ermittelt, sondern alle Kombinationen aus den Rezepten extrahiert.
Bei obigen Beispiel sind das zusätzlich zu dem Rezept mit 19 Zutaten (erste Kombination) nur noch weitere 81 Kombinationen von Zutaten die möglich sind. Natürlich steigt die Anzahl der Kombinationen mit jedem Rezept das weniger Zutaten benötigt, aber man muss nicht alle durchleiern.

Vielleicht ist das ein Ansatz um die Anzahl der Zyklen erheblich zu minimieren.

Gruß oki

[guidok]

Ich werfe mal den Begriff "Rucksackproblem" in die Runde. Vielleicht lässt sich daraus eine Lösung ableiten?

[guidok]

Ich habe noch mal drüber nachgedacht und vielleicht funktioniert folgendes:

Benennen wir die Zutaten mal nach dem Alphabet: A, B, C, usw.

Einige mögliche Rezepte wären: BFI, AFJ, BGK, BEH, BFJ

Nehmen wir an fünf Zutaten sind maximal erlaubt, also beginnen wir beim ersten Rezept (BFI) und erhalten die ersten drei Zutaten:

B F I

Jetzt nehmen wir das nächste Rezept (AFJ) und füllen noch zwei Zutaten auf (da eine ja bereits vorhanden ist):

B F I A J

Ab jetzt kann keine weitere Zutat mehr dazukommen und es muss nur noch geprüft werden, welche Rezepte sich mit den vorhandenen Zutaten noch mischen lassen. Macht in Summe drei Rezepte (BFI, AFJ und BFJ).

Jetzt beginnen wir dieses Spiel wieder von vorne, allerdings beginnen wir nicht mit dem ersten Rezept sondern mit dem zweiten. Es ergibt sich eine neue Zutatenkombination und demnach andere Rezepte, die möglich sind.

[oki]

Das entspricht in etwa der Vorgehensweise die ich in Beitrag 33 erläutert habe.

Wenn die Kombination aller Zutaten zu viele Möglichkeiten liefert (und das sind wirklich viele ) dann nehmen sich 2000 Rezepte zum Durchleiern (von mir aus auch 2000*2000) eher bescheiden aus.

Gruß oki

[Blup]

Die selbe Idee hatte ich auch und dazu mal schnell eine rekursive Prozedur und Zufallsdaten erzeugt.
100 Zutaten
2000 Rezepturen mit jeweils 3..10 Zutaten
Die Rezepturen habe ich vorsortiert, so daß Rezepturen mit vielen Zutaten am Anfang stehen.
Dadurch lässt sich die Anzahl der in hoher Rekursionstiefe zu berücksichtigenden Rezepturen optimieren.
Trotzdem schätze ich die Rechenzeit immer noch auf mehr als eine Woche.

[angos]

Nochmal meine Idee,

ein bisschen besser beschrieben:

1.) Ermittle die am geringsten vorkommene Zutat

2.) Enterne alle Rezepte aus der Rezeptliste mit dieser Zutat

3.) Entferne die Zutat aus der Zutatenliste. Berücksichtige hierbei, dass auch direkt Zutaten entfernt werden, welche nur in den
oben entfernten Rezepten vorhanden sind


Wiederhole 1 bis 3, bis du deine gewünschte Anzahl an Zutaten erreicht hast.

Das dürfte eine enorme Einsparung an Schleifendurchläufen ergeben. Ich denke auch, dass das Ergebnis hier doch sauber sein sollte. Oder habe ich etwas völlig vergessen zu berücksichtigen?

Gruß
Ansgar

[Blup]

Deine Idee liefert sicher ein gutes Ergebnis.
Für die Praxis dürfte es völlig ausreichen.
Aber es lassen sich leicht Fälle konstruieren, in denen sich das Optimum so nicht ermitteln lässt.
Die Diskussion ist hier eher theoretischer Natur, gibt es einen Algo der beweisbar und mit vertretbarem Zeitaufwand das Optimum findet (es kann auch mehrere Ergebnisse geben).

[guidok]

Ich fände es schon interessant, die vorgeschlagenen Algorithmen im direkten Vergleich zu sehen. Geschwindigkeit und vor allem das Ergebnis! Habe hier leider kein Delphi zur Verfügung und auf der Arbeit werde ich keine Zeit dazu finden... Schade.

Wäre siche ne lustige Idee daraus einen kleinen sportlichen Wettbewerb zu machen.