Optimální algoritmus výpočtu

[slowthinker]

Terminologie:
Elementární balení: to je snad jasné, v našem zadání bal1 (1ks, 20kč/ks), bal2 (5ks, 18kč/ks) atd.
Nákup: libovolná lineární kombinace elementárních balení (koeficienty jsou celočíselně nezáporné). např. 15* bal1 + 1*bal3 + 3*bal4
Jestliže do lineární kombinace dosadíme počty kusů v baleních, získáme počet nakoupených kusů zboží.
Jestliže do lineární kombinace dosadíme ceny balení, získáme cenu nákupu.
Ideální nákup I(k): uvažujme množinu všech nákupů, kterým nakoupíme k zboží (resp. alespoň k zboží - to záleží na zadání). Ideální nákup je každý takový nákup, který dosahuje v rámci této množiny minimální cenu.

A jakým způsobem zjistíš že je nákup ideální. To je práve základní zadání úlohy.

Ideální nákup zjistím tak, že porovnám ceny všech nákupů (dosazováním do lineární kombinace - viz odstavec výše) uvedených v bodech 1] a 2] v mém prvním příspěvku.

[Reklama]

[Ondřej Vaniš]

Ano to jsi popsal naprosto přesně.
Ale jakým způsobem dokážeš vypočítat tuto rovnici?
a*bal1+b*bal2+c*bal3+d*bal4=PozadovanyPocet

Kromě dosazování za a,b,c,d a zjištování jestli se rovna pozadovanemu poctu jsem nenasel.
Nebo mi neco uniklo?

[slowthinker]

U nákupů typu 1] zjišťuji snadno, zda obsahují požadovaný počet.
U nákupů typu 2] to nemusím zjišťovat, protože to vím: Chci 51 ks zboží, a nákup I(3)+I(48) prostě obsahuje 51 kusů zboží. Včechny nákupy ve skupině 2] obsahují 51 ks zboží.

[Logik]

slowthinker: samozřejmě chtěnej počet kusů, je to jen jiná formulace problému batohu, tak sem se upsal.

Tak ještě jednou a polopaticky. Tys navrhnul algoritmus, kterej je závislej kvadraticky na počtu chtěnejch kusů. A pomocí kolika bitů zakóduješ že chceš n kusů? Já to umim do log(n) bitů.
Takže vstup velikosti v=log_2(n) poběží rychlostí n^2. Proto n=exp_2(v) a tedy výsledná rychlost pro vstup v bitů je exp_2(v)^2. Samozřejmě s nějakym tim očkem, by to bylo precizně :-)
Jinými slovy, přidáním jednoho bitu na vstupu se ti zvýší čas čtyřnásobně. To prostě není polynomiální složitost...

Složitost algoritmu se vždy udává vzhledem k velikosti vstupu, nikoli k užitým hodnotám. Takže i když vymyslíš algoritmus, kterej je polynomiální, ale na něčem jinym než na velikosti vstupu, tak to nic neříká o náležitosti do NP. Btw. vymýšlíme tady opravdu kolo, tomudle algoritmu se říká pseudopolynomiální, patří mezi takzvané dynamické programování a učí se o nich asi v každym v základním kursu složitosti a NP úplnosti a už tu padly i linky na preciznější formulace. Zkus pohledat po netu, je tam hafo online skript.

PS:
Je to rozdíl oproti např. úlohám na setřídění, kde je daná složitost nikoli VELIKOSTÍ tříděných čísel, ale jejich POČTEM (přesněji čas porovnání dvou čísel roste s logaritmem jejich hodnoty respektive lineárně vzhledem k velikosti vstupu, takže tam je opravdu "nejdražší" samotné třídění: na porovnání dvou čísel lze hledět jako na atomickou operaci, protože je dražší zdvojnásobit počet čísel než zdvojnásobit možnou velikost tříděných čísel).

[Martin Prokš]

Hmm,

z prvniho nebo druheho semestru matematiky na CVUT FSI: hledani extremu funkce: parcialni derivace rovny nule -> pro dane zadani soustava linearnich rovnic stupne (od boku, nepocitam to, takze se mozna o jednicku spletu) n-1 stupne (n = pocet baleni). V tomto pripade to povede sice na necele reseni, ktere bude treba zaokrouhlit. Nic sloziteho. Symbolicky vyresit a je to. Smitec.

Matematicky ukol na ctvrt hodky pro studenta CVUT FSI ktery ma zkousku z matiky z parcialek za 3. Snazte se, preci jste lepsi ;-)

[Reklama]

[Karel]

Hmm, jasny je tam jaksi jen jedna omezujici podminka priste se radeji budu koukat pozorneji

