Dotaz: Algoritmus optimálního výběru

[camel1cz]

Zdravím a prosím o pomoc s algoritmickým řešením následující úlohy:

Je dáno:

• máme 9 druhů kamenů,
• každá uspořádaná trojice kamenů má určité ohodnocení (řekněme body),
• na začátku dostanu pytlík s mixem kamenů (je dán počet každého z nich).

Pravidla:

• znám ohodnocení těch kombinací,
• mohu si vybrat libovolnou kombínaci z pytlíku,
• mohu tu kombinaci směnit za body podle ohodnocení (tedy příjdu o 3 kameny a dostanu X bodů)

Cílem je získat pro daný mix v pytlíku nejvíce bodů.

Díky za postrčení.

P.S. Hladový algoritmus? Generický algoritmus? Něco jiného? Jak na to? Nějaké knihovny atd.? Řešit to potřebuju v PHP.

---

---

Odpovědi

[Jendа]

Pustil bych na to glpsol.

Problémy:

• není to v PHP
• možná to bude mít exponenciální časovou složitost

[Radek Isa]

jedná se o algoritmy umělé inteligence. Jak velký může být problém??
Doporučuji si něco nastudovat o prohledavání do hloubky(DFS), prohledávání do šírky(BHF), iterativní prohledávání a backtraking. Jedná se o algoritmy s umělou inteligencí.

[camel1cz]

Něčeho takového jsem se obával... zrovna moc zběhlý v tom nejsem a nevyplatí se mi to studovat kvůli této úloze :(

Jinak rozsah problému je: 9 druhů kamenů, 729 kombinací výběru a množství kamenů v úvodní množině řekněme v řádu stovek... umím si představit < 600

[TTTTTTTT]

Od pohledu se mi zdá, že to polynomiální nebude. Potřebuješ garantované maximum nebo ti stačí co nejlepší výsledek? Je to jednorázová úloha, která se může chvíli počítat nebo potřebuješ, aby to generovalo odpovědi na počkání? Té umělé inteligence se moc bát nemusíš, za složitými názvy se schovávají jednoduché algoritmy.

729 můžeš zredukovat na 165 (jestli dobře počítám) - zahoď trojice, které mají nižší ohodnocení než jiná trojice ze stejných kamenů.

[camel1cz]

Jde o interaktivní úlohu - uživatel bude zadávat 9 čísel (počty jednotlivých kamenů) a očekává posloupnost kroků, jak se dopracovat k optimálnímu zisku bodů.

Maximum nemusí být garantované - stačí "dobré maximum"

Jediné na co jsem přišel je: 1) genetický algoritmus, ale snažím se najít přímočařejší řešení... v tomhle oboru nemám moc zkušeností. 2) hladový algoritmus, teda snažit se volit nejziskovější kombinaci co jde.

To zahození je dobrý nápad! Určitě zjednoduší problém... můžu zahodit horší nebo stejné kombinace složené ze stejných kamenů.

[Jendа]

Tady je na to manuál se kterým jsem podobný problém zvládl.

Ten program bude něco jako

*_kamenů >= 0 integer

kombinace1 = 19 bodů
kombinace2 = 11 bodů
...

červených_kamenů = 2*kombinace1 + kombinace2 + ...
...

červených_kamenů <= kolik_máš_červených_kamenů
...

ct = sum kombinace*; max ct; solve

[Jendа]

DFS, BFS, iterativní prohledávání a backtracking mi nepřijde moc jako „algoritmy s umělou inteligencí“. Asi nemám tendenci je vidět všude… A nějak nevím jak to řeší tazatelův problém…

[David]

Prohledávání stavového prostoru je skupinou metod řešení úloh, spadající do oblasti umělé inteligence. Doporučuji si nastudovat základní věci.

[Radek Miček]

