Zadání
- Prozkoumejte citlivost metod řešení problému batohu na parametry instancí generovaných generátorem náhodných instancí. Máte-li podezření na další závislosti, modifikujte zdrojový tvar generátoru.
- Na základě zjištění navrhněte a proveďte experimentální vyhodnocení kvality řešení a výpočetní náročnosti.
- Pokud možno, prezentujte algoritmy jako body v ploše, jejíž souřadnice jsou výše uvedená kritéria.
Postup experimentu
Nejprve jsem sjednotil úlohy Batoh 1 a Batoh 2 do jediného projektu. Přidal jsem druhý výstup do kterého se ukládají průměrné hodnoty počtu operací v případě exaktních metod a relativních chyb v případě heuristik.
Pro generování instancí jsem použil Webový generátor instancí problému batohu. V předešlých úlohách jsme porovnávali výpočetní náročnost algoritmů v závislosti na velikosti instance. Proto jsem se soustředil na získání závislosti výpočetní náročnosti a chyby v závislosti na poměrné kapacitě batohu a granularitě vkládaných věcí. Pro experimenty jsem použil toto nastavení (pokud není uvedeno jinak):
Velikost instance: 20, Počet instancí: 50, Maximální váha věci: 100, Maximální cena věci: 250
Naměřené hodnoty a výsledky
V tabulce a grafech jsou zobrazeny průměrné hodnoty.
Tabulka: Závislost výpočetní náročnosti na kapacitě batohu (pro velikost instance = 15)
| poměr sumární váhy ke kapacitě batohu / algoritmus | BF | B&B | Dynamické prog. | GP |
|---|---|---|---|---|
| 0,1 | 345,5 | 304,2 | 1137 | 15 |
| 0,2 | 1817,4 | 1131,3 | 2238 | 15 |
| 0,3 | 5932,9 | 2566,1 | 3606 | 15 |
| 0,4 | 14287,2 | 3322,5 | 4387,5 | 15 |
| 0,5 | 21961,7 | 3187,8 | 5793 | 15 |
| 0,6 | 28282,3 | 2664,5 | 7099,5 | 15 |
| 0,7 | 31672,4 | 1178,9 | 8038,5 | 15 |
| 0,8 | 32642,6 | 539,7 | 9402 | 15 |
| 0,9 | 32760,5 | 285,5 | 10243,5 | 15 |
Dle mého názoru nemá praktický význam zde uvádět veškeré naměřené hodnoty. Daleko lepší vypovídající hodnotu mají grafy, které následují.
Za zmínku pouze stojí porovnání výpočetní složitosti Hrubé síly (BF) s ostatními algoritmy.
Graf 1: Závislost výpočetní náročnosti na kapacitě batohu (pro velikost instance = 15)
Nastavení generátoru: Velikost instance: 15, Počet instancí: 10, Maximální váha věci: 100, Maximální cena věci: 100
Graf 2: Závislost výpočetní náročnosti na kapacitě batohu (pro velikost instance = 20)
Graf 3: Závislost výpočetní náročnosti na granulritě instance (převaha malých věcí)
Charakter granularity nastaven na "Více malých věcí".
Graf 4: Závislost výpočetní náročnosti na granulritě instance (převaha velkých věcí)
Charakter granularity nastaven na "Více velkých věcí".
Graf 5: Závislost relativní chyby na kapacitě batohu (pro velikost instance = 15)
Velikost instance: 15, Počet instancí: 10, Maximální váha věci: 100, Maximální cena věci: 100
Graf 6: Závislost relativní chyby na kapacitě batohu (pro velikost instance = 20)
Graf 7: Závislost relativní chyby na granularitě instance
Závěr
Z grafu 1 a 2 je dobře patrné, že algoritmus větví a hranic (B&B) dosahuje nejhorší výpočetní náročnosti pokud je poměr sumární váhy ke kapacitě batohu roven 0,3 až 0,5.
Dále je patrná lineární závislost výpočetní náročnosti dynamického programovaní. Ta je vypočtena jako rozměr pole, tj. kapacita x počet věcí. Počet věcí je konstantní, ale mění se kapacita batohu, címž je ovlivněno měření. Pokud by generátor zachoval kapacitu konstantní, byla by i závislost konstantní.
Chyba heuristiky se zmenšuje s rostoucím poměrem sumární váhy ke kapacitě batohu. Naproti tomu o závislosti chyby heuristiky na granularitě nemůžeme z provedeného experimentu nic usoudit, hodnoty jsou téměř náhodné.