Úloha 4: Experimentální hodnocení
Jan Dohnal (dohnaj1@fel.cvut.cz)
Prozkoumejte citlivost metod řešení problému batohu na parametry instancí generovaných generátorem náhodných instancí. Máte-li podezření 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íž souřadnice jsou výše uvedená kritéria.
Porovnávání metod řešení bude založeno na určení výpočetní složitosti a kvalitě řešení. U výpočetní složitosti se zjišťuje počet prohledaných konfigurací batohu. Kvalita řešení přichází zase v úvahu pouze pro neexaktní metody, tedy pro heuristiky, kde se sleduje relativní chyba ceny k ceně optimální.
Měřené metody budou tyto:
hrubá síla
heuristika podle poměru
heuristika podle poměru s testem nejcennější věci
dynamické programování
metoda větví a hranic
Při testech budeme rozlišovat, zda se jedná o metody hledající optimální či suboptimální řešení.
Budou provedeny následující testy:
Test A - změna maximální váhy a ceny věci
počet věcí: 10, 20
maximální váha: 100, 300
maximální cena: 250, 500, 1000
exponent závislosti granularity
Test B - změna granularity
počet věcí: 20
maximální váha: 100
maximální cena: 250
exponent závislosti granularity: 1, 2, 3
Test C - mění se počet věcí (pro heuristiky)
počet věcí: 5, 10, 15, 20, 25, 30
maximální váha: 100
maximální cena: 250
exponent závislosti granularity: 1
Test A - změna maximální váhy a ceny věci
| počet věcí | maximální váha | maximální cena | hrubá síla (#kroků) | větve a hranice (#kroků) | dyn.dle kapacity batohu (#kroků) |
| 10 | 100 | 250 | 1023 | 270,32 | 1051,74 |
| 500 | 271,42 | ||||
| 1000 | 273,58 | ||||
| 300 | 250 | 269,68 | 1411,71 | ||
| 500 | 287,34 | ||||
| 1000 | 261,8 | ||||
| 20 | 100 | 250 | 1048575 | 21034,2 | 12041,38 |
| 500 | 17618,4 | ||||
| 1000 | 25106,3 | ||||
| 300 | 250 | 21268,9 | 22131,14 | ||
| 500 | 23011,8 | ||||
| 1000 | 22151,2 |
Test B - změna granularity
| exponent závislosti granularity | hrubá síla (#kroků) | větve a hranice (#kroků) | dyn.dle kapacity batohu (#kroků) |
| 1 | 1048575 | 10060,04 | 7642,36 |
| 2 | 1048575 | 12101,09 | 5039,44 |
| 3 | 1048575 | 9984,73 | 4173,4 |
| 1 | 1048575 | 33762,04 | 15381,25 |
Test A - změna maximální váhy a ceny věci
| počet věcí | maximální váha | maximální cena | heuristika cena/váha (#kroků) | heuristika cena/váha s testem nejcennější věci (#kroků) |
| 10 | 100 | 250 | 7,12 | 7,12 |
| 500 | 7,18 | 7,18 | ||
| 1000 | 7,16 | 7,16 | ||
| 300 | 250 | 7,04 | 7,04 | |
| 500 | 7,12 | 7,12 | ||
| 1000 | 7,01 | 7,01 | ||
| 20 | 100 | 250 | 14,62 | 14,62 |
| 500 | 14,64 | 14,64 | ||
| 1000 | 14,47 | 14,47 | ||
| 300 | 250 | 14,64 | 14,64 | |
| 500 | 14,74 | 14,74 | ||
| 1000 | 14,83 | 14,83 |
Test B - změna granularity
| exponent závislosti granularity | heuristika cena/váha (#kroků) | heuristika cena/váha s testem nejcennější věci (#kroků) |
| 1 | 16,70 | 16,70 |
| 2 | 17,06 | 17,06 |
| 3 | 16,35 | 16,35 |
| 1 | 13,42 | 13,42 |
| 2 | 12,67 | 12,67 |
| 3 | 12,50 | 12,50 |
Test C - mění se počet věcí (pro heuristiky)
| počet věcí | heuristika cena/váha (#kroků) | heuristika cena/váha s testem nejcennější věci (#kroků) |
| 5 | 2,63 | 2,63 |
| 10 | 1,06 | 1,06 |
| 15 | 0,38 | 0,38 |
| 20 | 0,35 | 0,35 |
| 25 | 0,39 | 0,39 |
| 30 | 0,34 | 0,34 |
Následuje stručné shrnutí naměřených hodnot z testů, tedy stručná charakteristika jednotlivých metod.
výpočetní náročnost: pomalé řešení, exponenciální závislost
kvalita řešení: absolutní
hodnocení: nezávislá metoda, velmi pomalá, malá použitelnost (pro malé instance)
výpočetní náročnost: relativně rychlé řešení
kvalita řešení: absolutní
hodnocení: závislé na poměru sumární ceny věcí ke kapacitě, není tolik rychlá, pro specifické instance
výpočetní náročnost: celkem rychlé
kvalita řešení: absolutní
hodnocení: rychlá metoda, závislé na hmotnosti předmětů, velká paměťová režie
výpočetní náročnost: nejrychlejší řešení
kvalita řešení: dobrá
hodnocení: nejrychlejší metoda ale také přesná, pro obecné batohy
výpočetní náročnost: nejrychlejší řešení
kvalita řešení: dobrá
hodnocení: nejrychlejší metoda, stejná kvalita jako u normální heuristiky, velmi vhodné pro malé batohy