3. Problém batohu dynamickým programováním, metodou větví a hranic a heuristikou




Zadání:

Všechny Vaše existující programy pro 0/1 batoh upravte tak, aby poskytovaly pomocný výstup ve formátu:

ID počet kroků řešení výsledná cena
... ... ...



Řešení - větve a hranice:

Jedná se v podstatě o bruteforce metodu procházení stromu do hloubky s tím, že ořezáváme (neřešíme) podstromy, které nemohou vést k řešení. To testujeme podmínkou, zda maximální teoretická cena batohu kterou můžeme v dané konfiguraci dosáhnout může být lepší než doposavaď nalezené nejlepší řešení. Maximální teoretickou cenu spočítáme naplněním batohu na maximum s tím, že postupně bereme předměty seřazené podle poměru cena/váha a z posledního předmětu který se do batohu již nevejde připočteme poměrnou část ceny. Zárověň dále neprocházíme větve, ve kterých jsme již překročili nosnost batohu.
První nejlepší řešení nalezneme navštívením prvního koncového listu. Při dosažení každého dalšího listu otestujeme zda není nalezené řešení lepší a případně updatneme související proměnné.
Teoreticky je složitost stejná jako u metody hrubá síla, tedy 2^n, prakticky je díky optimalizacím daleko nižší.


Řešení - dynamické programování:

Spočteme maximální cenu naplněného batohu se zachováním jeho nosnosti. Na začátku budeme pracovat s nenaplněným batohem. Zeptáme se, jaká je cena batohu s nějakým vloženým předmětem a bez něho a vybereme si lepší variantu, a tím převedeme náš úkol na určení ceny batohu s počtem přemětů o jedna menším. Postupnou rekurzí dojdeme k řešení triviálních problémů - kapacita batohu je vyčerpána. Takto by měl algoritmus složitost opět 2^n. Pokud si však budeme stavy s opakovaným řešením pamatovat (ikdyž je postup k těmto stavům různý, mají tyto stavy vždy stejné řešení), zlepšíme složitost na n*(nosnost batohu). Pamět realizujeme dvojrozměrným polem s délkou N a výškou odpovídající nostnosti batohu. Pole bychom mohli zredukovat na dvousloupcové, ztratili bychom tím ovšem možnost zpětně zjistit, jaké předměty do batohu vložit.


Řešení - heuristika podle poměru cena/hmotnost s testem nejcennější věci:

Naše heuristika je založena na setřídění předmětů podle poměru cena/váha sestupně. Do batohu se pak snažíme vkládat prvky postupně z této posloupnosti. Řešení této heurestiky z úlohy 1 pak porovnáme s cenou nejdražšího předmětu a rozhodneme se pro výhodnější řešení.


Řešení - heuristika podle poměru cena/hmotnost s výběrem k-tic:

Pro každou k-tici se provede metoda hrubé síly. V našem případě jsme k zvolili experimentálně 4. Volné místo v batohu se dále pokusíme zaplnit podle již dříve řešené heurestiky. Parametr k ovliňuje výpočetní složitost a přesnost metody.


Porovnání:

V tabulce jsou pro porovnání uvedeny i výsledky z první úlohy. Počet prohledávaných instancí není průměr, ale odhadnuté číslo, které se průměru blíží.
Všechny metody (kromě bruteforce) vyřešili problém i pro největší počet věcí (40) pod 1 sekundu.

n Přibližný počet prohledávaných instancí
Bruteforce Heuristika Větve a hranice Dynamicky Heuristika s testem Heuristika s k-ticemi
4 136 14 40 25 17 24
10 20500 65 180 600 74 2210
15 983070 135 560 2600 149 20715
20 41943080 230 1250 5300 249 97320
22 184549420 275 1200 6500 296 161436
25 1677721650 350 1700 9000 374 316900
27 - 405 1900 11600 431 474606
30 - 495 2000 15000 524 823080
32 - 560 2100 18300 591 1151776
35 - 665 2700 22200 699 1833860
37 - 740 3000 26100 776 2445071
40 - 860 3300 - 899 3657240
Závěr:

Metoda větví a hranic v porovnání s hrubou silou podává velmi dobré výsledky. Optimalizace ořezáváním je účinější než jsem předpokládal, vypadá to, že se jedná a metodu s nejlepším poměrem přesnost / doba výpočtu.
Metoda dynamického programování dává optimální výsledky v rozumném čase. Je pamětově náročnější, což se promítne při řešní složitějších problémů.
Heuristická metoda podává nejrychlejší výsledky (závislé pouze na použitém algoritmu řazení - v našem případě bubble-sort). Bohužel tato metoda nenachází vždy nejlepší řešní.
Kombinace hrubé síly a heurestiky je ovšem opět velice silná metoda, která z obou metod přebírá výhody i nevýhody. Je tedy pomalejší než samotná heurestika, ale podává přesnější výsledky (v závislosti na parametru k, který určuje poměr použité hrubé síly a heurestiky).


Přílohy:

zdrojový kód batoh.cpp
zakompresovaná data použitá v analýze data.zip