Optimální algoritmus výpočtu

[Ghost]

Jiste, jenze pokud si nevi rady se zaklady, tak je pro nej lehci na pochopeni urcite B&B. Reseni, ktere jsem tady napsal, se da napsat odhadem do max 50 radku v cemkoliv.

Jsou to jen dva vnorene cykly + pouziti zasobniku (pripadne rekurzivni volani).

Abych priznal barvu, metodu DP jsem uz dlouho nepouzil, takze bych ji z hlavy ted nejspis taky nedal. Naposledy kdysi davno prave pro batoh

[Reklama]

[Logik]

Právě že to dynamický programování je i zdaleka nejjednodušší algoritmus na napsání. Odhadem na 10 řádek v čemkoli (no dobře, assembler možná dvacet). nehledejte problém tam, kde neni.

Kód: [Vybrat]

Inicializuj mincena[1..n] na nekonečno.
pro i z 1 ... n
 pokud existuje balení o i prvcích: mincena[i] = cena i-prvkového balení
 pro j z 1 ... i/2
    pokud mincena[j]+mincena[i-j] < mincena[i]: mincena[i] = mincena[j] + mincena[i-j]

That's all folks. Tádydádydádydááá.... :-)

[Ghost]

Ok, rikam, dlouho jsem nepouzil.
Lehci na pochopeni pro neznale mi porad prijde B&B - pravda, jen se musi vymyslet dobre generovani konfiguraci, aby se neduplikovaly ...

Jen doplnim k DP co si jeste pamatuju:
1. chybi zminka o trivialnim reseni, bez ktereho se nehnes (vim, jedno prirazeni
2. chybi rekonstrukce toho, co mas dat do kosiku, ted mas jen nejlepsi cenu

[Logik]

Nebuď dogmatik. To přiřazení tam je - akorát v jiný formě.
Je jím první řádek cyklu. Schválně jsem čekal, jestli se někdo chytne :-)
Klasický dynamický programování jede "po prvcích" - ale já jedu po "počtech".
Po prvcích by šlo taky - pak bych musel s každým prvekm vytvořit
všechny možné kombinace s dosud existujícími kombinacemi a nebylo by to tak elegantní.


A rekonstrukci košíku jsem sem nedal úmyslně - důležitý je pochopit myšlenku a ta se snadnějc pochopí z tohodle, a kdo to pochopí, ten si to snadno dopíše....

---

Jinak ono dynamický programování je v podstatě totéž, co B&B, akorát prohledává stavovej prostor v jinym pořadí.
Mů invariant je: než sestrojím stav s počtem prvků X, sestrojím všechny stavy s počtem prvků menším než X.
Tvuj invariant je: než v dané konfigurac košíku na Y tém místě v košíku vyzkouším prvek X, vyzkouším na tom místě všechny prvky menší než X a větší rovny než prvek na místě Y-1.

Že by ten Tvůj invariant byl jednodušší se mi moc nezdá.

Důkaz "dynamického" algoritmu je jednoduchá indukce dle ceny:
- Je-li košík N minimálním (má nejmenší možnou cenu) pro počet prvků n, pak jakékoli dva košíky A a B, pro které platí A+B=N (sesypání košíků) jsou minimální.
Sporem: není-li tomu tak, pak BÚNO existuje stav minimální košík A' a tedy i cena N' = A' + B je menší než N, což je spor.
- Pro nula prvků je nejlevnější prázdný košík.
- Vyřešil-li jsem stavy 0..n-1, pak každý minimální košík pro n je kombinací dvou minimálních košíků pro 1..n, nebo se sestává z jednoho balení. (triviální důsledek předchozího lematu)

V případě B&B to imho takhle elegantně nepůjde.

[slowthinker]

- Pro nula prvků je nejlevnější prázdný košík.

Tohle tvrzení k důkazu nijak nepřispívá, ze dvou prázdných košíků stejně nic nesestavíš. S tou indukcí bych na tvé místě začal od jedničky... 

Smiřte se s tím, že problém baťohu je NP úplnej a jde vyřešit pseudopolynomiálně

Předpokládám, že tím chceš říct, že totéž platí i o úloze probírané v tomto vlákně: no s tím se teda nesmíříme 
Můj algoritmus je podle "tvé" definice časové náročnosti lineární:
Na vstupu je požadovaný počet kusů zboží n (fixní délka vstupu) a atomická balení (neomezená délka vstupu). Takže ta část algoritmu, která k sobě skládá dvojice nákupů, je časově omezená maximálním n, a doba běhu závisí lineárně na délce vstupu (kvůli zjišťování, jestli lze nákup sestavit z jediného atomického balení - tj. nákup typu 1] v popisu algoritmu)
(Edit: A podle "mé" definice (která zatím neexistuje) je algoritmus kvadratický.)

Todle je vcelku hezká definice - ake už v příkladu 3 narážíš na problém

