Problém batohu

Zadání úlohy

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.

Použité algoritmy

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.

Naměřená data

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:

Naměřené časy Naměřené chyby

Závěr

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.