A to nestačí? Podle mě to je lineární programování. Minimalizuje se cena, neznámé jsou počty jednotlivých balení a omezující rovnice je daná součtem kusů = vyžádaný počet kusů. Viz http://cs.wikipedia.org/wiki/Lineární_programování (matice A nemusí být čtvercová).
Pro lin. programování existují P algoritmy, otázka je se vyplatí je implementovat. Problém je, že lin. prog. řeší úlohu v reálných číslech, takže výsledky je třeba upravit (zaokrouhlit nqa celá balení), což zavádí určitou chybu. Řešení pomocí problému batohu by tuto chybu eliminovalo, ale za cenu NP algoritmu.

[Logik]

Přestaňte už konečně vymejšlet kolo. :-)
Lineární programování??? Parciální derivace???
Ufff. Tam vám jaksi kupodivu vždycky vyjde, že máte vzít 0.35467 kusů balení s nejnižší cenou za kus. Na to nemusim derivovat, abych todle určil, ani si dělat ty úžasný mentální tabulky na linprog.

Slowthinker postnul nejlepší řešení  (a pár lidí před ním odkaz na něj), nic lepšího se vymyslet nedá, je to prostě NP úplnej problém v trochu jinym ošacení.
Když už chcete nějaký přibližný řešení, tak se nabízí hladovej algoritmus, ale ten tady v podstatě taky zazněl (beru vždy nejlevnější balení, který se mi ještě vejde).

[Ghost]

Je to jen mirne upraveny problem batohu. Prepokladam, ze muzu pouzit treba dve baleni po 20ks, pokud neni opakovani mozne tak je to klasicky batoh.
Nalezeni vzdy optimalni reseni.
1 hruba sila
2. B&B
3. dynamicke programovani

U prvnich dvou jde jen o to napsat generovani unikatnich (aby se nebloudilo ve stavovem prostoru, tj. aby to byl strom ) posloupnosti. V pripade bez opakovani vkladani je to trivialni problem (kdyztak popisu). Druhy pripad je akorat rozsiren o orezavani - tj nebudu expandovat dalsi stavy, kdyz vim, ze budou vzdy horsi, nez nejlepsi dosud nalezene reseni. A dale nebudu expandovat stavy, ktere zarucene nevedou k reseni. Oboji jde napsat velice jednoduse.

Dynamicke programovani je rychlejsi (a taky asi narocnejsi na pochopeni). ale predpoklada jiste vlastnosti problemu - takove reseni je pak pseudopolynomialni a zalezi jen na velikosti problemu a dalsim parametru (treba cene).

[slowthinker]

Takže žádnou exponencionální náročnost nevidím, maximálně kubickou, pokud budou proměnné jak počet požadovaných kusů tak počet elementárních balení, a budeme předpokládat že rostou "stejně rychle".
Podle mě ale lze počet elementárních balení považovat za proměnnou veličinu pouze ve velmi speciálních případech. Rozhodně ne tehdy, pokud se musí nejprve nějaký obchodník rozhodnout, že nabídne k prodeji nové balení, a někdo je pak bude muset přidat ručně do systému. Ano tehdy, pokud budou balení a jejich ceny určovány automatizovaně - budou vypočteny třeba na základě cen na trhu, a to i pro velmi (neomezeně) velká balení.

Teď mi došlo, že tohle je nesmysl. Předpokládal jsem, že ve vnitřním cyklu je třeba počítat ceny I(48) a I(3) sečtením lineárních kombinací, a pak teprve je možné je sčítat. To ale není pravda: je jednodušší si ceny I(48) a I(3) pamatovat.
Takže se vždy jedná o kvadratickou náročnost: algoritmus je tvořen dvěma vnořenými cykly a ve vniřním cyklu se v zásadě jenom sečtou dvě čísla (např. ceny I(48) a I(3)) a porovnají se s dočasným minimem.

@Matyáš Novák:
K tvému polopatickému vysvětlení mám tři zásadní výhrady:

Složitost algoritmu se vždy udává vzhledem k velikosti vstupu, nikoli k užitým hodnotám.

1) Udávat ASYMPTOTICKOU složitost algoritmu v závislosti na velikosti čísel tvořících vstup by byl principiální nesmysl, protože v praxi mají hodnoty na vstupu vždy OMEZENOU velikost (ještě jsem neviděl program, který by byl zařízen na příjem neomezeně velkých čísel na vstupu).

2) Pokud by se takto měřila časová náročnost algoritmů, dala by se tvoje úvaha aplikovat na všechny algoritmy (včetně třídění). I obyčejný součet dvou čísel (tj. úloha s obecně uznanou konstantní náročností) by tedy podle tebe měl exponenciální náročnost, nebo  lineární, pokud uznáš bod 3) níže.