Ještě se k tomu zkusím vrátit, nemám na to teď čas.

[Reklama]

[ghost]

uff, tak tvuj algoritmus jsem teda nijak nekoumal, ale tvrdit, ze to jde linearne je odvaha ...
jedna se o problem batohu a ten je zkratka NP-uplny, takze nejlepsi (optimalni) reseni nemas sanci najit v polynomialnim case - leda v pseudo a to za pomoci DP.

Ber to jako hotovou vec, ptz optimalni reseni muze byt v kteremkoliv stavu. V pripade 0/1 batohu mas takovych reseni 2^<celkovy_pocet_veci> - jak vidis, tak zavislost je exponencialni, stejne tak v tomto pripade, navic nemas omezenu kapacitu kosiku - jen potrebujes co nejlevneji koupit urcity pocet kusu

[jaromír]

Nevím v čem je dynamické programování lepší proti mému programu, který projde podle stromové struktury pouze jednou jedinkrát existující možnosti, které vyhovují zadání. To znamená, že vůbec negeneruje možnosti, které nesplňují zadaní a také znovu nevytváří kombinace, které byly už jednou vytvořeny. A také navíc začíná od cenově výhodnějších kombinací, takže vždy přijde na nejvýhodnější kombinaci v několika prvních cyklech. Pak zbývající čas už jenom ověřuje, zda neexistuje nějaká lepší.

[ghost]

Nevím v čem je dynamické programování lepší proti mému programu, který projde podle stromové struktury pouze jednou jedinkrát existující možnosti, které vyhovují zadání. To znamená, že vůbec negeneruje možnosti, které nesplňují zadaní a také znovu nevytváří kombinace, které byly už jednou vytvořeny. A také navíc začíná od cenově výhodnějších kombinací, takže vždy přijde na nejvýhodnější kombinaci v několika prvních cyklech. Pak zbývající čas už jenom ověřuje, zda neexistuje nějaká lepší.

DP muze byt pro nektera zadani o dost rychlejsi, nez B&B. Co se tyka stromove struktury jak popisuje. Tak asi podobne reseni jsem poslal i ja. Akorat zacinam od trivialniho - tj. prazdneho kosiku a pridavam veci. Zadny stav se mi nenavstivi 2x a stav, ktery neni resenim se uz dal neexpanduje.

Co se tyka vety: najdu nejvyhodnejsi reseni v nekolika cyklech ... to bych se ja osobne neopovazoval tvrdit. Ptz vse zavisi na tom jak generujes stavy prostor a take na konfiguraci baleni. Takze se ti klidne muze stat, ze to optimalni bude az uplne to posledni

[jaromír]

Vzhledem k tomu, že začínám kombinace tak, abych měl nejvíce balíčků nejlevnějších a jak postupně levné balíčky snižuji a tím přidávám dražší balíčky, ale stále tak, aby celkový počet položek byl stále rovný zadání (to znamená, že se mi tam neobjeví kombinace, která mi dá celkový počet položek jiný, než zadaný).
Tímto způsobem se mi nemůže stát, aby se nejvýhodnější sestava objevila na konci hledání, neboť by musela být kombinací těch nejdražších balíčků.

[ghost]

Vzhledem k tomu, že začínám kombinace tak, abych měl nejvíce balíčků nejlevnějších a jak postupně levné balíčky snižuji a tím přidávám dražší balíčky, ale stále tak, aby celkový počet položek byl stále rovný zadání (to znamená, že se mi tam neobjeví kombinace, která mi dá celkový počet položek jiný, než zadaný).
Tímto způsobem se mi nemůže stát, aby se nejvýhodnější sestava objevila na konci hledání, neboť by musela být kombinací těch nejdražších balíčků.

hm, zajimave, ale takto popsane reseni mi silne pripomina hladovy algoritmus - ktery u batohu nemusi byt optimalni ... sic nevim co si mam (resp. nevim jak provadis) predstavit pod dohledani lepsich

[jaromír]

Tady je řešení jak lineárního programu, které samozřejmě nenajde nejlepší řešení, pokud je v zadání podraz.

Tak i rekurzivního, které má vlastnosti jenž jsem popisoval.

[slowthinker]

uff, tak tvuj algoritmus jsem teda nijak nekoumal, ale tvrdit, ze to jde linearne je odvaha ...

Lineární není podle mne, ale podle definice časové náročnosti, kterou používá Matyáš Novák.
Podle mne je to řešení kvadratické, alespoň podle "intuitivní" definice časové náročnosti (jedná se o dva vnořené cykly od 1 do n, kde n je určeno vstupními hodnotami).

(viz tato debata pár stránek zpět)

Nevím v čem je dynamické programování lepší proti mému programu, který projde podle stromové struktury pouze jednou jedinkrát existující možnosti, které vyhovují zadání.