Pokud těch kamenů není příliš mnoho, tak to můžete vyřešit dynamickým programováním – pro každou devítici si spočítat maximální skóre. Když pak přecházíte k devítici s větším počtem kamenů, tak zkusíte až 729 způsobů (ve skutečnosti méně), jak tato větší devítice mohla vzniknout z menší devítice (jelikož u té menší již znáte maximální skóre, je snadné spočítat maximální skóre i pro tu větší).

Pokud můžete k řešení použít nějaký externí program, tak bych zkusil nějaký CSP řešič – například minion.

[TTTTTTTT]

Nepochopil jsem - mám problém s menší a větší deviticí (čekal bych, že devítice jsou všechny stejné). Taky mi není jasné, proč uvažovat devítice, když jsou ohodnocené trojice. Ve své úvaze dospěl k závěru, že dynamické programování na to aplikovat nepůjde, tak mě zajímá, jestli jsem něco přehlédl.

jelikož u té menší již znáte maximální skóre, je snadné spočítat maximální skóre i pro tu větší

Pokud znám nejlepší řešení pro 1 trojici a 2 trojice, nevidím jak snadno najít nejlepší řešení pro tří trojice. Jde najít kombimace, kdy v nejlepším řešení pro tři trojice nebude žádná trojice, která je v nejlepších řešeních pro 1 resp. 2 trojice.

[Radek Miček]

Myslel jsem něco jako (s tím, že se výsledky maxSkore budou cachovat):

// poctyKamenu je pole. poctyKamenu[i] oznacuje, kolik kusu i-teho kamene mame.
function maxSkore(poctyKamenu)
  m = 0
  for i = 1 .. 9 do
    for j = 1 .. 9 do
      for k = 1 .. 9 do
        if poctyKamenu umoznuji vybrat trojici (i, j, k) then
          od poctyKamenu odecti kameny pouzite v (i, j, k)
          m = max(maxSkore(poctyKamenu) + skore trojice (i, j, k), m)          
          k poctyKamenu pricti kameny pouzite v (i, j, k)
        end if
      end for
    end for
  end for
end function

[Radek Miček]

Na konci funkce musíte vrátit m, to jsem zapomněl.

[Radek Miček]

BTW, jak psal TTTTTTTT, počet možností by šlo snížit uvažováním neuspořádaných trojic (vyberete si uspořádanou trojici s největším skóre):

  for i = 1 .. 9 do
    for j = i .. 9 do
      for k = j .. 9 do

Dále lze v rekurzivních voláních maxSkore uvažovat pouze lexikálně stejně velké nebo vyšší trojice.

[TTT]

Dík, už chápu. Nevím proč jsem uvažoval jen budovat to "odspodu". Každopádně při uvedených číslech se tímto způsobem zřejmě nedopočítá (buď dojde cache nebo to bude počítat roky). Dá se to zřejmě ještě dost prořezat - např. zkusit nejdřív najít nějaké dobré řešení (třeba hladově) a pak zaříznout výpočet už ve chvíli, kdy vidím, že už nedostanu tak dobré řešení. Nebo podobně jako jsem zahodil některé drojice, můžu si předpočítat i které dvojice (trojice, čtveřice) trojic nikdy nebudou spolu v řešení. Ale i tak bych vsadil spíš na to lineární programování.

[Radek Miček]

Pokud máte hodně kamenů a nehledáte optimální řešení, můžete použít lineární programování.

[Jendа]

To byl ten glpsol nahoře (když zruší integer podmínku, tak to asi nenajde optimum, ale řešení by mohlo být „docela dobré“ a spočítá se rychle).

[Radek Miček]

Lze zkusit php-simplex, ten je v PHP.

[camel1cz]

Trochu sem to pročetl a nevidím způsob, jak to na úlohu LP nasadit.

Nemohu volit jako proměnné sadu 9 proměnných (pro každý kámen jedna) - protože kámen má různou hodnotu v různých kombinacích (v tom je složitost té úlohy).

