1) Zadání : Naprogramujte řešení 0/1 problému batohu pomocí dynamického programování a pomocí ořezávání - větví a hranic.
2) Vypracování : Pro řešení zadaného problému jsem jako vhodný programovací jazyk zvolil Borland C++ Builder 5. Zdrojový program i spustitelný soubor jsou přiloženy.
3) Rozbor řešení :
Ořezávání : Metoda ořezávání je velmi podobná metodě hrubé síly. Je založena na postupném prohledávání stavového prostoru, avšak některé větve dle zadaných kritérií ořízne. Tato metoda má několik částí. Jako první musíme vytvořit stavový strom, jehož uzly budou obsahovat dva ukazatele na potomky (listy budou ukazovat na NULL) , maximální možnou cenu (dále jen MMC) batohu a aktuální cenu batohu v dané větvi. Ukazatel na levého potomka nám značí, že daná věc (dle hloubky stromu) do batohu patří. Pravým ukazatelem naopak věc z batohu vyndáváme. V druhém bodě algoritmu naplníme všechny uzly ve stromu MMC. MMC můžeme určit různými algoritmy. Já jsem si dle zkušeností z první úlohy vybral heuristiku dle poměru cena/váha. V případě, že jdeme ve stromu do leva, můžeme MMC jen zkopírovat z otce do syna, ale při průchodu doprava je nutné MMC vypočítat dle námi zvoleného algoritmu.Ve třetí části přijde na řadu vlastní ořezávání stromu. Zatímco MMC jsme plnili od kořene k listům, tak aktuální cenu, potažmo ořezávat, budeme od listů ke kořenu. Pokud je aktuální cena pravé větve uzlu větší než MMC, tak můžeme levou větev uzlu odříznout, aniž bychom ji museli předem procházet a počítat její aktuální cenu.
V případě, že na počátku postavíme plný binární strom, tedy o 2^(počet věcí v batohu) uzlech bude tento algoritmus velmi paměťově náročný (pro 25 věcí, za předpokladu, že ukazatele a INTEGER jsou dvou bytové, je datová velikost stromu 2^(25)*4*2=256MB).
Dynamické programování : Tento algoritmus využívá již známých výsledků cen, které si zapamatovává v dvourozměrném poli o rozměrech (n+1)(k+1), kde n je počet věcí a k maximální kapacita batohu. Takto postavený algoritmus, ale dokáže zjistit jen cenu batohu, avšak už nám nic neřekne o tom, jaké věci v batohu máme, nebo-li jaké věci máme do batohu dát, abychom dosáhli této ceny. Algoritmus by šel upravit tak, že by přibyli další pomocná pole pro zapamatování si řešení.
4) Naměřené hodnoty :
Ořezávání : Testování této metody bylo praktikováno pouze pro počty věcí v batohu do 22. Nad tento počet již byla časová náročnost algoritmu neúnosná. Pro srovnání dávám do tabulky ještě čas hrubé síly.
|
Počet věcí |
4 |
10 |
15 |
20 |
22 |
25 |
|
Hrubá síla (s) |
0 |
0,6 |
1,97 |
57,40 |
247,93 |
2232,33 |
|
Ořezávání (s) |
0 |
0,33 |
9,89 |
404,53 |
2053,28 |
56850 |
|
Dynamicky (s) |
0 |
0,06 |
0,17 |
0,32 |
0,38 |
0,61 |
Pro batoh s 25-ti věcmi je čas spočten lineární aproximací. Byl změřen pouze čas trvání první instance 1187s a vynásoben 50-ti. Délka trvání byla díky velké paměťové náročnosti algoritmu deformována, jelikož si systém Windows při nedostatku paměti začal vypomáhat swapováním na disk (256MB fyzické paměti, až 1,4GB SWAP na disku). Pro lepší přehled ještě uvedu trvání jednotlivých fází algoritmu pro 25 věcí:
Na skupině testovaných batohů došlo k několika odlišnostem oproti hrubé síle, což znamená, že kritéria pro ořezávání nejsou na 100% korektní (viz. tabulka počtu odlišností od hrubé síly níže).
|
Počet věcí |
4 |
10 |
15 |
20 |
22 |
|
Poměr c/v |
14 |
27 |
20 |
30 |
35 |
|
Ořezávání |
5 |
16 |
11 |
26 |
26 |
Dynamické programování : Jak je vidět z tabulky časů (viz. výše) je metoda dynamického programování velice rychlá a což je důležitější dává pro soubory se 4-25 věcmi stejné výsledky jako hrubá síla, tedy optimální.
5) Závěr :
Z naměřených výsledků je jasně patrné, že dynamické programování podává nejlepší výsledky za nejmenší čas a je tedy pro náš případ problému batohu skvělým algoritmem. Samozřejmě jen za předpokladu, že nám postačuje znát cenu batohu a nemusíme znát jeho kapacitu či řešení.
Ořezávání s generovaným úplným binárním stromem je naprosto nepoužitelné a naprosto zbytečné, jelikož je ještě pomalejší než hrubá síla. Avšak pokud bychom algoritmus upravili tak, že bychom ořezávali strom již při jeho tvorbě, dostali bychom výsledky mnohem přívětivější. Tento upravený algoritmus by mohl dosahovat zhruba 4 násobného zrychlení oproti hrubé síle, v závislosti na počtu věcí a především na váhové reprezentaci jednotlivých věcí v batohu. Rychlost by byla tím větší čím by dané věci v batohu měli větší váhu, blížící se ke kapacitě batohu.