abclinuxu.cz AbcLinuxu.cz itbiz.cz ITBiz.cz HDmag.cz HDmag.cz abcprace.cz AbcPráce.cz
AbcLinuxu hledá autory!
Inzerujte na AbcPráce.cz od 950 Kč
Rozšířené hledání
×
dnes 17:25 | IT novinky

Do prodeje (Farnell) se dostal jednodeskový počítač Tinker Board (unboxing). Jedná se o konkurenci Raspberry Pi 3 od společnosti Asus. Porovnání (jpg) těchto počítačů například na CNXSoft. Cena Tinker Boardu je 55 £.

Ladislav Hagara | Komentářů: 0
dnes 14:44 | Zajímavý projekt

Byla zveřejněna pravidla hackerské soutěže Pwn2Own 2017, jež proběhne od 15. do 17. března v rámci bezpečnostní konference CanSecWes ve Vancouveru. Soutěžit se bude o více než milion dolarů v pěti kategoriích. Letos se bude útočit i na Ubuntu. Jedná se již o 10. ročník této soutěže.

Ladislav Hagara | Komentářů: 1
dnes 13:33 | Nová verze

Po sedmi měsících vývoje od vydání verze 5.7 byla vydána verze 5.8 (YouTube) toolkitu Qt. Z novinek lze zmínit například Qt Lite pro vestavěná zařízení. Nově jsou plně podporovány moduly Qt Wayland Compositor (YouTube) a Qt SCXML (YouTube). Současně byla vydána verze 4.2.1 integrovaného vývojového prostředí (IDE) Qt Creator.

Ladislav Hagara | Komentářů: 0
dnes 11:52 | Pozvánky

Lednový Prague Containers Meetup se koná ve čtvrtek 26. ledna 2017 od 18:00 v Apiary, Pernerova 49, Praha 8. Přijďte se podívat na přednášky o Enterprise Kubernetes a Jenkins as a code.

little-drunk-jesus | Komentářů: 0
dnes 11:40 | Pozvánky

Program letošního ročníku konference Prague PostgreSQL Developer Days, která se koná již 15. a 16. února 2017 na ČVUT FIT, Thákurova 9, Praha 6, byl dnes zveřejněn. Najdete ho na stránkách konference včetně anotací přednášek a školení. Registrace na konferenci bude otevřena zítra (24. ledna) v brzkých odpoledních hodinách.

TomasVondra | Komentářů: 0
včera 02:20 | Zajímavý článek

David Revoy, autor open source webového komiksu Pepper&Carrot nebo portrétu GNU/Linuxu, upozorňuje na svém blogu, že nový Inkscape 0.92 rozbíjí dokumenty vytvořené v předchozích verzích Inkscape. Problém by měl být vyřešen v Inkscape 0.92.2 [reddit].

Ladislav Hagara | Komentářů: 0
včera 02:02 | Komunita

Øyvind Kolås, hlavní vývojář grafických knihoven GEGL a babl, které využívá grafický program GIMP, žádá o podporu na Patreonu. Díky ní bude moci pracovat na vývoji na plný úvazek. Milník 1000 $, který by stačil na holé přežití, se již téměř podařilo vybrat, dalším cílem je dosažení 2500 $, které mu umožní běžně fungovat ve společnosti.

xkomczax | Komentářů: 12
21.1. 23:54 | Pozvánky

DevConf.cz 2017, již devátý ročník jedné z největších akcí zaměřených na Linux a open source ve střední Evropě, proběhne od pátku 27. ledna do neděle 29. ledna v prostorách Fakulty informačních technologií Vysokého učení technického v Brně. Na programu je celá řada zajímavých přednášek a workshopů. Letos je povinná registrace.

Ladislav Hagara | Komentářů: 0
21.1. 22:11 | Nová verze

Byla vydána verze 1.0.0 emulátoru terminálu Terminology postaveného nad EFL (Enlightenment Foundation Libraries). Přehled novinek v poznámkách k vydání.

Ladislav Hagara | Komentářů: 0
20.1. 17:00 | Nová verze

