Hodnocení algoritmů pro řešení problému batohu (4. úloha)

Zadání úlohy

Analyzujte algoritmy pro řešení problému batohu z hlediska dvou kritérií: kvalita řešenívýpočetní náročnost.

Citlivost algoritmů na parametry instancí

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.

Dynamické programování versus maximální cena

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.

Závislost výpočetní náročnosti DP na maximální ceně

Poměr celková váha předmětů / kapacita batohu

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í.

Závislost výpočetní náročnosti na poměru celková váha / kapacita

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.

Dynamické programování versus max.cena, poměr váha/kapacita

Granularita instance

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ý.

Vyhodnocení algoritmů

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á.

Zhodnocení algoritmů Zhodnocení algoritmů -- včetně poměru kapacita/váha

Závěr

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.