Pro zadaná vstupní data vyřešte 0/1 problém batohu následujícími metodami:
Pozorujte závislost výpočetního času na počtu předmětů n, u heuristických metod také průměrné zhoršení proti exaktním metodám a maximální chybu.
Nechal jsem programem zpracovat dodaná vstupní data. Řešení hrubou silou jsem prováděl pouze v rozsahu 4–30 předmětů, neboť pro větší počty předmětů jsou zapotřebí extrémní časy. Výsledky jsou v následující tabulce:
n | Čas BF | Čas H1 | Čas BB | Čas DP | Čas H2 | Max. chyba H1 | Prům. chyba H1 | Max. chyba H2 | Prům. chyba H2 |
---|---|---|---|---|---|---|---|---|---|
4 | 0,009 | 0,008 | 0,008 | 0,354 | 0,007 | 36,36 % | 2,17 % | 24,75 % | 1,33 % |
10 | 0,024 | 0,011 | 0,030 | 2,597 | 0,011 | 11,48 % | 1,10 % | 11,48 % | 1,10 % |
20 | 18,961 | 0,018 | 0,184 | 11,914 | 0,018 | 4,08 % | 0,45 % | 4,08 % | 0,45 % |
22 | 72,213 | 0,016 | 0,557 | 14,870 | 0,016 | 3,02 % | 0,54 % | 3,02 % | 0,54 % |
25 | 593,531 | 0,017 | 1,145 | 19,417 | 0,017 | 2,59 % | 0,42 % | 2,59 % | 0,42 % |
27 | 2505,576 | 0,019 | 1,753 | 22,079 | 0,017 | 1,85 % | 0,29 % | 1,85 % | 0,29 % |
30 | 20421,150 | 0,022 | 6,589 | 29,369 | 0,019 | 1,75 % | 0,40 % | 1,75 % | 0,40 % |
32 | — | 0,023 | 10,603 | 32,398 | 0,021 | 2,28 % | 0,28 % | 2,28 % | 0,28 % |
35 | — | 0,025 | 32,141 | 38,350 | 0,023 | 1,82 % | 0,19 % | 1,82 % | 0,19 % |
37 | — | 0,028 | 33,691 | 41,813 | 0,024 | 1,18 % | 0,18 % | 1,18 % | 0,18 % |
40 | — | 0,034 | 253,529 | 48,955 | 0,028 | 0,95 % | 0,15 % | 0,95 % | 0,15 % |
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. (Poznámka: v grafu časů není vidět celá naměřená křivka pro metodu hrubé síly, protože jinak by grafy ostatních metod prakticky splývaly.
Je zřejmé, že náročnost řešení hrubou silou exponenciálně roste, takže již při počtu předmětů blížícím se čtyřiceti je takové řešení nepoužitelné. Oproti tomu je časová náročnost heuristických metod zcela zanedbatelná, přičemž se jejich výsledky pro vyšší počty předmětů od optimálního řešení liší jen velmi málo. Pro malý počet předmětů je výhodné testovat nejcennější předmět (heuristika 2), neboť se tím poněkud zmenší případné extrémní chyby. Pro vyšší počty předmětů již tento test nepřináší žádné zlepšení.
Zbývající dvě metody jsou jistým kompromisem: dávají přesná řešení ve výrazně kratším čase než metoda hrubé síly. Metoda dynamického programování toho dosahuje dokonce v polynomiálním čase (při omezených cenách), ovšem za cenu vysoké paměťové náročnosti. Metoda větví a mezí je velice dobrým vylepšením metody hrubé síly, protože relativně jednoduchou úpravou programu dosahuje mnohem lepšího času.
Ještě je třeba se zmínit o čase metody větví a mezí pro 40 předmětů. Je zde vidět obrovský skok oproti předchozím 37 předmětům (proto také příliš neodpovídá použité proložení křivkou), přičemž tento průměrný čas je zkreslen jedinou instancí (instance číslo 9557) problému, která vyžaduje prohledání více než desetkrát vyššího počtu stavů než libovolná jiná instance.