Pro zadaná vstupní data vyřešte 0/1 problém batohu jednak hrubou silou, jednak heuristikou podle poměru cena/váha. Pozorujte závislost výpočetního času na n, průměrné zhoršení proti exaktní metodě, maximální chybu.
Podle zadání jsem vytvořil jednak prohledávání hrubou silou, řešené několika způsoby, přičemž v programu používám rekurzivní proceduru. Heuristické řešení je triviální výpočet pole heuristického ohodnocení, načež toto pole procházím a vybírám dosud nepoužitý předmět s nejvyšším ohodnocením, který se do batohu ještě vejde.
Nechal jsem programem zpracovat dodaná vstupní data v rozsahu 4–30 předmětů. Výsledky jsou v následující tabulce:
| n | Čas brute-force | Čas heuristika | Maximální chyba | Průměrná chyba |
|---|---|---|---|---|
| 4 | 0,005 | 0,006 | 36,36 % | 2,17 % |
| 10 | 0,018 | 0,007 | 11,48 % | 1,10 % |
| 20 | 19,154 | 0,013 | 4,08 % | 0,45 % |
| 22 | 72,213 | 0,017 | 3,02 % | 0,54 % |
| 25 | 593,531 | 0,021 | 2,59 % | 0,42 % |
| 27 | 2505,576 | 0,021 | 1,85 % | 0,29 % |
| 30 | 20421,150 | 0,022 | 1,75 % | 0,40 % |
Všechny časy vyjadřují průměrný čas v milisekundách na jednu instanci problému.
Naměřené výsledky jsou shrnuty v následujících dvou grafech:
Je zřejmé, že náročnost řešení hrubou silou opravdu exponenciálně roste, takže již při počtu předmětů blížícím se 40 je takové řešení nepoužitelné. Oproti tomu je časová náročnost heuristického řešení zcela zanedbatelná, přičemž se její výsledky pro vyšší počty předmětů od optimálního řešení liší jen velmi málo.