U heuristiky nebudeme měřit časovou závislost, ta záleží jen lineárně na počtu věcí a je nejnižší. Naopak zde budeme zkoumat závislost kvality řešení (porovnání s exaktními metodami). V grafech je použito uzlů a pro posouzení kvality heuristiky Ø relativní zhoršení v %.
Id | Parametr generátoru | Značení | Formát | Defaultní hodnota | Testované hodnoty |
1. | Velikost instance | n | celé číslo | 20 | 4; 10; 15; 20; 22; 25; 27; 30; 32; 35; 37; 40 |
2. | Počet instancí | i | celé číslo | 50 | neměníme, dostačující pro statistické průměrování |
3. | Maximální váha věci | Wmax | celé číslo | 100 | 50; 100; 150; 200; 250; 300 |
4. | Maximální cena věci | Cmax | celé číslo | 250 | 50; 100; 150; 200; 250; 300 |
5. | Poměr sumární váhy ke kapacitě batohu | m | desetinné číslo | 0.6 | 0,1; 0,2; 0,3; 0,4; 0,5; 0,6; 0,7; 0,8; 0,9; 1 |
6. | Charakter granularity | g | celé číslo | 1-Nerozlišovat | 1 - Nerozlišovat 0 - Více malých věcí 2 - Více velkých věcí |
7. | Exponent závislosti granularity | e | desetinné číslo | 1 | -2; -1; -0,5; 0; 0,5; 1; 2 |
Kvalita HC pro větší instance stoupá. Proto je vhodnější, když exaktní metody jsou příliš zdlouhavé.
Tento parametr nemá vliv na žádnou metodu.
Tento parametr má vliv na metodu DP, zvětšuje tabulku a proto trvá déle. Naopak matoda VH trvá kratší dobu, nejlepší cena dosáhne rychleji vyšší hodnoty a dojde k drastičtějšímu ořezání stromu.
Tento parametr nemá vliv na žádnou metodu.
Jak je vidět z výsledků, některé parametry jsou zcela nezávislé, jiné nepatrně a jiné silně, zde je nutné s tímto faktem počítat a zvolit vhodnou metodu (případně i kombinace metod). Například pro třídění náhodých prvku je pro instanci o velikosti do několika desítek vhodné použít MergeSort, a pro větší QuickSort. Měření neuvažuje závislost parametrů mezi sebou navzájem, rapidně by tím stoupnul počet měření, a v tomto typu úlohy není tento vliv významný.