Byl vydán Docker 1.13. Přehled novinek na YouTube a v poznámkách k vydání na GitHubu. Docker umožňuje běh aplikací v softwarových kontejnerech (Wikipedia).

Ladislav Hagara | Komentářů: 7
Jak se stavíte k trendu ztenčování přenosných zařízení (smartphony, notebooky)?
 (11%)
 (2%)
 (73%)
 (3%)
 (10%)
Celkem 377 hlasů
 Komentářů: 29, poslední dnes 18:00
Rozcestník
Reklama

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

13.7.2015 15:00 camel1cz | skóre: 23
Algoritmus optimálního výběru
Přečteno: 640×

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.


Řešení dotazu:


Odpovědi

Jendа avatar 13.7.2015 15:06 Jendа | skóre: 73 | blog: Výlevníček | JO70FB
Rozbalit Rozbalit vše Re: Algoritmus optimálního výběru
Pustil bych na to glpsol.

Problémy:
  • není to v PHP
  • možná to bude mít exponenciální časovou složitost
„To jsem nedávno zjistil, že naše televize jde ovládat po síti. Docela mě to překvapilo.“ „Jo? A kdo vám ji ovládal?“
13.7.2015 16:11 Radek Isa | skóre: 11
Rozbalit Rozbalit vše Re: Algoritmus optimálního výběru
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í.
13.7.2015 16:18 camel1cz | skóre: 23
Rozbalit Rozbalit vše Re: Algoritmus optimálního výběru
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
13.7.2015 16:40 TTTTTTTT
Rozbalit Rozbalit vše Re: Algoritmus optimálního výběru
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ů.
13.7.2015 16:54 camel1cz | skóre: 23
Rozbalit Rozbalit vše Re: Algoritmus optimálního výběru
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а avatar 13.7.2015 16:43 Jendа | skóre: 73 | blog: Výlevníček | JO70FB
Rozbalit Rozbalit vše Re: Algoritmus optimálního výběru
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
„To jsem nedávno zjistil, že naše televize jde ovládat po síti. Docela mě to překvapilo.“ „Jo? A kdo vám ji ovládal?“
Jendа avatar 13.7.2015 16:38 Jendа | skóre: 73 | blog: Výlevníček | JO70FB
Rozbalit Rozbalit vše Re: Algoritmus optimálního výběru
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…
„To jsem nedávno zjistil, že naše televize jde ovládat po síti. Docela mě to překvapilo.“ „Jo? A kdo vám ji ovládal?“
18.7.2015 11:51 David
Rozbalit Rozbalit vše Re: Algoritmus optimálního výběru
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.
13.7.2015 20:06 Radek Miček | skóre: 23 | blog: radekm_blog
Rozbalit Rozbalit vše Re: Algoritmus optimálního výběru
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.
13.7.2015 21:29 TTTTTTTT
Rozbalit Rozbalit vše Re: Algoritmus optimálního výběru
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.
13.7.2015 21:47 Radek Miček | skóre: 23 | blog: radekm_blog
Rozbalit Rozbalit vše Re: Algoritmus optimálního výběru
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
13.7.2015 21:48 Radek Miček | skóre: 23 | blog: radekm_blog
Rozbalit Rozbalit vše Re: Algoritmus optimálního výběru
Na konci funkce musíte vrátit m, to jsem zapomněl.
13.7.2015 22:04 Radek Miček | skóre: 23 | blog: radekm_blog
Rozbalit Rozbalit vše Re: Algoritmus optimálního výběru
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.
13.7.2015 23:58 TTT
Rozbalit Rozbalit vše Re: Algoritmus optimálního výběru
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í.
13.7.2015 22:20 Radek Miček | skóre: 23 | blog: radekm_blog
Rozbalit Rozbalit vše Re: Algoritmus optimálního výběru
Pokud máte hodně kamenů a nehledáte optimální řešení, můžete použít lineární programování.
Jendа avatar 13.7.2015 22:39 Jendа | skóre: 73 | blog: Výlevníček | JO70FB
Rozbalit Rozbalit vše Re: Algoritmus optimálního výběru
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).
„To jsem nedávno zjistil, že naše televize jde ovládat po síti. Docela mě to překvapilo.“ „Jo? A kdo vám ji ovládal?“
13.7.2015 22:47 Radek Miček | skóre: 23 | blog: radekm_blog
Rozbalit Rozbalit vše Re: Algoritmus optimálního výběru
Lze zkusit php-simplex, ten je v PHP.
14.7.2015 10:41 camel1cz | skóre: 23
Rozbalit Rozbalit vše Re: Algoritmus optimálního výběru
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?
14.7.2015 11:12 Radek Miček | skóre: 23 | blog: radekm_blog
Rozbalit Rozbalit vše Re: Algoritmus optimálního výběru
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а avatar 14.7.2015 13:03 Jendа | skóre: 73 | blog: Výlevníček | JO70FB
Rozbalit Rozbalit vše Re: Algoritmus optimálního výběru
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.
„To jsem nedávno zjistil, že naše televize jde ovládat po síti. Docela mě to překvapilo.“ „Jo? A kdo vám ji ovládal?“
14.7.2015 13:34 Radek Miček | skóre: 23 | blog: radekm_blog
Rozbalit Rozbalit vše Re: Algoritmus optimálního výběru
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.
14.7.2015 14:57 TTTTTTTT
Rozbalit Rozbalit vše Re: Algoritmus optimálního výběru
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а avatar 14.7.2015 15:34 Jendа | skóre: 73 | blog: Výlevníček | JO70FB
Rozbalit Rozbalit vše Re: Algoritmus optimálního výběru
(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.
„To jsem nedávno zjistil, že naše televize jde ovládat po síti. Docela mě to překvapilo.“ „Jo? A kdo vám ji ovládal?“
14.7.2015 16:33 TTTTTTTT
Rozbalit Rozbalit vše Re: Algoritmus optimálního výběru
Hm, mě to kdysi možná i šlo, ale zdá se, že ty časy jsou už ty tam. Máš pravdu.
Jendа avatar 14.7.2015 15:36 Jendа | skóre: 73 | blog: Výlevníček | JO70FB
Rozbalit Rozbalit vše Re: Algoritmus optimálního výběru
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ý.
„To jsem nedávno zjistil, že naše televize jde ovládat po síti. Docela mě to překvapilo.“ „Jo? A kdo vám ji ovládal?“
14.7.2015 21:17 camel1cz | skóre: 23
Rozbalit Rozbalit vše Re: Algoritmus optimálního výběru
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ě?
Řešení 1× (camel1cz (tazatel))
14.7.2015 22:02 Radek Miček | skóre: 23 | blog: radekm_blog
Rozbalit Rozbalit vše Re: Algoritmus optimálního výběru
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.
15.7.2015 01:10 camel1cz | skóre: 23
Rozbalit Rozbalit vše Re: Algoritmus optimálního výběru
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 :)
Řešení 1× (camel1cz (tazatel))
Jendа avatar 14.7.2015 22:16 Jendа | skóre: 73 | blog: Výlevníček | JO70FB
Rozbalit Rozbalit vše Re: Algoritmus optimálního výběru
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).
„To jsem nedávno zjistil, že naše televize jde ovládat po síti. Docela mě to překvapilo.“ „Jo? A kdo vám ji ovládal?“
14.7.2015 22:28 Radek Miček | skóre: 23 | blog: radekm_blog
Rozbalit Rozbalit vše Re: Algoritmus optimálního výběru
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а avatar 14.7.2015 22:32 Jendа | skóre: 73 | blog: Výlevníček | JO70FB
Rozbalit Rozbalit vše Re: Algoritmus optimálního výběru
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?
„To jsem nedávno zjistil, že naše televize jde ovládat po síti. Docela mě to překvapilo.“ „Jo? A kdo vám ji ovládal?“
15.7.2015 01:06 camel1cz | skóre: 23
Rozbalit Rozbalit vše Re: Algoritmus optimálního výběru
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.

Založit nové vláknoNahoru

Tiskni Sdílej: Linkuj Jaggni to Vybrali.sme.sk Google Del.icio.us Facebook

ISSN 1214-1267   www.czech-server.cz
© 1999-2015 Nitemedia s. r. o. Všechna práva vyhrazena.