Dotaz: hledani optimalni kombinace slozeni

[Gilhad]

Mam velke mnozstvi smesi, ktere se skladaji z maleho mnozstvi prvku. Mam zadanou vyslednou smes, kterou potrebuju vyrobit (kdyz ne presne, tak aspon neco podobneho). Potrebuju najit, kolik kterych smesi mam smichat, abych dostal pozadovany vysledek. (aspon jedno z moznych reseni).

data vypadaji asi takto:

SMESI.txt:
# p1, p2, p3, p4, p5, p6 # (sloupecky obsahuji mnozstvi prvku v dane smesi, radky jsou jednotlive receptury)
  1   2   10   5   6   7 # smes cislo jedna 1xp1 + 2xp2 + 10xp3 .... + 7xp6
  4   7    3   1   8   12 # smes cislo dva 4xp1 + 7xp2 + 3xp3 .... + 12xp6
...........
  11  2    8   1  96   18 # smes cislo dveste 11xp1 + 2xp2 + 8xp3 .... + 18xp6


POZADAVEK.txt
  230 300 127 55  200  700 # chci smes obsahujici priblizne 230xp1 + 300xp2 + 127xp3 ... + 700xp6

==============
VYSLEDEK.txt
5
0
3
12
.
.
35
# vezmi napriklad 5 dilu smesi 1+ 0 dilu smesi 2 + 3 dily smesi 3 + ... + 35 dilu smesi 200
# a dostanes neco velmi blizkeho pozadavku

Je to nejake carovani s maticemi, ale ted mu nemuzu prijit na jmeno. Problem je samozrejme v tom, ze

• prvku je malo, smesi hodne, dost podobnych, moznych kombinaci muze vyjit hodne - nas zajima najit aspon jednu kombinaci (kteroukoli)
• samozrejme nesmi vyjit zaporne mnozstvi u zadne smesi
• naopak muze vyjit vysledek jako realna cisla, tedy nevadi nam 12.5 dilu smesi osm a 0.12345 dilu smesi devet
• nemusi byt mozne exaktni reseni (pozadavak nelze namichat presne), pak nas zajima aspon reseni priblizne (co nejlepsi aproximace, napriklad metoudou nejmensich ctvercu, nebo tak neco)
• samozrejme nektere smesi muzou mit podobne ci stejne slozeni, (linearne zavisle radky), pak je celkem jedno, jak se to z nich namicha (2 dily mirne slane vody, nebo 1 dil hodne slane vody napriklad)

Doufam, ze jsem problem popsal dost dukladne a nekdo bude vedet, jaka metoda se na to pouziva (idealne kdyby to byla nejaka funkce v pythonu, ale kdyz ne, tak v nejakem snadno dostupnem jazyku, nebo pochopitelny matematicky popis - nacteni a vypis hodnot se uz vzdycky nejak zvladne)

---

---

Odpovědi

[Jendа]

Nepřipomíná to trochu problém batohu?

[sss]

Jo, presne ... cili resenim je klasicke prohledavani s navratem (backtracking).

[Josef Kufner]

Asi bych se vykašlal na superchytré matematické úvahy a šel na to genetickým programováním.

Napsat nějaký jednoduchý evoluční algoritmus není nic těžkého. Fitness funkci (hodnocení kvality jedinců) máš jasnou. Bude potřeba vymyslet rozumnou reprezentaci jedinců, ale i něco naivního postačí. Pak postačí to doplnit o nějaké rozumné optimalizace jedinců, např. pokud vyjde součet moc veliký, tak aby ho to normalizovalo na požadované množství.

Pak to spustíš, necháš to sežrat kopec paměti, zajdeš si na oběd a můžeš začít míchat koktejl.

[Josef Kufner]

... A jak tak nad tím přemýšlím, v podstatě hledáš sadu koeficientů m, které se hodí do součtu y = sum(m(i) * p(i)), kde m je reálné kladné číslo a p jsou polynomy reprezentující jednotlivé směsi (pole floatů m = jedinec).

Trošku mi to ale smrdí lineární algebrou a bázemi lineárních prostorů, kdy pokud by jsi z dostupných směsí vybral skupinu, jejichž polynomy by byly lineárně nezávislé (to lze celkem snadno; projít všechny kombinace a ověřit si to), bude jednoduché je namíchat do správného poměru, tedy přenásobit maticí pro převod z prostoru reprezentovaného jednotkovou maticí (zadání po složkách) do prostoru tvořeného vybranými směsmi.

[Gilhad]

Možná hledáš simplexovou metodu.

[lertimir]

No vždyt to je sada lineárních rovnic asi někde ze 6 třídy.

Když označíme množství směsi jako neznámé veličiny A1, A2, ... A200. Tak pro prvky p1,p2... máme rovnice

1*A1 + 4*A2 +...+ 11*A200 = 230
2*A1 + 7*A2 +...+  2*A200 = 300
.
.
.

Vzhledem k tomu, že proměnných je více než rovnic tak všechna řešení budou vytvářet podprostor v tom 200 dimensionálním prostoru směsí. Stačí to pak oříznout pro nezáporný podprostory. Asi nejjednodušší řešení je nalézt prvních n nezávislých směsí, kde n je počet prvků ve směsích a to jednoduše vyřešit jako soustavu rovnic. Třeba tím simplexem.