Úloha z předmětu 36PAA
Martin Tůma
U jednotlivých metod byly odhadnuty následující závislosti a provedena příslušná měření:
Použitá implementace metody hrubé síly [2] prochází vždy všechny možné stavy stavového prostoru, není tedy ani teoreticky možné, aby výpočetní složitost byla závislá na jiném paramatru než velikosti instance. Dále se jedná, stejně jako u B&B a dynamického programování, o "exaktní" metodu (tzn. metoda najde vždy optimální řešení) z čehož plyne, že je zbytečné provádět jakákoliv měření kvality/relativní chyby algoritmu.
Zde lze předpokládat, že algoritmus je citlivý na poměr sumární váhy ke kapacitě batohu (m/M). Pro velmi málo zaplňený batoh lze předpokládat účiné ořezávání zespoda (tzn. v dalších větvích již nelze očekávat lepší výsledek), pro téměř plný batoh pak naopak účinné ořezávání zezhora (přidání dalších věcí by vedlo k přeplnění batohu).
Algoritmus B&B dále může být citlivý na granularitu věcí v batohu.
Řešení metodou dynamického programování má složitost O(mmax·n), musí tedy lineárně záviset na parametru maximální váhy věci. Jiné závislosti nelze předpokládat.
Výpočetní složitost kombinované heuristiky by měla být ke všem parametrům, invariantní, závislosti lze ovšem očekávat u kvality/relativní chyby metody, a to na poměru sumární váhy ke kapacitě batohu (m/M) - s rostoucím zaplněním batohu je méně kritické nevložení některé věci - a granularitě obsahu.
Výchozí konfigurace generátoru pro všechna měření:
Naměřené výsledky jsou vždy průměry (na jednu instanci) ze všech instancí ve vstupním souboru při změně zkoumaného parametru.
m/M | 0.1 | 0.2 | 0.3 | 0.4 | 0.5 | 0.6 | 0.7 | 0.8 | 0.9 |
---|---|---|---|---|---|---|---|---|---|
Navštívených stavů | 25591 | 212984 | 368107 | 287676 | 151114 | 31370 | 7629 | 925 | 166 |
Graf 1: Závislost výpočetní složitosti metody B&B na poměru sumární váhy ke kapacitě batohu.
n | Navštívených stavů (Více malých věcí) |
Navštívených stavů (Více velkých věcí) |
---|---|---|
20 | 533 | 4555 |
25 | 1059 | 21819 |
30 | 1952 | 89142 |
35 | 3911 | 663775 |
40 | 11013 | 2303979 |
Graf 2: Výpočetní složitosti metody B&B při velké a malé granularitě věcí v batohu. (k=1)
Maximální váha věci | 100 | 500 | 1000 | 5000 | 10000 | 20000 |
---|---|---|---|---|---|---|
Navštívených stavů | 44436 | 211642 | 428751 | 2069822 | 4294668 | 8414791 |
Graf 3: Závislost výpočetní složitosti metody dynamického programování na maximální váze věci.
m/M | ηø [%] | ηmax [%] |
---|---|---|
0.1 | 1.29 | 5.39 |
0.2 | 1.30 | 5.23 |
0.3 | 0.76 | 3.75 |
0.4 | 0.66 | 3.66 |
0.5 | 0.53 | 4.56 |
0.6 | 0.22 | 1.46 |
0.7 | 0.23 | 1.46 |
0.8 | 0.17 | 1.26 |
0.9 | 0.09 | 1.33 |
Graf 4: Závislost relativní chyby řešení kombinované heuristiky na poměru sumární váhy ke kapacitě batohu.
n | v.m.v. ηø [%] |
v.m.v. ηmax [%] |
v.v.v. ηø [%] |
v.v.v. ηmax [%] |
---|---|---|---|---|
20 | 0.85 | 5.42 | 0.40 | 2.99 |
25 | 0.61 | 4.23 | 0.26 | 1.65 |
30 | 0.41 | 2.20 | 0.24 | 2.29 |
35 | 0.21 | 1.39 | 0.23 | 1.57 |
40 | 0.28 | 2.26 | 0.29 | 1.57 |
Graf 5: Relativní chyba řešení kombinované heuristiky při velké a malé granularitě věcí v batohu.
Výpočetní složitost metody B&B v závislosti na na poměru sumární váhy ke kapacitě batohu potvrdila doměnky, že směrem ke "kraji" grafu nabývá na účinnosti vždy jedno z obou ořezávání stavového prostoru. Zajímavá je poloha maxima grafu, které je posunuto směrem k počátku (m/M = 0.3), což svědčí o vyšší účinosti ořezávání zezhora.
Mnohem překvapivější je vysoký rozdíl výpočetní složitosti pro různou granularitu věcí v batohu, která je pro převahu velkých věcí v batohu řádově vyšší, než pro batoh složený z více malých věcí. Pro tento jev jsem však bohužel žádné věrohodné vysvětlení nenašel.
Test pro metodu dynamického programování zcela potvrdil lineární závislost výpočetní složitosti na maximální váze věci, i, což z grafu patrné není, rostoucí paměťovou náročnost algoritmu v závislosti na max. váze. Pro řešení instancí s max. váhou 20000 jsou již třeba desítky MB RAM.
Experimenty zaměřené na kvalitu řešení heuristiky prokázaly závislost relativní chyby na poměru sumární váhy ke kapacitě batohu i mírnou závislost na granularitě věcí v batohu. Rozhodujícím kritériem pro kvalitu řešení je však velikost instance - pro velká n klesá i vliv závislostí na parametrech na kvalitu/relativní chybu řešení.
[1]
http://service.felk.cvut.cz/courses/36PAA/wknapgen.html
[2]
http://tumic.wz.cz/fel/online/36PAA/1
1. batoh_bb.c
- Program pro řešení metodou B&B.
2. batoh_dyn.c
- Program pro řešení dynamickým programováním.
3. batoh_h2.c
- Program pro řešení heuristikou podle poměru C/m s testem Cmax
4. stats.sh
- Script na výpočet relativní chyby heuristiky