Úloha 3 z předmětu 36PAA

Zadání

Problém batohu

Všechny Vaše existující programy pro 0/1 batoh upravte tak, aby poskytovaly pomocný výstup ve formátu
 
ID počet kroku rešení výsledná cena
... ... ...

Výsledky řešení problému batohu

Metoda

Závislost výpočetního času na n

Čas je uveden v instrukčních cyklech, kvůli odstíněnní závislosti na rychlosti procesoru. V řádu časové složitosti se to však neprojeví, jedná se pouze o multiplikativní konstantu.

Tabulka závislosti výpočetního času na n

Graf závislosti výpočetního času na n

Graf závislost výpočetního času na n

Jak je vidět, časová složitost metody dynamického programování je lepší zhruba pro n>40.

Tabulka porovnání dosažené ceny exaktní metody a heuristiky

Zdrojový kód

Závěr

Metoda větví byla použita již v první úloze - prohledávání se ukončí jakmile je překročeno omezující kritérium. Metoda hranic odkrojí ty větve, v kterých i při vložení všech následujících věcí nebude překročena nejlepší dosažená cena. Metoda větví a hranic sice ořeže značnou část stavového prostoru, avšak časová složitost zůstavé stále na úrovni hrubé síly. Metoda dynamického programování vrací stejné hodnoty jako metoda hrubé síly, je však asymptoticky odpovídající heuristice. Její jedinou nevýhodou je větší paměťová složitost. Rozdíl heuristik cena/váha a cena: průměrnou Relativní chybu má lepší 1. metoda (0,54% vs 1,68%), avšak max. relativní chybu metoda druhá (36,4% vs 24,8%). Heuristika nejnižší ceny se podle předpokladů ukázala jako nejhorší.

Pozn. Relativní chyba je dána |E-H| / E kde E je výsledek exaktní metody a H výsledek heuristiky.