Domácí úloha číslo 4. : Experimentální zhodnocení

1) Zadání : Prozkoumejte citlivost metod řešení problému batohu na parametry instancí generovaných generátorem náhodných instancí. 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íž souřadnice jsou výše uvedená kritéria.

2) Vypracování : Pro řešení zadaného problému jsem použil již hotový generátor náhodných instancí, který jsem pouze upravil do programovacího jazyka Borland C++ Builder 5. Veškeré parametry generátoru zůstaly zachovány.

 

3) Rozbor řešení :

Kvalita řešení: Kvalitu řešení můžeme díky tomu, že hrubá síla nám dává optimální řešení, zjišťovat absolutně vůči jejímu řešení. Tabulka kvality a graf 1 nám poskytují názornou představu o kvalitě algoritmů. Abs. chyba je aritmetický průměr všech absolutních chyb zjištěných cen vůči hrubé síle v souboru 50-ti instancí, % chyba pak určuje tuto absolutní chybu v relativním měřítku vůči optimální ceně. Počet chyb udává, kolikrát došlo k libovolně velké chybě, oproti optimu, nebo-li doplněk do 50-ti nám určuje, kolikrát vypočetl daný algoritmus optimální cenu batohu.

Výpočetní náročnost řešení: Náročnost jednotlivých řešení můžeme určit opět absolutně a to měřením času výpočtu, nebo určením projitých stavů stavového prostoru, který je velký 2^(počet věcí v batohu). Časové měření je však závislé na mnoha faktorech, především pak na výkonnosti počítače (procesor, paměť, systém ...). Pokud ovšem budeme měřit na jednom konkrétním počítači pak nám i tato metoda poskytne srovnání mezi náročností jednotlivých algoritmů. Určení počtu projitých stavů je sice na těchto technických vlivech nezávislé, avšak i zde narážíme na problém. A to co se v daných algoritmech má považovat za jeden stav stavového prostoru. Pokud bychom za stav určili jeden konkrétní naplněný batoh, což se nabízí jako první alternativa, nejsem si jist zda-li bychom se tím nedopustili velkého zkreslení. Proto jsem si zavedl dva ukazatele, počet stavů a počet uzlů, které mají pro algoritmy následující význam.

 

Algoritmus

Počet stavů

Počet uzlů

Hrubá síla

řešení, při kterém není batoh přeplněn

všechna možná řešení

Poměr c/v

počet věcí v batohu

počet věcí v batohu +1, při kterém se zjistí přeplnění

Dynamicky

kolikrát přidává novou věc do batoh

kolikrát spouštím rekurzivní funkci pro výpočet

Ořezávání

kolikrát při ořezávání projde listem

kolikrát se počítá max.možná cena (heuristika c/v)

 

4) Naměřené hodnoty :

n

Dle poměru cena/váha

Dynamické programování

Ořezávání

poč.věcí

abs.chyba

% chyba

počet chyb

abs.chyba

% chyba

počet chyb

abs.chyba

% chyba

počet chyb

4

25,84

2,53654

27

0

0

0

11,26

1,09274

13

10

39,32

2,45655

35

0

0

0

26,42

1,63583

23

15

29,42

1,35116

30

0

0

0

15,78

0,71518

16

20

34,68

1,47873

35

0

0

0

23,64

0,99846

26

22

16,3

4,16582

13

0

0

0

8,52

2,01079

6

 

 

 

 

 

 

 

 

 

 

cena

Dle poměru cena/váha

Dynamické programování

Ořezávání

max.cena

abs.chyba

% chyba

počet chyb

abs.chyba

% chyba

počet chyb

abs.chyba

% chyba

počet chyb

100

10,74

1,78135

26

0

0

0

6,1

1,0379

18

250

39,32

2,45655

35

0

0

0

26,42

1,63583

23

400

34,64

1,41619

29

0

0

0

17,54

0,73311

18

550

59,26

1,76365

29

0

0

0

34,92

1,05092

22

700

74,78

1,6665

32

0

0

0

35,44

0,79989

19

 

 

 

 

 

 

 

 

 

 