Jinými slovy, přidáním jednoho bitu na vstupu se ti zvýší čas čtyřnásobně.

3) Někde bude chyba. I když budu předpokládat stroj, který umí jenom bitové operace, zdvojnásobením počtu bitů se doba sčítání zdvojnásobí. Lineární závislost, nikoli exponencionální.

Je to rozdíl oproti např. úlohám na setřídění, kde je daná složitost nikoli VELIKOSTÍ tříděných čísel, ale jejich POČTEM

Ten rozdíl opravdu nevidím.
Uvědom si, jak jsou atomické operace u třídění a "mého algoritmu" podobné: u třídění se jedná o porovnání, u "mého algoritmu" o součet dvou čísel a pak porovnání. To je jedno a to samé.

[Logik]

Tvuj nick je přesnej, tak ještě jednou. :-) :-)

1) Udávat ASYMPTOTICKOU složitost algoritmu v závislosti na velikosti čísel tvořících vstup by byl principiální nesmysl...

Ale to právě děláš ty!!! Vždyť ty měříš složitost dle požadovaného počtu předmětů - čili podle velikosti jednoho čísla na vstupu, což je právě blbina (respektive není to blbina, ale takový algoritmus se nazývá nikoli polynomiální ale pseudopolinomiální).

Složitost algoritmu se prostě měří dle závislosti rychlosti (popř. spotřebované paměti) na velikosti (počtu bitů) vstupu. (Pokud ji chceš měřit podle něčeho jinýho, můžeš, ale pak nemá smysl se bavit např. o NP atd... - na spoustu NP problémů existují pseudopolynomiální algoritmy - v podstatě z definice NPúplnosti pro všechny NP úplné).

Pokud chceš Tedy měřit rychlost tvého algoritmu dle velikosti čísla udávajícího žádaný počet, musíš to dělat podle velikosti vstupu toho čísla. Ale tam je exponenciální závislost.
 

Někde bude chyba. I když budu předpokládat stroj, který umí jenom bitové operace, zdvojnásobením počtu bitů se doba sčítání zdvojnásobí. Lineární závislost, nikoli exponencionální.

Chci 16 kusů (tzn vstup čtyři bity 1000). Jelikož tvuj algoritmus má závislost kvadratickou na požadovaný počet kusů, rychlost bude o(16^2)
Chci 32 kusů (tzn. vstup pět bitů 10000). Rychlost bude o(32^2) = 4*o(16^2). Tzn čtyřikrát větší.

Vůbec nejde o rychlost sčítání ale o to, že rychlost je kvadratický vzledem k něčemu, co jde na vstupu logaritmicky kódovat a tedy exponenciální k velikosti vstupu.

Uvědom si, jak jsou atomické operace u třídění a "mého algoritmu" podobné: u třídění se jedná o porovnání, u "mého algoritmu" o součet dvou čísel a pak porovnání. To je jedno a to samé.

* Znova - u třídění NEZÁVISÍ na tom, jak jsou tříděná čísla velká, závisí na tom, KOLIK jich na vstupu je. Zdvojnásobením počtu čísel se zdvojnásobí velikost vstupu (a 2*log(2) zpomalí výpočet).
* U tvého algoritmu závisí počet kroků na VELIKOSTI čísla, nikoli na jejich POČTU. Zdvojnásobení čísla se ale vstup prodlouží pouze o jeden bit. Tzn. jde o závislost na něčem jiném než na velikosti vstupu.
(že jsou na vstupu pak ještě data udávající počty ceny různě velkých balení je irelevantní - s jejich větším počtem rychlost poroste max lineárně, takže je můžeme zanedbat (stejně jako u třídění velikost tříděných čísel), jediné co hraje roli je požadovaný počet kusů).

Vůbec tady nejde o složitost porovnání či sčítání, ty mají lineární složitost. Jde o to, jak ovlivní nárůst délky vstupu počet operací. Ta je u třídění daná jako nlog(n), kde n je počet tříděných prvků a u tvého algoritmu exp(n)^2, kde n je počet bitů, kterým je zapsán
chtěný počet kusů.

[petr]

Ufff. Tam vám jaksi kupodivu vždycky vyjde, že máte vzít 0.35467 kusů balení s nejnižší cenou za kus. Na to nemusim derivovat, abych todle určil, ani si dělat ty úžasný mentální tabulky na linprog.

Lineární programováni by opravdu šlo použít(ILP - integer linear programing) a vypadli by správné výsledky. Jediná nevýhoda je složitost, protože ILP úlohy jsou NP-úplné, a tak ILP řešení funguje v exponenciálním čase.

[slowthinker]

@Matyáš Novák
ano, můj nick je přesný. Lepší myslet pomalu než blbě jako někteří, které nechci jmenovat :p