Musím tedy volit jako proměnné trojice kamenů - nejdříve eliminuji závislost kombinací na pořadí výběrem vždy té nejcennější z nich - tak docílím komutativnosti výpočtu dále. Pak to bude vypadat tak, že budu mít několik set funkcí (to budou zadané ceny kombinací a budou pro mou úlohu konstatní).

x(1) = 3
x(2) = 9
...
x(n) = k(n)

Dále mám nějaké kameny, to vyjádřím:

y(1) = 100 // tím zavedu počet kamenů, možná by mělo být y(m) <= k(m) ale to je detail
y(2) = 23
...
y(9) = 11

Otázka teď ale zní, jak vyjádřím závislost x(n) na kamenech - tedy y(m)?

Podle mého nikdy nedostanu do jedné (ne)rovnice x(n) a y(m), protože hodnota kamenu není konstanta...

Uniká mi něco?

[Radek Miček]

Musím tedy volit jako proměnné trojice kamenů

Ano. Trojice kamenů očísluji 1-729 a x(i) bude vyjadřovat, kolikrát vyberu trojici s číslem i.

Je-li c(i) konstanta s cenou trojice číslo i, pak chceme maximalizovat c(1)*x(1) + … + c(729)*x(729) s tím, že počty použitých kamenů nesmí přesáhnout počty kamenů na vstupu.

Tj. označíme-li n(1), …, n(9) počty kamenů na vstupu, pak pro každé n(j) musí platit:

    (suma x(i) takových, že trojice číslo i obsahuje právě jeden kámen j) +
2 * (suma x(i) takových, že trojice číslo i obsahuje právě dva kameny j) +
3 * (suma x(i) takových, že trojice číslo i obsahuje právě tři kameny j) <= n(j)

[Jendа]

Trochu sem to pročetl a nevidím způsob, jak to na úlohu LP nasadit.

Napsal jsem to výše. (btw. pokud to jde tím dynamickým programováním jak napsal Radek výše, tak to je mnohem lepší)

Pak to bude vypadat tak, že budu mít několik set funkcí

Ano, to není problém, třeba můj úkol pro předmět ze kterého pochází ten manuál měl 10k funkcí a výpočet trval pár sekund.

Otázka teď ale zní, jak vyjádřím závislost x(n) na kamenech - tedy y(m)?

Vyrobíš si proměnné z(1) .. z(n), které značí, kolikrát jsi kterou kombinaci použil. Potom vyrobíš proměnné a(1) .. a(9), které v závislosti na vektoru z ukazují, kolik kamenů jsi využil.

a(1) = 1*z(1) + 2*z(2) + 1*z(4)

pokud v kombinaci 1 je 1 kámen barvy 1, v kombinaci 2 jsou 2 kameny barvy 2, v kombinaci 3 žádný atd.

Pak už jenom zadáš podmínky že nesmíš použít víc kamenů než máš

a(1) <= y(1)

Pak zadáš účelovou funkci - součet ohodnocení * kolikrát ta kombinace padla

ct = z(1)*x(1) + z(2)*x(2) + .. + z(n)*x(n)

A řešíš pro

max ct

Ale jak jsem psal, pokud to jde iterativně dynamicky, dá to lepší výsledek a nejspíš to doběhne i rychleji.

[Radek Miček]

btw. pokud to jde tím dynamickým programováním jak napsal Radek výše, tak to je mnohem lepší

Obávám se, že pro větší počet kamenů to je nepraktické. Například pro 100 kamenů celkem existuje 108! / 100! / 8! možných devític.

[TTTTTTTT]

To je počet možných _zadání_ programu, ne? Velikost potřebná pro řešení je podle mě horší. Uvažujme, že mám od každého kamene 10+ kusů, tedy jsem schopen sestavit 1ibobolných 10 trojic. Do cache se dostane každá kombinace, tedy i všechny kombinace 10 trojic, kterých je 738! / 10! / 728!. To je ještě přibližně totéž jako 108! / 100! / 8!, ale pro 20 kusů od každého míčku se z toho stane 738! / 20! / 718! ~ 10^38 (resp. 10^25 při zredukování 729 na 165), ne "přijatelných" 208! / 200! / 8 ~ 10^15 .

