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í
×
včera 22:00 | Komunita

Portál Stack Overflow po roce opět vyzpovídal své uživatele, jedná se především o vývojáře softwaru, a zveřejnil (podcast) detailní výsledky průzkumu. Průzkumu se letos zúčastnilo více než 64 tisíc vývojářů. Jejich nejmilovanější platformou je linuxový desktop. Ten je také druhou nejpoužívanější platformou vývojářů.

Ladislav Hagara | Komentářů: 0
24.3. 11:55 | Komunita

Vývojový tým OpenSSL ve spolupráci s iniciativou Core Infrastructure konsorcia Linux Foundation spustil proces přelicencování této kryptografické knihovny ze současné licence na licenci Apache Licence v 2.0 (ASLv2). Nová licence usnadní začleňování OpenSSL do dalších svobodných a open source projektů. Všichni dosavadní vývojáři OpenSSL (Authors) obdrží v následujících dnech email s prosbou o souhlas se změnou licence.

Ladislav Hagara | Komentářů: 7
24.3. 01:11 | Komunita

Před třemi týdny Mozilla.cz představila projekt Photon, jehož cílem je návrh a implementace nového vzhledu Firefoxu. Včera zveřejnila první náhled vzhledu Photon. Práce na projektu Photon jsou rozděleny do pěti týmů, které celkem čítají 19 lidí. Zaměřují se na zlepšení prvního spuštění Firefoxu a zaujetí nových uživatelů, celkovou úpravu vzhledu, zlepšení animací, zrychlení odezvy uživatelského rozhraní a také upravení nabídek. Vývoj lze sledovat v Bugzille.

Ladislav Hagara | Komentářů: 38
23.3. 20:00 | Komunita

OneDrive pro firmy je již ve webových prohlížečích na Linuxu stejně rychlý jako na Windows. Microsoft opravil chybu z listopadu loňského roku. OneDrive pro firmy běžel na Linuxu mnohem pomaleji než na Windows. V popisu chyby bylo uvedeno, že stačilo v prohlížeči na Linuxu nastavit v user-agentu Windows a vše se zrychlilo. Odpovědí Microsoftu bylo (Internet Archive: Wayback Machine), že Linux není podporován. Po bouřlivých diskusích na redditu i Hacker News byla chyba nalezena a opravena.

Ladislav Hagara | Komentářů: 6
23.3. 19:00 | Zajímavý projekt

Byla vyhlášena soutěž Hackaday Prize 2017. Soutěž je určena vývojářům open source hardwaru. Pro výherce je připraveno celkově 250 tisíc dolarů. Každý ze 120 finalistů získá tisíc dolarů. Nejlepší pak navíc 50, 30, 20, 15, 10 a 5 tisíc dolarů. Jedná se již o čtvrtý ročník soutěže. V roce 2014 zvítězil projekt globální sítě open source pozemních satelitních stanic SatNOGS. V roce 2015 zvítězil open source systém pro řízení elektrických invalidních vozíků pohybem očí Eyedriveomatic. V roce 2016 zvítězil modulární robot Dtto.

Ladislav Hagara | Komentářů: 0
23.3. 15:00 | Bezpečnostní upozornění

Byla vydána Samba ve verzích 4.6.1, 4.5.7 a 4.4.12. Řešen je bezpečnostní problém CVE-2017-2619. Pomocí symbolických odkazů a souběhu (symlink race) lze "teoreticky" získat přístup k souborům, které nejsou sdíleny. Linuxové distribuce jsou postupně aktualizovány (Debian).

Ladislav Hagara | Komentářů: 0
23.3. 07:43 | Nová verze

Na Steamu se objevil port hry Arma: Cold War Assault (Operation Flashpoint) pro Mac a Linux. … více »

creon | Komentářů: 30
23.3. 05:55 | Nová verze

Po 18 měsících od vydání verze 8.0 byla vydána verze 9.0 open source alternativy GitHubu, tj. softwarového nástroje s webovým rozhraním umožňujícího spolupráci na zdrojových kódech, GitLab. Představení nových vlastností v příspěvku na blogu a na YouTube.

Ladislav Hagara | Komentářů: 0
23.3. 03:33 | Komunita

Platnost posledního patentu souvisejícího s Dolby Digital (AC-3) vypršela. Po MP3 se tak do Fedory oficiálně dostane také kodek AC-3.

Ladislav Hagara | Komentářů: 5
23.3. 00:44 | Komunita

Feral Interactive, společnost zabývající se vydáváním počítačových her pro operační systémy macOS a Linux, nabízí své hry na Steamu vývojářům open source 3D grafické knihovny Mesa zdarma. Podmínkou je minimálně 25 commitů za posledních 5 let. Stejnou nabídku dostali vývojáři knihovny Mesa v roce 2015 od Valve. O rok dříve dostali od Valve tuto nabídku vývojáři Debianu a Ubuntu.

Ladislav Hagara | Komentářů: 0
Jak se stavíte k trendu ztenčování přenosných zařízení (smartphony, notebooky)?
 (14%)
 (2%)
 (72%)
 (3%)
 (10%)
Celkem 932 hlasů
 Komentářů: 72, poslední 1.3. 11:16
    Rozcestník

    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: 643×

    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
    Nezapomeňte si příští víkend posunout časovače na svých bombách o hodinu dopředu!
    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
    
    Nezapomeňte si příští víkend posunout časovače na svých bombách o hodinu dopředu!
    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…
    Nezapomeňte si příští víkend posunout časovače na svých bombách o hodinu dopředu!
    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).
    Nezapomeňte si příští víkend posunout časovače na svých bombách o hodinu dopředu!
    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.
    Nezapomeňte si příští víkend posunout časovače na svých bombách o hodinu dopředu!
    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.
    Nezapomeňte si příští víkend posunout časovače na svých bombách o hodinu dopředu!
    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ý.
    Nezapomeňte si příští víkend posunout časovače na svých bombách o hodinu dopředu!
    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).
    Nezapomeňte si příští víkend posunout časovače na svých bombách o hodinu dopředu!
    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?
    Nezapomeňte si příští víkend posunout časovače na svých bombách o hodinu dopředu!
    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.