Úloha 1 z předmětu 36PAA

Zadání

Základ problému

Je dáno

0/1 problém batohu

Nejznámější varianta je optimalizacní. Pokud se mluví o "problému batohu" bez bližšího určení, vetšinou se rozumí tato verze.

Zkonstruujte množinu X={x1, x2, ... ,xn }, kde každé xi je 0 nebo 1, tak, aby

Úloha

Výsledkem bude krátká zpráva s naměřenými charakteristikami, doprovázená zdrojovými texty. Meření nechť je orientační - doba chodu jednotlivých testů nemusí překračovat několik málo minut. Rozsáhlejší experimenty jsou náplní pozdějších úloh.

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

Exaktní metoda

Heuristika

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 exaktní metody stoupá exponencielně - O(2n), což je pro čísla řádu desítek už tak zdlouhavé, že se problém stává neřešitelným. Za použití heuristiky (poměr cena/váha) je časová složitost lineární - O(n) čož značí její dobrou kvalitu, dále ještě zjistíme jak mnoho se výsledky s použitím heuristiky liší od přesných.

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

Průměrné zhoršení proti exaktní metodě

Absolutní hodnoty 9,7; relativně 0,54%.

Maximální chyba

Pro Id=9 080 dosáhla absolutní hodnoty 121; pro Id=9 037 dosáhla relativní chyba 36,4%.

Zdrojový kód

Závěr

Čas pro řešení hrubou silou jsem měřil jen pro n do 30. Při vyšších hodnotách už narůsta potřebný čas do řádů hodin. Průměrná hodnota heuristického řešení se příliš neliší, zato v rychlosti je rapidní rozdíl.