Pokud bych necachoval, tak při 99 kamenech má ta rekurze 33 úrovní s větvícím faktorem 729 (resp. ~150) => 10^66. Hádám, že to tedy ani nedokážu paměť vyměnit za čas.

[Jendа]

(tohle mi nikdy nešlo)

Do cache se dostane každá kombinace, tedy i všechny kombinace 10 trojic

Cache je 9-rozměrné pole o hranách kolik_kamenů_od_té_barvy_máme, ne? Takže pro 20 kusů od každého kamene je to „jenom“ 20^9 * sizeof(uint64) = 4 TB.

[TTTTTTTT]

Hm, mě to kdysi možná i šlo, ale zdá se, že ty časy jsou už ty tam. Máš pravdu.

[Jendа]

A pokud alespoň trochu můžeš, nepoužívej ten php-simplex, ale spouštěj z PHP binárku glpsol. Ten je oproti php-simplexu značně optimalizovaný.

[camel1cz]

jj jedu na tom glpsol... mám to napsané, ale někde je chyba... píše to, že "multiplication of linear forms not allowed" na řádku s tou maximalizací účelové funkce.

Kod vypadá takto (zkráceno):

# x(i) ... promenna kolikrat jsem pouzil kombinaci i (vůbec nebo libovolně krát)
var x1 >= 0;
var x2 >= 0;
var x3 >= 0;
var x4 >= 0;
var x5 >= 0;
var x6 >= 0;
var x7 >= 0;
var x8 >= 0;
var x11 >= 0;
...
var x729 >= 0;

# c(i) ... hodnota kombinace i (dané konstanty)
var c1 = 6;
var c2 = 5;
var c3 = 6;
var c4 = 5;
var c5 = 5;
var c6 = 7;
var c7 = 8;
var c8 = 9;
var c9 = 5;
var c11 = 4;
...
var c729 = 3;

# vstupy a(i) - kolik mám kamenů daných typů (nerovnost, protože nemusím použít všechny)
var a1 <= 6;
var a2 <= 0;
var a3 <= 0;
var a4 <= 0;
var a5 <= 0;
var a6 <= 0;
var a7 <= 0;
var a8 <= 0;
var a9 <= 0;

# a(n) ... pocet pouzitych kamenu n... tohle je dáno zadáním - např. kombinace 1 je ze 3 kamenu typu 1, proto je v a1 člen 3*x1
v1: a1 = 0 + 3*x1 + 2*x2 + 2*x3 + 2*x4 + ...
v2: a2 = 0 + 1*x2 + 2*x11 + 1*x12 + 1*x13 + ...
v3: a3 = 0 + 1*x3 + 1*x12 + 2*x21 + 1*x22 + ... 
v4: a4 = 0 + 1*x4 + 1*x13 + 1*x22 + 2*x31 + ...
v5: a5 = 0 + 1*x5 + 1*x23 + 1*x32 + 2*x41 + ...
v6: a6 = 0 + 1*x6 + 1*x15 + 1*x24 + 1*x33 + ...
v7: a7 = 0 + 1*x7 + 1*x25 + 1*x34 + 1*x43 + ...
v8: a8 = 0 + 1*x8 + 1*x17 + 1*x26 + 1*x35 + ...
v9: a9 = 0 + 1*x9 + 1*x27 + 1*x36 + 1*x45 + ...

# ucelova fce ct = c(1)*x(1) + c(2)*x(2) + .. + c(n)*x(n) - vždy násobím hodnotu kombinace krát počet jejích užití... celkový součet maximalizuji
maximize ct: 0 + c1*x1 + c2*x2 + c3*x3 + c4*x4 + c5*x5 + c6*x6 + ...

