Kombinatorik-Problem: Optimierte Auswahl von Zutaten

[blackfin]

Hallo liebe Foren-Profis,

Ich habe ein kombinatorisches Problem, über das ich schon den ganzen Tag grüble, allerdings glaube ich langsam, ich hab da einen Knoten im Kopf und komme nicht auf einen Lösungsansatz.

Folgende Problemstellung ist gegeben:

- Vorhanden sind 2000 Rezepte mit diversen Zutaten.
- Zutaten gibt es insgesamt 100 Stück.
- Es dürfen aber nur 20 Zutaten eingekauft werden.
Frage: Welche 20 Zutaten müssen gekauft werden, um möglichst viele der 2000 Rezepte abzudecken.

Irgendwie habe ich einen Drehwurm im Kopf :(
Kann mit jemand vielleicht einen Lösungsansatz oder Hilfestellung geben?

P.S. Das ist KEINE Schul-Mathematik-Aufgabe, sondern ein reelles Problem, mit dem ich mich da rumschlagen muss :)

[jfheins]

Viel Spaß beim alle-Möglichkeiten-durchprobieren - ich vermute mal, das problem ist np-vollständig ;)

Das Problem erinnert an das Rucksack-Problem, welches np-vollst. ist: http://de.wikipedia.org/wiki/Rucksackproblem

Mit anderen Worten: Wenn meine Vermuting stimmt, kannst du Heuristiken entwickeln, die eine gute Lösung liefern - um jedoch die beste Lösung zu finden musst du alles durchprobieren.

[Mithrandir]

Was doch aber bei den heutigen Rechenleistungen kein Problem darstellt, oder?

[ToFaceTeKilla]

Musst du möglichst viele Rezepte abdecken oder möglichst viele vollständig, also dass alle Zutaten vorhanden sind?

[Satty67]

Ist ja nur eine Logik-Frage, da wäre das auch als Schulaufgabe kein Problem.

Erste Idee von mir war, alle 2000 Rezepte durchgehen und für die darin enthaltenen Zutaten einen Zähler bei den Zutaten hoch zählen. Dann wären die meist gebrauchten Zutaten sichtbar. Aber kann ja sein das es nicht automatisch die Zutaten sind, mit denen auch die meisten Rezepte komplettiert sind?

[blackfin]

Zitat:

Zitat von ToFaceTeKilla

Musst du möglichst viele Rezepte abdecken oder möglichst viele vollständig, also dass alle Zutaten vorhanden sind?

Möglichst viele vollständig. Sonst ist das Rezept ja nicht mischbar, wenn eine Zutat dazu fehlt. :)

Ja, das Rucksack-Problem habe ich mir auch angeschaut, aber irgendwie hat es meinem Kopf auhc nicht geholfen, einen Lösungs-Ansatz zu finden ;/

Danke aber schon einmal für die bis jetzt stehenden Antworten!

[himitsu]

Praktisch alle möglichen Kombinationen an Zutaten durchgehen und für jede Möglichkeit die Anzahl der Rezepte bestimmen, welche damit möglich wären.

[Mithrandir]

Zitat:

Zitat von Satty67

Aber kann ja sein das es nicht automatisch die Zutaten sind, mit denen auch die meisten Rezepte komplettiert sind?

Und wenn man ne Liste mit den 20 häufigsten Zutaten erstellt, und dann alle Rezepte auflistet, in denen nur Zutaten aus dieser Kategorie auftauchen? Dann müssten das doch imho die gesuchen sein, oder?

@blackfin: Wenn das wirklich ein reales Problem ist: Wer braucht denn sowas, wenn ich mal fragen darf? Nur aus Neugier... :stupid:

[blackfin]

Zitat:

Zitat von Daniel G

@blackfin: Wenn das wirklich ein reales Problem ist: Wer braucht denn sowas, wenn ich mal fragen darf? Nur aus Neugier... :stupid:

Klar darfst du fragen!
Allerdings darf ich da wohl auch nicht zuviel sagen :(
Aber soviel: Es geht um Mischroboter und deren optimale Bestückung :)