Jakmile procházíš strom, je časová náročnost exponenciální. Kvadratické řešení je lepší.

[jaromír]

Jakmile procházíš strom, je časová náročnost exponenciální. Kvadratické řešení je lepší.

Aha, ale to nevím jak bych naprogramoval.
Tohle je pro mne jednodušší, už z toho důvodu, že je obecné a funguje pro libovolný počet balíčků. Je fakt, že pro velký počet kusů, vzniká obrovské množství kombinací, které je časově náročné. V tomto příkladu (3 balíčky a 24 kusů) je to stále ještě rychlé.

Například pro 5 balíčků:
B:[[1,20],[5,18],[10,19],[50,17]]

a 1024 kusů přišel na řešení okamžitě, ale vlastní kontrola ještě trvala 8 sekund.

a při 2048 kusech sice také měl správné řešení ihned, počítal však ještě 101 sekund.

a při 4096 kusech našel správné řešení ihned, počítal však ještě 1360 sekund.

Podle mně by vůbec nemusel procházet všechny řešení. Stejně na to přijde okamžitě. Možná by stačilo ho po nějaké krátké době useknout a považovat nalezené řešení za správné.

[Logik]

slowthinker:Fixní élka vstupu u složitosti je nesmysl. Už třeba proto, že se bavíme o asymptotické složitosti, tedy o složitosti kdy délka vstupu se limitně blíží k nekonečnu. Takže buďto můžeš prohlásit n za konstantu, nebo mu povolit růst do nekonečna (to ale nejde s fixní délkou vstupu).
Ono pokud měříš složitost dle délky vstupu pro n zadané fixní délkou, tak samozřejmě nejdéle to vždy poběží, když n je maximální. A vstup je furt stejně dlouhý, takže vlastně měříš složitost algoritmu: "jaký je nejlevnější košík pro C", kde C je konstanta (2^délku n). Ale to je už trochu jinej algoritmus.
(např. proto, že neumí řešit všechny případy).

Seřazení dvaceti čísel variabilní délky má taky lineární složitost. (s délkou čísel roste jen lineárně) - a přesto má řazení složitost větší: n*log(n).

Tohle tvrzení k důkazu nijak nepřispívá, ze dvou prázdných košíků stejně nic nesestavíš. S tou indukcí bych na tvé místě začal od jedničky... 

Při indukci je vyžadováno, aby pro krok n byl vyřešen krok n-1. Takže mám dvě možnosti, buď vyřeším úplně triviální případ pro nulu (byť z nulového košíku nikdy další skládat nebudu), nebo pro jedničku, kdy je to složitější. Jsem línej člověk a tak radši vyřeším tu nulu. :-P.
PS: Jedička se pak vyřeší jako běžnej krok, holt se tam prostě půlka neuplatní, protože neexistuje žádná vhodná kombinace A a B, ale co mi po tom?

jaromír:
V čem je lepší?
Ty jen projdeš stromovou strukturu.... :-) Že je velikost té stromové struktury exponenciální (2^n vrcholů stromu)ty už jaksi nevadí.... Vždyť sám píšeš, že pro větší počty to bude pomalý.
Jestli chceš přesně vědět, v čem je dynamický programování lepší, tak třeba v tom, že pokud máš balení s jedním a dvěma kusama, obě za korunu kus, tak zatímco dynamické programování rozvine jen jedno řešení a u druhého zjistí, že není lepší a zahodí ho už hned jak vezme do ruky to dvoukusový balení, tak ty rozvíjíš obě možnosti a zjistíš, že jsou ekvivalentní teprve poté, co prohledáš celý podstrom.
Exaktnějc řečeno, tvoje řešení není pseudopolynomiální, zatímco dynamické programování ano.

Tímto způsobem se mi nemůže stát, aby se nejvýhodnější sestava objevila na konci hledání, neboť by musela být kombinací těch nejdražších balíčků.

Ach jo. Opravdu?
Chceš 1600 kusů
400 kusů celkem za 4000
1 kus za 10000000
+ hromada 300 - 399 kusových balení za cenu pod 3000.
Výsledná kombinace bude obsahovat 4x4 kusy, ale na tu přijdeš skoro až jako poslední.

Další věc je, že i když přijdeš na nejlepší kombinaci rychle, tak pokud jsou ceny hodně podobné, tak stejně zbytek stromu musíš projít hodně do hloubky, než přijdeš na to, že
ostatní kombinace jsou horší.

[Logik]

jaromir: Složitost se vždy řeší dle nejhoršího možného vstupu dané délky. Navíc program, který nenajde správné řešení vždy je na nic - jak můžeš vědět, že nalezené řešení je správné?
Stejnětak čas kdy se najde optimální řešení je nic neříkající údaj: jediný, co je směrodatný je čas, kdy algoritmus doběhne. Protože než doběhne, tak nevíš, jestli to optimum je opravdu optimum.