solve;
end;

Ty kombinace jsem zkrátil - teda vybral vždy jen jen tu nejlepší permutaci pro danou trojici kamenů - zbylo 165 kombinací.

Netušíte, v čem je zakopaný pes a co je špatně?

[camel1cz]

multiplication of linear forms not allowed

Nemůže být problém v tom, že násobíte proměnné jinýmy proměnnými? Místo c1, c2 atd. bych zkusil použít přímo konkrétní čísla.

[camel1cz]

Díky moc, takhle jsem to nakonec udělal... i když Jenda níže našel asi lepší zápis s ponecháním konstant. Ale to už jsem ladil jednoduchý TCP server, který dotazuji z PHP :)

[camel1cz]

param c1 := 6; etc. Píšou to tady. glpk nepochopil, že je to konstanta, a myslí si, že řešení není hodnědimenzionální mnohostěn, ale že je to omezené nějakým polynomem proměnná*proměnná.

/tmp> cat lin.mod
var x1 >= 0;
var x2 >= 0;
var x3 >= 0;
var x4 >= 0;

param c1 := 6;
param c2 := 5;
param c3 := 6;
param c4 := 5;

var a1 <= 6;
var a2 <= 0;
var a3 <= 0;
var a4 <= 0;

v1: a1 = 0 + 3*x1 + 2*x2 + 2*x3 + 2*x4;
v2: a2 = 0 + 1*x2;
v3: a3 = 0 + 1*x2;
v4: a4 = 0 + 1*x3;

maximize ct: 0 + c1*x1 + c2*x2 + c3*x3 + c4*x4;

solve;
end;
/tmp> glpsol -m lin.mod 
GLPSOL: GLPK LP/MIP Solver, v4.55
Parameter(s) specified in the command line:
 -m lin.mod
Reading model section from lin.mod...
24 lines were read
Generating v1...
Generating v2...
Generating v3...
Generating v4...
Generating ct...
Model has been successfully generated
GLPK Simplex Optimizer, v4.55
5 rows, 8 columns, 15 non-zeros
Preprocessing...
1 row, 2 columns, 2 non-zeros
Scaling...
 A: min|aij| =  1.000e+00  max|aij| =  2.000e+00  ratio =  2.000e+00
Problem data seem to be well scaled
Constructing initial basis...
Size of triangular part is 1
*     0: obj =   1.200000000e+01  infeas =  0.000e+00 (0)
*     1: obj =   1.500000000e+01  infeas =  0.000e+00 (0)
OPTIMAL LP SOLUTION FOUND
Time used:   0.0 secs
Memory used: 0.1 Mb (102316 bytes)
Model has been successfully processed

No a tohle ti najde řešení, které když zaokrouhlíš, tak asi bude nějak „přiměřeně dobré“ (v tom předmětu ze kterého to pochází se pak třeba dokazuje jestli takto získané řešení není více než 2x horší než skutečné optimum atd.). Když za "x" proměnné napíšeš "integer" (var x1 >= 0, integer;), tak to najde optimum, ale asi to bude počítat dýl (obecně až exponenciálně dlouho).

[Radek Miček]

obecně až exponenciálně dlouho

Obecně i Simplex počítá exponenciálně dlouho (lineární programy lze však řešit v polynomiálním čase – například elipsoidovou metodou).

[Jendа]

Jsem se musel podívat jestli jsi mě z tohohle předmětu vlastně letos necvičil, ale ne, to byl Radek Hušek .

Vím, a gplk neimplementuje elipsoidovou metodu?

[camel1cz]

Tak hlásím úspěch! Sice mi to vrací v některých případech nepřípustné kombinace, ale to bude asi chybou v sestavení rovnic... případné odladění již zvládám!

Moc děkuju všem, kdo mi pomáhali a hlavně Jendovi - jehož považuji za řešitele problému.