Kombinatorik-Problem: Optimierte Auswahl von Zutaten

[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


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

[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

[jfheins]

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 ....

[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 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 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

[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)