[jfheins]

Zitat:

Zitat von Daniel G

Was doch aber bei den heutigen Rechenleistungen kein Problem darstellt, oder?

Vielleicht waren die zahlen nur nett gewählt um das Problem für das Forum zu vereinfachen ;)
Außerdem: Wenn es wirklich 100 Zutaten sind, ergibt das 5,36*10^20 Möglichkeiten.
Falls er einen 3GHz-Quanten-Quadcore hat und damit in jedem Takt 4 Möglichkeiten prüft braucht er immernoch 1,4 Jahre
(Natürlich nur, wenn das Problem wirklich NP-schwer ist ...)

Zitat:

Zitat von ToFaceTeKilla

Musst du möglichst viele Rezepte abdecken oder möglichst viele vollständig, also dass alle Zutaten vorhanden sind?

Was kann man mit einem Rezept machen, wenn man nicht alle Zutaten davon hat? :stupid:

[himitsu]

[info] da sich grad mein Beitrag da oben einfach nicht editieren läßt....

Praktisch alle möglichen Kombinationen an Zutaten durchgehen und für jede Möglichkeit die Anzahl der Rezepte bestimmen, welche damit möglich wären.

sind ja nur 2^100-1 = 1,2676506*10^30 Möglichkeiten :angel2:


PS: wenn zutaten übrigbleiben dürfen, dann kann ich dir die Lösung auch so sagen:
nimm alle Zutaten und du kannst damit das Meißte an Rezepten mischen :nerd:

[mirage228]

Lässt sich das nicht ggf. als Zuordnungsproblem bzw. Transportproblem verstehen und mit der ungarischen Methode lösen (sonst ggf. auch Simplex) ?

[himitsu]

Zitat:

Aber soviel: Es geht um Mischroboter und deren optimale Bestückung

dann sind es ja nicht x aus 100, sondern x-maximale_die_der_Robotor_reinbekommt von 100,
damit ließe sich die Anzahl der Möglichkeiten stark reduzieren

wenn dann noch die Anzahl der Robotor bekannt ist, könnte man bestimmt eine gute zusammenstellung wählen, damit diese möglichst viele Rezepte mischen können, ohne ständig neu bestückt zu werden.

[Satty67]

Hmm, wenn man einen 200bit Wert nimmt (oder String mit 0/1), jedes Bit repräsentiert eine Zutat. Dann erstellt man für jedes Rezept den passenden Wert/String.

Kommt man damit durch geschicktes sortieren/filtern weitern... auch nicht oder... auf halber Strecke vertrocknet meine nächste Idee :gruebel:

[jfheins]

Zitat:

Zitat von himitsu

Zitat:

Aber soviel: Es geht um Mischroboter und deren optimale Bestückung

dann sind es ja nicht x aus 100, sondern x-maximale_die_der_Robotor_reinbekommt von 100,
damit ließe sich die Anzahl der Möglichkeiten stark reduzieren

Zitat:

Chef: Warum bekommt der Roboter denn nur 10 Teile, wenn er 20 aufnehmen könnte?
Mitarbeiter: Hey - 10 sind doch auch schon was !?
Chef: Dafür hab' ich aber nicht 10000€ mehr ausgegeben!?
Mitarbeiter: Naja - 10 waren einfacher zu rechnen und da dachte ich mir halt ...
Chef: Ja??
Mitarbeiter: ... dass wir die Bestückung häufiger ändern damit ich weniger rechnen muss!
Chef: und jedesmal die Produktionsstraße komplett stillegen? Für 100€ die Minute Stillstand?
Mitarbeiter: Öhhhhmmm ....

:mrgreen:

[himitsu]

nee, klappt wohl auch nicht ... damit wäre ja nur die Speicherung festgelegt, aber die Methode der Auswahl und Anzahl der Möglichkeiten bleibt.

