Analyzujte algoritmy pro řešení problému batohu z hlediska dvou kritérií: kvalita řešení a výpočetní náročnost.
Nejprve jsem zkoušel programu předložit instance vyrobené generátorem při různých hodnotách parametrů, abych zjistil případnou citlivost algoritmů na příslušné parametry.
Nejprve jsem analyzoval citlivost metody dynamického programování na maximální cenu předmětu. Již z algoritmu je vidět, že čím vyšší je celková cena předmětů, tím větší je pole uchovávaných mezivýsledků (a tedy i paměťové nároky), a tím více času je zapotřebí pro jejich výpočet. Na následujícím grafu je vidět tento nárůst výpočetní složitosti.
Dále jsem zkusil zjistit, zda má na výpočetní náročnost algoritmů nějaký vliv poměr celkové váhy předmětů ke kapacitě batohu. Na následujícím grafu vidíme, že tento parametr má vliv na výpočetní náročnost metody hrubé síly i metody větví a mezí. Metoda dynamického programování je sice také ovlivněna, ovšem v mnohem menší míře, než obě předchozí.
Jelikož jsme již zjistili, že metodu dynamického programování ovlivňuje i maximální cena, je na následujícím grafu shrnutí vlivu obou parametrů, ze kterého je vidět, že max. cena je pro dynamické programování důležitějším parametrem.
Nakonec jsem ještě otestoval, jestli má nějaký vliv převaha malých, nebo převaha velkých věcí. Jak se můžete přesvědčit z grafů převaha malých, převaha velkých, na metodu větví a mezí granularita jistý vliv má (převaha velkých předmětů řešení zpomaluje), ovšem tento vliv je relativně malý.
V následujících grafech vidíme shrnutí vlastností použitých algoritmů: Každý bod znázorňuje použití jednoho algoritmu na skupinu instancí s jistým poměrem kapacita/celková váha. Ideální algoritmus by se nacházel v levém horním rohu grafu (maximální kvalita, minimální čas). Je zřejmé, že s výjimkou heuristických algoritmů mají všechny algoritmy 100% kvalitu (exaktní řešení). Z hlediska počtu prohledaných stavů (osa x, logaritmické měřítko) je pak celkově nejlepší metoda větví a mezí, ovšem vzhledem k její citlivosti na poměr kapacita/váha existují instance, pro které je lépe použít metodu dynamického programování, která je na tento poměr prakticky necitlivá.
Metody řešení problému batohu můžeme rozdělit do dvou skupin: exaktní metody a heuristické metody. Heuristické metody mají prakticky zanedbatelnou časovou náročnost a vzhledem k tomu, že jejich chyba je obvykle velice malá, jsou zřejmě nejlepší volbou pro nejběžnější situace.
Pokud vyžadujeme nejlepší řešení, z exaktních metod je obvykle o něco rychlejší metoda větví a mezí, ovšem pro problémy s „levnými“ věcmi může být lepší metoda dynamického programování, zvláště pokud se součet hmotností pohybuje kolem 50 % kapacity batohu.