Závěrečná zpráva 4

Úvod

Výsledky měření

Obsah

1. Závislost na m (poměr nosnosti batohu a celkové váhy věcí) - počet stavů, cena
2. Závislost na maximální hmotnosti W - počet stavů, cena
3. Závislost na maximální ceně C - počet stavů, cena
4. Závislost na granularitě (d, k) (převaze velkých či malých věcí) - počet stavů, cena

Nastavení generátoru instancí, není-li řečeno jinak, je následující:

m = 0,5;  W_max = 300; C_max = 300; d = 0; k = 1 (nepodstatné)

Poznámka: závislost počtu stavů je uváděna pouze pro BB a DP, jelikož pro heuristiku je to konstantně 30 (= počet věcí). Závislost ceny řešení se naopak zkoumala pouze pro heuristiku, nebo» BB a DP  jsou exaktní algoritmy, tzn. vždy dosáhnou optimálního řešení (pročež právě podle srovnání s jejich výsledky určuji kvalitu heuristiky).

Značení

1. Závislost na m (poměr nosnosti batohu a celkové váhy věcí)

1.a. Závislost počtu navštívených stavů na m (poměr nosnosti batohu a celkové váhy věcí)

Tab 1.a: Počet navštívených stavů / m m bb dp 0,1 62572 13486 0,2 855056 26910 0,3 3774713 40628 0,4 3484917 53847 0,5 2428540 68380 0,6 593864 80124 0,7 84695 95371 0,8 10001 106371 0,9 739 121099

Závěr

 Můžeme vidět, že pro BB je nejsnazší buď hodně velký nebo hodně malý batoh. To je dáno tím, že u malého batohu mnohem dříve dochází k zamítnutí rozvíjené větve jakožto neperspektivní, naopak když je batoh hodně velký, tak se tam téměř všechny věci vejdou. DP roste lineárně proto, že obsahuje smyčku od 0 do nosnosti batohu. Kromě případu, kdy  poměr překračuje 0,7, BB provádí mnohonásobně víc operací než DP.

1.b. Závislost chyby ceny řešení heuristikou na m (poměr nosnosti batohu a celkové váhy věcí)

Tab 1.b: Chyba ceny řešení / m m odchylka hr 0,1 3,21% 0,2 4,54% 0,3 3,82% 0,4 4,98% 0,5 6,65% 0,6 8,78% 0,7 8,30% 0,8 6,77% 0,9 4,35%

Závěr

Odchylka heuristiky od optimálního řešení se s rostoucí velikosti batohu zvyšuje až k nosnosti rovné 60% celkové váhy věcí a pak se opět snižuje. Je tedy zapotřebí vzít tuto charakteristiku instance v potaz.

2. Závislost na maximální hmotnosti W

Rozmezí pro maximální hmotnost jsem zvolil s ohledem na propagované rovnoměrné rozložení vah věcí v rozsahu 31 až 600, tzn. počet věcí (+ 1) až dvacetinásobek, což mi připadá rozumné rozmezí na to, aby se projevily případné závislosti.

2.a. Závislost počtu navštívených stavů na max. hmotnosti

Tab 2.a: Počet navštívených stavů / Wmax Wmax bb dp 31 2513631 6960 60 2235911 13527 90 1943607 20145 120 1657329 27141 150 2048331 33675 180 2607335 40672 210 3523451 47589 240 2025606 54277 270 2637518 60678 300 2629382 66534 Wmax bb dp 330 1698373 74044 360 2763215 81258 390 1939966 86593 420 1900321 97191 450 2967573 101223 480 2788828 109962 510 2869162 116992 540 2068680 120156 570 1654920 133079 600 2892008 136248

Závěr

Z grafu se zdá, že maximální váha věci nemá na BB žádný vliv. DP mírně lineárně roste, protože W_max rovněž určuje nosnost batohu ( nosnost = m*W_max ).

2.b. Závislost chyby ceny řešení heuristikou  na max. hmotnosti

Tab 2.b: Chyba ceny řešení / Wmax Wmax odchylka hr 31 0,67% 60 0,69% 90 1,37% 120 1,64% 150 1,55% 180 2,40% 210 2,56% 240 2,71% 270 4,10% 300 6,31% Wmax odchylka hr 330 8,81% 360 11,40% 390 13,27% 420 16,12% 450 16,19% 480 17,79% 510 19,56% 540 18,23% 570 23,43% 600 20,72%

 Závěr

