4. Experimentální hodnocení algoritmů pro řešení problému batohu




Zadání:


Řešení:
Pro určení statistiky použijeme výpočetní náročnost a kvalitu řešení algoritmů. Výpočetní náročnost je určena počtem prohledaných konfigurací batohu. Kvalitu řešení pro heuristické metody určíme porovnáním ceny naměřené heurestikou a ceny optimálně sbaleného batohu.
Měření provedeme pro následující algoritmy: hrubá síla, dynamické programování, metoda větví a hranic, heuristika podle poměru cena/váha a kombinovaná heurestika.
Pro určení výpočetní náročnosti jsem vybral tyto sady testů:
Pro výpočet relativní chyby heurestických algoritmů použijeme stejný soubor vstupních dat jako v prvním zadání problému batohu, jen dopočítáme chybu pro kombinovanou heurestiku. Proměnnou veličinou je tedy počet předmětů.


Naměřené hodnoty:
U algoritmů podávajících exaktní řešení je chyba nulová a je tedy zbytečné ji v tabulkách uvádět. Všechny hodnoty uvedené v tabulkách vznikly jako průměr 50ti naměřených hodnot.

První tabulka udávájící zavislost výpočetní náročnosti na změně počtu věcí, maximální váhy věcí a ceny věcí.

parametry testu výpočetní náročnost
počet věcí maximální váha maximální cena hrubá síla větve a hranice dynamicky jednoduchá heurestika kombinovaná heurestika
10 100 250 20500 210,12 1013,22 65 2210
10 100 700 20500 225,26 1027,26 65 2210
10 300 250 20500 263,32 1376,18 65 2210
10 300 700 20500 231,22 1327,02 65 2210
25 100 250 1677721650 1552,3 20038,12 350 316900
25 100 700 1677721650 1439,38 20161,42 350 316900
25 300 250 1677721650 2037,56 55114,14 350 316900
25 300 700 1677721650 1432,1 52863,76 350 316900


Ve druhé tabulce je uvedena závislost zavislost výpočetní náročnosti na granularitě.

granualita výpočetní náročnost
charakter exponent závislosti hrubá síla větve a hranice dynamicky jednoduchá heurestika kombinovaná heurestika
více malých 1 41943080 1044,94 4938,58 230 97320
více malých 3 41943080 3128,78 445,24 230 97320
více velkých 1 41943080 1419,84 14747,7 230 97320
více velkých 3 41943080 2628,44 1052,9 230 97320


Třetí tabulka znázorňuje zavislost výpočetní náročnosti na poměru sumární váhy věcí k nosnosti batohu.

poměr sumární váhy věcí k nosnosti batohu výpočetní náročnost
hrubá síla větve a hranice dynamicky jednoduchá heurestika kombinovaná heurestika
0,1 41943080 743,9 960,98 230 97320
0,3 41943080 1049,84 5645,32 230 97320
0,5 41943080 1014 9730,8 230 97320
0,7 41943080 860 12834,58 230 97320
0,9 41943080 879,62 14074,28 230 97320


Poslední tabulka - porovnání relativních chyb heurestik v závislosti na počtu předmětů.

předmětů relativní chyba [%]
jednoduchá kombinovaná
10 1,1925 0,0000
15 0,3619 0,0182
20 0,6016 0,0391
22 0,3632 0,0420
25 0,4647 0,0162
27 0,6017 0,0205
30 0,4670 0,0202
32 0,3829 0,0470
35 0,3948 0,0266
37 0,5077 0,0302
40 0,4171 0,0243


Následující graf prezentuje algoritmy jako body v ploše a názorně tak ukazuje jejich použitelnost. Vychází z hodnot úplně prvního měření (tzn. první řádek v první tabulce), což není příliš podstatné, protože použití jiných hodnot ovlivní graf minimálně. Co by graf ovlivnilo je nastavení parametru k u kombinované heurestiky, jehož zmenšení by její bod posunulo směrem doprava dolů. Porovnání heurestických a exaktních algoritmů podle počtu navštívených stavů je velice nepřesné (dá se říci nepoužitelné?), body značící heurestiku by teoreticky měly být co se výpočetní složitosti níže než libovolná přesná metoda.

krasnej graf



Závěr:
Pro metodu hrubé síly neexistuje žádná závislost, metoda vždy prohledá celý stavová prostor.

Metoda větví a hranic má pro těžší přeměty větší výpočetní náročnost - předměty se do batohu nevejdou a začne tak další rekruze bez snížení volného prostoru v batohu. Překvapivě to vypadá, že metoda je závislá na exponentu závislosti granuality, to by znamenalo závislost na množství předmětů podobné váhy (k čemuž nevidím žádný rozumný důvod, jde spíše o náhodu). Dále to vypadá, že se metoda hodí pro hodně malé nebo naopak velké poměry celkové váhy věcí k nosnosti batohu.

Dynamické programování vykazuje závislost na maximální hmotnosti předmětu. To je dáno algoritmem, jedná se přeci o dekompozice podle kapacity batohu. Stejně jako u metody větví a hranic vykazuje dynamické programování jistou závislost na množství předmětů podobné váhy.

U heurestiky je rozhodující počet věcí k naskládání do batohu. Ten totiž ovlivňuje řazení, nejpomalejší část algoritmu.

Obecně se dá říct:


Přílohy:
zdrojový kód batoh.cpp
zakompresovaná data použitá v analýze data.zip