d

Dle poměru cena/váha

Dynamické programování

Ořezávání

rozložení

abs.chyba

% chyba

počet chyb

abs.chyba

% chyba

počet chyb

abs.chyba

% chyba

počet chyb

více malých

24,26

1,52255

26

0

0

0

12,42

0,76933

18

stejně

39,32

2,45655

35

0

0

0

26,42

1,63583

23

více velkých

24,26

1,52255

26

0

0

0

12,42

0,76933

18

 

 

 

 

 

 

 

 

 

 

k

Dle poměru cena/váha

Dynamické programování

Ořezávání

granularita

abs.chyba

% chyba

počet chyb

abs.chyba

% chyba

počet chyb

abs.chyba

% chyba

počet chyb

1

39,32

2,45655

35

0

0

0

26,42

1,63583

23

5

39,32

2,45655

35

0

0

0

26,42

1,63583

23

10

39,32

2,45655

35

0

0

0

26,42

1,63583

23

20

39,32

2,45655

35

0

0

0

26,42

1,63583

23

50

39,32

2,45655

35

0

0

0

26,42

1,63583

23

 

 

 

 

 

 

 

 

 

 

m

Dle poměru cena/váha

Dynamické programování

Ořezávání

kap:sum

abs.chyba

% chyba

počet chyb

abs.chyba

% chyba

počet chyb

abs.chyba

% chyba

počet chyb

1:10

29,44

5,47572

25

0

0

0

13,16

2,59023

10

3:10

50,36

4,69984

39

0

0

0

27,24

2,54506

24

5:10

28,24

2,02457

33

0

0

0

12,92

0,94198

18

7:10

16,88

0,99255

28

0

0

0

7,22

0,41637

11

9:10

7,26

0,40438

20

0

0

0

2,28

0,1255

5

Tabulka kvality

 

 

Dle cena/váha

Dynamické program.

Hrubá síla

Ořezávání

n

sek.

stavů

uzlů

sek.

stavů

uzlů

sek.

stavů

uzlů

sek.

stavů

uzlů

4

0

121

171

0,06

460

1217

0

460

750

0,05

319

800

10

0

331

381

0,05

23352

52174

0,06

35799

51150

0,5

17313

51200

15

0

501

551

0,27

113270

239216

1,65

1217745

1638350

9,06

498061

1638400

20

0

684

734

0,5

250391

519084

55,59

40723369

52428750

380,25

15953778

52428800

22

0,05

749

799

0,66

322466

665608

241,8

165268847

209715150

2599,85

61364495

209715200

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Dle cena/váha

Dynamické program.

Hrubá síla

Ořezávání

Cmax

sek.

stavů

uzlů

sek.

stavů

uzlů

sek.

stavů

uzlů

sek.

stavů

uzlů

100

0

493

543

0,28

115016

242525

1,37

1217745

1638350

9,06

478474

1638400

250

0

501

551

0,27

113270

239216

1,65

1217745

1638350

9,06

498061

1638400

400

0

503

553

0,28

113908

240303

1,37

1217745

1638350

9,06

476382

1638400

550

0

500

550

0,33

114292

241165

1,37

1217745

1638350

9,01

479292

1638400

700

0,06

505

555

0,27

114357

241393

1,37

1217745

1638350

9,01

487930

1638400

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Dle cena/váha

Dynamické program.

Hrubá síla

Ořezávání

rozložení

sek.

stavů

uzlů

sek.

stavů

uzlů

sek.

stavů

uzlů

sek.

stavů

uzlů

více malých

0

495

545

0,27

115281

243159

1,37

1216425

1638350

9,07

481385

1638400

stejně

0

501

551

0,27

113270

239216

1,65

1217745

1638350

9,06

498061

1638400

více velkých

0

495

545

0,28

115281

243159

1,37

1216425

1638350

9,06

481385

1638400

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Dle cena/váha

Dynamické program.

Hrubá síla

Ořezávání

granularita

sek.

stavů

uzlů

sek.

stavů

uzlů

sek.

stavů

uzlů