PS: zu meinem letzem Post...
dazu noch eine Black-/White-Liste, mit Rezepten, welche nicht benötigt werden, bzw. welche auf jeden fall mischbar sein sollten ... und man hat das Problem nicht, daß nötige Mischungen nicht mischbar sind und unnötiges unterstützt wird
und die Zahl der gesamten Möglichkeiten schrumpft auch noch.

[blackfin]

Zitat:

Zitat von himitsu

dazu noch eine Black-/White-Liste, mit Rezepten, welche nicht benötigt werden, bzw. welche auf jeden fall mischbar sein sollten ... und man hat das Problem nicht, daß nötige Mischungen nicht mischbar sind und unnötiges unterstützt wird
und die Zahl der gesamten Möglichkeiten schrumpft auch noch.

Sehr gute Idee, die werde ich mal verfolgen und damit rumprobieren, wie sich das ganze noch eingrenzen lässt. DANKE! :)

[himitsu]

jupp, denn damit sind schon einige der 20 von 100 Zutaten durch die White-List (nötige Zutaten der Rezepte) festgelegt und man muß nur noch den Rest der 20 möglichen Zutaten finden
und über die Black-List (deren Zutaten, welche nur von diesen Rezepten benötigt werden, aber nicht von irgendwelchen anderen) könnten eventuell auch noch Zutaten entfallen, welche man dann nichtmehr testen muß ...

also vorallem die Whitelist spart da schon unheimlich ein, wenn z.B. dadurch schon 10 Zutaten festgelegt sind und man nur noch die Restlichen 10, statt alle 20 finden muß.

20-y von 100-y-z

y = Zutaten von der White-List-Rezepte
z = Zutaten, welche nur in den Rezepten der Black-List vorkommen

[blackfin]

Zitat:

Zitat von jfheins

dann sind es ja nicht x aus 100, sondern x-maximale_die_der_Robotor_reinbekommt von 100,
damit ließe sich die Anzahl der Möglichkeiten stark reduzieren

Öhm...das hatte ich ja eiiigentlich geschrieben *schaut nach oben*. :?: Es dürfen maximal 20 Zutaten eingekauft werden (also 20 Stück, die der Roboter reinbekommt).
Mit den 20 Zutaten sollen dann eben möglichst viele Rezepte abgedeckt werden können, die aber eben insgesamt 100 unterschiedliche Zutaten beinhalten.
Somit ist eben die optimale Bestückung gesucht, mit denen mal möglichst viele Rezepte abarbeiten kann, ohne eine Zutat zu wechseln.
Was hatte ich da falsch geschrieben? Mhm, ich glaub ich bin zu verwirrt heute :D

[jfheins]

Das Zitat ist von himitsu ;)

Okay - 10 Zutaten sind von der Whitelist festgelegt, bleiben noch 10.

100 über 10 ist 1,73*10^13 nehmen wir wieder an, wir hätten unseren 3GHz-Quanten-Quadcore brauchen wir nur noch 24 Minuten.

Wenn man mit etwas realistischeren Werten rechnet (Quadcore, 10ms/Probe = 400 Proben/s) kommt man auch 12 Stunden. Immernoch lang, aber machbar ;)

Ist dann aber natürlich nicht die optimale Lösung (Ohne die Whitelist könnte man evtl. noch mehr Rezepte machen) :stupid:

[himitsu]

nee nee, das mit den 20 hatte ich nur falsch gelesen/verstanden.


da könnte man ja zuerst mal eine Liste zusammenstellen, welche die mglichen Kombinationen aus maximal 20 Zutaten enthält ... aber da dürfte es schneller sein, wenn man über die Rezepte geht und über deren nötigen Zutaten diese Liste erstellt ... die 20000 2000 Rezepte dürften schneller abgearbeitet sein, als alle 2^100 Zutatenkombinationen.

und dann die gefundenen Kombinationen nochmal aufarbeiten (falls sie aus den Rezepten entstanden), so daß auch Kombinationen aus je "genau" 20 Zutaten entstehen

und dann die entstandene Liste nochmal durchgehn und die Rezepte zählen.

[Satty67]