Po mnohahodinovém úsilí mi došlo, co mi chceš sdělit. Veškeré naše nepochopení se zřejmě točí kolem tvé následující věty:

Složitost algoritmu se prostě měří dle závislosti rychlosti (popř. spotřebované paměti) na velikosti (počtu bitů) vstupu.

(místo "rychlosti" má být zřejmě "doby běhu")

To je podle mne špatný způsob měření. Vysvětlím na dvou příkladech:

_______________________________________________________
Příklad 1

Porovnejme následující algoritmy:
Algoritmus A)
Na vstup dostane přirozené číslo n, spočte jeho faktoriál

Algoritmus B)
Na vstup dostane n čísel, spočte jejich součin

Algoritmus C)
Na vstup dostane čísla 1, 2 ,3, 4 ...n , ověří vzestupnost posloupnosti, pak spočte jejich součin stejným postupem jako A)

Všechny tři algoritmy mají stejný charakter: jedná se o jeden for cyklus od 1 do n, uvnitř cyklu se pouze násobí (A a C jsou dokonce v podstatě totožné). Tvrdím proto, že časová náročnost všech algoritmů je stejná. A také tvrdím, že způsob určování časové náročnosti, který toto popírá, nemá z praktického hlediska žádný význam (dále budu zkráceně říkat "je špatný")

Tvůj způsob určování časové náročnosti (tj. délka běhu programu striktně vztažená k bitové délce vstupu) je tedy špatný.
Je to způsobeno tím, že vstupy algoritmů A), B) a C) mají jistou charakteristiku (zcela nezávislou na bitové délce vstupu), a tou je "n". Toto "n" (a NIKOLI bitová dělka vstupu) je právě tou charakteristikou, která určuje smrštěni-natažení běhu programu a ovlivňuje dobu jeho běhu.
_____________________________________________________________
Příklad 2

Uvažujme algoritmus, který na vstupu dostane dvě čísla v daném formátu (dejme tomu word), a na výstupu odevzdá jejich součet. (algoritmus nedokáže přijímat a sčítat libovolně velká čísla)
Jak určíš časovou náročnost dle tvé definice? Ty říkáš, že je to exponenciální  náročnost (odpověď #33, 2. odstavec), což je samo o sobě dosti překvapivý závěr. Jenomže zapomínáš, že délka vstupu tohoto algoritmu je ve skutečnosti neměnná, takže nelze uvažovat ani žádnou asymptotickou funkci, ani určovat časovou náročnost.

[slowthinker]

@Matyáš Novák, pokrač.
Musím přiznat, že o teorii algoritmů v podstatě nic nevím, a začal jsem pátrat, odkud bereš své tvrzení, že časová náročnost se musí udávat v závislosti na bitové délce vstupu.

Vzal jsem do ruky knihu L. Kučera, kombinatorické algoritmy, kde jsem se na str. 37 dočetl:
"Budeme říkat, že počítač ... pracuje v čase f(n), jestliže f je taková funkce, že každá přípustná vstupní data velikosti n zpracuje v čase nejvýše f(n)"

To odpovídá tvému určování časové náročnosti. Ale pak jsem si přečetl, co autor považuje za "vstupní data velikosti n":
"pro každá přípustná vstupní data určíme číslo, které budeme nazývat velikostí vstupních dat. Jeho volba závisí na druhu objektu, které data popisují. (příklady) ... za velikost matice řádu nxn se obvykle považuje číslo n (i když je třeba zadat n^2 čísel)"

Takže "velikostí vstupu" se nemyslí "bitová délka vstupu". A to je patrně ta chyba, kterou ve svých úvahách děláš.

Závěr: Možná, že s tvou definicí časové náročnosti některé teorie pracují. Nemá ale téměř žádný praktický význam.

[andrej]

Zlozitost moze udavat hocico podla toho, co meriame. Ak robime HW design, zaujima nas napr. priestorova zlozitost (pocet hradiel), ak implementujeme algoritmus, zaujima nas cas a pamat. Napr. mame graf o N vrcholoch a v akom case nieco vieme? (cas f(N), napr N^3) Takze v tomto pripade ziadne bity.

K problemu batoha existuju aproximacne algoritmy, ktore ale nedaju vzdy optimalny vysledok, ale da sa dokazat o co bude (najviac) horsi oproti optimu. Ake su, to to tu uz niekto spominal.

Ak mas malo tych mnozstiev, pusti na to backtracking a je .

[slowthinker]

@andrej: Reaguješ trochu z rychlíku.
Mluvíme o časové složitosti. Dohadujeme se o tom, v závislosti na čem časovou složitost měřit, tj. jaké hodnoty jsou možné/smysluplné jako x-ová složka f(N) .