Chyba ceny heuristiky s W_max  roste, zvláště od W_max  = 270. S největší pravděpodobností heuristice dělá problémy rostoucí rozmanitost věcí (kombinací cena/hmotnost).

3. Závislost na maximální ceně C

3.a. Závislost počtu navštívených stavů na max. ceně

Tab 3.a: Počet navštívených stavů / Cmax Cmax bb dp 30 3409839 66285 60 1628137 69082 90 3274375 67354 120 1963898 67135 150 2335052 68002 180 1985827 69086 210 2250712 69093 240 2668862 68105 270 2306236 69747 300 3223225 67403 Cmax bb dp 330 1807276 67281 360 2202767 67545 390 2164388 66777 420 2395362 68425 450 2492475 69694 480 1849777 67848 510 2363729 66375 540 2743233 66735 570 2718265 66594 600 1496576 68225

Závěr

Z grafu se zdá, že maximální cena věci nemá na BB and DP žádný vliv. Můžeme však vypozorovat, že zatímco rychlost DP je víceméně konstantní, u BB je značně nepravidelná (jak ukazuje i měření závislosti na W_max).

3.b. Závislost chyby ceny řešení heuristikou  na max. ceně

Tab 3.b: Chyba ceny řešení / Cmax Cmax odchylka hr 30 28,26% 60 27,47% 90 25,18% 120 23,03% 150 21,35% 180 17,14% 210 15,61% 240 11,47% 270 10,03% 300 5,56% Cmax odchylka hr 330 4,50% 360 3,19% 390 2,91% 420 2,71% 450 2,66% 480 2,98% 510 2,85% 540 2,65% 570 2,61% 600 2,03%

Závěr

Chyba ceny heuristiky s C_max  klesá, zvláště od 0 do 330. Příčinou je, že při velké C_max je snazší vybrat ty nejcennější věci do řešení, které pak představují větší část řešení. Když se ceny věcí pohybují zhruba v kolem téže hodnoty, je úkol vybrat ty nejvhodnější hodně kombinačně náročný.

4. Závislost na granularitě (převaze velkých či malých věcí)

4.a. Závislost počtu navštívených stavů na granularitě

4.a.1 Převaha malých věcí (d = -1, pravděpodobnost  obsažení p = 1/w^k)

Tab 4.a.1: Počet navštívených stavů / četnost malých věcí k bb dp -0,6 2495035 67023 -0,4 1274735 67210 -0,2 2317295 67541 0 1968653 66845 0,2 1679668 61775 0,4 678101 52494 0,6 580166 43915 (Větší k => méně malých věcí)

4.a.2 Převaha velkých věcí (d = +1, pravděpodobnost obsažení p=1/(W_max-w)^k)

Tab 4.a.2: Počet navštívených stavů / četnost malých věcí k bb dp -0,6 1866978 66605 -0,4 1749475 67460 -0,2 2018245 67075 0 2798183 66192 0,2 2801690 73782 0,4 3738469 80535 0,6 3353919 88450 (Větší k => méně velkých věcí)

Závěr

Pro oba algoritmy je příznivější převaha větších věcí nad menšími, i když u BB je to podstatně výraznější. U BB je to dáno tím, že díky váhově výrazným věcem častěji dochází k odříznutí větve. 

4.b. Závislost chyby ceny řešení heuristikou  na granularitě

 4.b.1 Převaha malých věcí (d = -1, pravděpodobnost  obsažení p = 1/w^k)

Tab 4.b.1: Chyba ceny řešení / četnost malých věcí k odchylka hr -0,6 6,89% -0,4 7,96% -0,2 5,57% 0 6,82% 0,2 5,32% 0,4 3,44% 0,6 2,59% (Větší k => méně malých věcí)

4.b.2 Převaha velkých věcí (d = +1, pravděpodobnost obsažení p=1/(W_max-w)^k)

Tab 4.b.2: Chyba ceny řešení / četnost velkých věcí k odchylka hr -0,6 6,91% -0,4 5,97% -0,2 7,00% 0 5,80% 0,2 7,88% 0,4 10,65% 0,6 14,65% (Větší k => méně velkých věcí)

Závěr

Chyba ceny heuristiky klesá s rostoucím počtem těžších věcí. 

Přílohy