36PAA - Experimentální hodnocení algoritmů pro řešení problému batohu

Zadání

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 / algoritmusBFB&BDynamické prog.GP
0,1345,5304,2113715
0,21817,41131,3223815
0,35932,92566,1360615
0,414287,23322,54387,515
0,521961,73187,8579315
0,628282,32664,57099,515
0,731672,41178,98038,515
0,832642,6539,7940215
0,932760,5285,510243,515

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

Závislost výpočetní náročnosti na kapacitě batohu

Graf 2: Závislost výpočetní náročnosti na kapacitě batohu (pro velikost instance = 20)

Závislost výpočetní náročnosti na kapacitě batohu

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í".

Závislost výpočetní náročnosti na granulritě instance (převaha 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í".

Závislost výpočetní náročnosti na granulritě instance (převaha 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

Závislost relativní chyby na kapacitě batohu (pro velikost instance = 15)

Graf 6: Závislost relativní chyby na kapacitě batohu (pro velikost instance = 20)

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é.