sek.

stavů

uzlů

k=1

0

501

551

0,27

113270

239216

1,65

1217745

1638350

9,06

498061

1638400

k=5

0

501

551

0,27

113270

239216

1,38

1217745

1638350

9,06

498061

1638400

k=10

0

501

551

0,28

113270

239216

1,37

1217745

1638350

9,06

498061

1638400

k=20

0

501

551

0,27

113270

239216

1,43

1217745

1638350

9,06

498061

1638400

k=50

0

501

551

0,28

113270

239216

1,43

1217745

1638350

9,06

498061

1638400

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Dle cena/váha

Dynamické program.

Hrubá síla

Ořezávání

kap:sum

sek.

stavů

uzlů

sek.

stavů

Uzlů

sek.

stavů

uzlů

sek.

stavů

uzlů

1:10

0

177

227

0,05

3554

21858

1,32

3772

1638350

6,1

2090

1638400

3:10

0

325

375

0,11

49215

120768

1,37

152040

1638350

7,8

49259

1638400

5:10

0

450

500

0,28

95633

207354

1,37

820559

1638350

8,84

321182

1638400

7:10

0

562

612

0,28

126976

263117

1,43

1486134

1638350

9,17

673046

1638400

9:10

0

671

721

0,38

142752

287622

1,82

1634535

1638350

9,17

802827

1638400

Tabulka náročnosti

Graf 1

Graf 2

Graf 3

5) Závěr :

Z tabulky kvality a grafu 1 je jasně patrné, že metodou dynamického programování jsme dosáhli optimálního řešení jako při hrubé síle. Metoda ořezávání by měla také poskytovat optimální řešení, ale u mé metody tomu tak není, což jednoznačně ukazuje na špatně volenou funkci ořezávání, jelikož se ořezává i větev s optimálním řešením. Graf 1 nám poskytuje přehled o vlivu různorodosti dat na chybovost algoritmů. Asi nejzajímavější lze považovat zjištění, že při změně exponentu granularity se chybovost vůbec nemění. Při více malých či velkých věcí v batohu je chybovost o téměř 1 % menší než při stejnoměrném rozložení věcí v batohu. Celkem předpokládaný výsledek jsme dostali pro změnu poměru kapacity batohu k celkové váze všech věcí. Je samozřejmé, že čím menší poměr (kapacita batohu se blíží k váze všech věcí) tím i menší chybovost, jelikož se do batohu vejde více věcí.

            Z tabulky náročnosti a grafů 2 a 3 je vidět silná závislost nároků na počtu věcí v batohu. Pro změnu maximální ceny, rozložení věcí v batohu a exponentu granularity zůstává náročnost konstantní. Pro poslední ze zkoumaných parametrů, poměr kapacity batohu k celkové váze věcí, lze taktéž jako u parametru počtu věcí v batohu, pozorovat nárůst náročnosti vzhledem k růstu poměru. Asi největší nárůst časové náročnosti je pro metodu dynamického programování. Pro metody hrubé síly a ořezávání je nárůst minimální. Metoda poměru c/v je časově neměřitelná avšak pro počty stavů grafy vykazují stejné tendence jako pro ostatní metody.

Z těchto všech tabulek a grafů je jasně patrné, že pro problém batohu je asi nejlepší dynamické programování, které je velice rychlé a poskytuje optimální řešení. V případě mnohonásobně většího počtu věcí v batohu a podmínce co nejrychlejšího výpočtu řešení lze použít metodu poměru c/v. Musíme však počítat s tím, že tato metoda bude poskytovat řešení s chybou, která je však menší než 6%.

 

 

batoh1 – podrobnější popis metod hrubé síly a heuristiky c/v

batoh3 – podrobnější popis metod dynamického programování a ořezávání

batoh.exe – kompletní verze programu pro řešení problému batohu ve spustitelném tvaru

batoh.cpp – kompletní verze programu pro řešení problému batohu ve zdrojovém tvaru

gener.exe – generátor instancí dle parametrů z příkazové řádky či dle průvodce ve spustitelném tvaru