Úloha 4 z předmětu 36PAA

Zadání

Problém batohu

• Prozkoumejte citlivost metod rešení problému batohu na parametry instancí generovaných generátorem náhodných instancí. Máte-li podezrení 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íž souradnice jsou výše uvedená kritéria.

Stručný popis použitých metod

Použijeme metody již dříve pouřité a to

• Exaktní:
  • Větve a hranice (VH)
  • Dynamické programování (DP)
• Heuristika:
  • Heuristika podle poměru cena/váha (HC)

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

Výsledky řešení problému batohu

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

Velikost instance

Kvalita HC pro větší instance stoupá. Proto je vhodnější, když exaktní metody jsou příliš zdlouhavé.

Maximální váha věci

Tento parametr nemá vliv na žádnou metodu.

Maximální cena věci

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.

Poměr sumární váhy ke kapacitě batohu

Nevejde-li se do batohu žádná či všechny věci dává metoda HC přesný výsledek, jinak je výsledek tím přesnější, čím je větší a tím pádem se do batohu vejde víc věcí. Metoda VH stoupá v důsledku vzrůstajícího počtu věcí, které se dají do batohu vložit, dosahuje maxima dosahuje pro m=0,3. Dále pak klesá v důsledku ořezávání.

Charakter granularity

Kvalita HV je větší pro více malých věcí. Větší věci v metodě VH způsobí rychlejší prožezání stromu.

Exponent závislosti granularity

Tento parametr nemá vliv na žádnou metodu.

Měřená data

Zdrojový kód

Závěr

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