Wieviele Zutaten hat den im Durchschnitt so ein Rezept.. eher 5, 10 oder 15 oder sogar über 20 und der Rest muss von Hand beigemischt werden?

[franktron]

Also eine Lösung die zu >90% richtig ist.

Man suchte die Zutat die am meisten vorkommt dann sucht man im Ergebnis wieder die am meisten vorkommende Zutat u.s.w.

Das Problem ist ob die am meisten vorkommende Zutat auch die meisten Rezepte bringt,
mann kann das aber noch mit Platz 2-10 Testen.

[jfheins]

Zitat:

Zitat von franktron

Also eine Lösung die zu >90% richtig ist.

Man suchte die Zutat die am meisten vorkommt dann sucht man im Ergebnis wieder die am meisten vorkommende Zutat u.s.w.

Das Problem ist ob die am meisten vorkommende Zutat auch die meisten Rezepte bringt,
mann kann das aber noch mit Platz 2-10 Testen.

Diese Lösung kann dazu führen, dass man von allen Rezepten ein paar Zutaten hat, aber für kein Rezept alles. Wär dann auch irgendwie doof ... :stupid:

[Satty67]

Eine abschließende Frage hab' ich noch.

Gibt es wirklich so viele Kombinationen bei 20 aus 100? Darf ja keine Permutation dabei sein. Also 100^20 Kombinationen?

[jfheins]

100 über 20 ist 5,36 * 10^20 ("Kombinationen" - Also die Möglichkeiten, aus einer Menge von 100 Elementen 20 herauszunehemen ohne Beachtung der Reihenfolge)

Mit Beachtung der Reihenfolge ("Variation") sind es 1,3 * 10^39

interessant dazu auch das hier: http://de.wikipedia.org/wiki/Kombinatorik Für die Anzahl der Möglichkeiten mit/ohne Beachtung der Reihenfolge ohne Zurücklegen ;)

[guidok]

Zitat:

Zitat von Daniel G

Zitat:

Zitat von Satty67

Aber kann ja sein das es nicht automatisch die Zutaten sind, mit denen auch die meisten Rezepte komplettiert sind?

Und wenn man ne Liste mit den 20 häufigsten Zutaten erstellt, und dann alle Rezepte auflistet, in denen nur Zutaten aus dieser Kategorie auftauchen? Dann müssten das doch imho die gesuchen sein, oder?

@blackfin: Wenn das wirklich ein reales Problem ist: Wer braucht denn sowas, wenn ich mal fragen darf? Nur aus Neugier... :stupid:

Ich könnte mir folgende Frage vorstellen: Welche 20 Zutaten brauche ich, um möglichst viele Cocktails mixen zu können? :lol:

[Satty67]

Zitat:

Zitat von jfheins

interessant dazu auch das hier: http://de.wikipedia.org/wiki/Kombinatorik Für die Anzahl der Möglichkeiten mit/ohne Beachtung der Reihenfolge ohne Zurücklegen ;)

Ja, Danke... gibt halt ein paar Bereich in der Mathematik, die nicht wirklich zu meinen Stärken gehört. :oops:

[Draos]

Meine Idee wäre eine Liste mit der Häufigkeit jeder Zutat. Die Rezepte, in denen die häufigsten Zutaten vorkommen, sollten dann vervollständigt werden. Wenn noch Zutaten übrig sind nächste Ebene von Rezepten (weniger häufige Zutaten) nehmen. Wäre ne Idee spart auch Rechenleistung, aber ob es die Optimale ist kA.

[franktron]

Zitat:

Zitat von Draos

Meine Idee wäre eine Liste mit der Häufigkeit jeder Zutat. Die Rezepte, in denen die häufigsten Zutaten vorkommen, sollten dann vervollständigt werden. Wenn noch Zutaten übrig sind nächste Ebene von Rezepten (weniger häufige Zutaten) nehmen. Wäre ne Idee spart auch Rechenleistung, aber ob es die Optimale ist kA.

Genau so meinte ich das auch.

Hab mich wohl etwas undeutig ausgedrückt

[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, :gruebel: 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 :shock: ) 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.