====== Experimentální hodnocení kvality algoritmů ======
  * CTU Prague, MI-PAA, ZS 2011
  * Autor: **Tomáš Borovička (borovto1)**

**Zadání**
  * 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
  * Pozorujte zejména závislosti výpočetního času (B&B, DP, heuristika) a rel. chyby (heuristika) na:
    * maximální váze věcí
    * maximální ceně věcí
    * poměru kapacity batohu k sumární váze
    * granularitě (pozor - zde si uvědomte smysl exponentu granularity)
  * Doporučuje se zafixovat všechny parametry na konstantní hodnotu a vždy plynule měnit jeden parametr

===== Popis problému =====
Úkolem je zhodnotit kvalitu řešení a výpočetní náročnost implementovaných algoritmů pro problém batohu v závislosti na parametrech řešených instancí.

===== Řešení =====
V práci hodnotím výpočetní náročnost a kvalitu v závislosti na parametrech řešených instancí u následujícíh algoritmů pro řešení problému batohu:

  * B&B branch and bound
  * Heuristika (cena/váha)
  * Dynamické programování
  * FTPAS

==== Chování vzhledem k maximální váze věcí ====

=== Kód pro generování instancí ===
<code bash>
#!/bin/bash
for i in 40 60 80 100 150 200 300 400 500
do
./knapgen -n 25 -N 40 -m 0.5 -W $i -C 200 -k 1 -d 0 >> instances/W/knap_W$i.inst.dat
done
</code>

=== Závislost výpočetního času ===
Závislost výpočetního času můžeme pozorovat u všech algoritmů krom heuristiky, kde je vliv jen minimální. U ostatních je vidět rostoucí tendence výpočetního času s maximální vahou.

{{:school:fit:mipaa:zavislostcasuvypotunavaze.png|}}

=== Relativní chyba ===
S rostoucí vahou výrazně roste průměrná chyba u řešení pomocí heuristiky (cena/váha). Naopak při řešení FPTAS průměrná chyba klasá - což je logické, víme-li, že u FPTAS dekomponujeme podle váhy věcí, neboli "zaokrouhluje" posledních x (2) bitů. Chyba u FTPAS klesala od 5% pri maximální váze 40 až pod 0,5% při maximální váze 500. Naopak relativní chyba u řešení pomocí heuristiky rostla s maximální vahou od 1,3% při maximální váze 40 až k 20% při maximální váze 500. 

{{:school:fit:mipaa:relativnichybavaha.png|}}

==== Chování vzhledem k maximální ceně věcí ====
=== Kód pro generování instancí ===
<code bash>
#!/bin/bash
for i in 40 60 80 100 150 200 300 400 500
do
./knapgen -n 25 -N 40 -m 0.5 -W 100 -C $i -k 1 -d 0 >> instances/C/knap_C$i.inst.dat
done
</code>

=== Závislost výpočetního času ===
Z grafu lze vypozorovat snižující se tendence při rostoucí maximální ceně. Tento trend lze pozorovat u šech algoritmů. Nejméně výrazný je opět u heuristiky, kde je na hranici signifikance.

{{:school:fit:mipaa:zavislostcasuvypoctunacene.png|}}

=== Relativní chyba ===
S grafu je vidět výrazné relativní chyba heuristiky, která se snižuje s rostoucí maximální cenou. To je opět očekávaný trend, vzhledem k logice heuristiky cena/váha. Naopak algoritmus založený na FTPAS není ovlivněn vůbec, jelikož je problém dekomponován podle váhy věcí.

{{:school:fit:mipaa:relativnichybacena.png|}}

==== Chování vzhledem k poměru kapacity batohu k sumární váze ====
=== Kód pro generování instancí ===
<code bash>
#!/bin/bash
for i in 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
do
./knapgen -n 25 -N 40 -m $i -W 100 -C 200 -k 1 -d 0 >> instances/m/knap_m$i.inst.dat
done
</code>

=== Závislost výpočetního času ===
U všech algoritmů, opět kromě heuristiky, je vidět výrazná závislost výpočetního času na poměru kapacity batuhu k sumární váze. U Dynamického programování a FTPAS je rostoucí trend výpočetního času s rostoucím poměrem. U řešení branch and bound můžeme pozorovat největší výpočetní složitost při poměru 0.5, při ostatních poměrech, když se sumární váha blíží kapacitě batohu, nebo je výrazně větší, dokáže B&B velice efektivně ořezat stavový prostor.

{{:school:fit:mipaa:zavislostcasuvypoctunapomerukapacityavaze.png|}}

=== Relativní chyba ===
Relativní chyba heuristiky je nejvyšší při poměru 0.5. Chyba FTPAS klesá s rostoucím poměrem, neboli klesající sumární váhou.

{{:school:fit:mipaa:relativnichybapomerkapacitavaha.png|}}

==== Chování vzhledem k granularitě ====
=== Kód pro generování instancí ===
<code bash>
#!/bin/bash
for i in 0.1 0.2 0.5 0.8 1 2 5 8
do
./knapgen -n 25 -N 40 -m 0.5 -W 100 -C 200 -k $i -d 0 >> instances/k/knap_k$i.inst.dat
done
</code>

=== Závislost výpočetního času ===
Závislost výpočetního času na granularitě je na hranici signifikance, spíše můžeme řici, že při nastavených parametrech neměla granularita vliv na výpočetní čas a to u všech testovaných algoritmů.

{{:school:fit:mipaa:zavislostcasuvypoctunagranularite.png|}}

=== Relativní chyba ===
Stejně jako výpočetní čas, ani relativní chyba při nastavených parametrech nekoreluje s granularitou testovaných instancí.

{{:school:fit:mipaa:relativnichybagranularita.png|}}

===== Závěr =====
Experimentálně jsem zkoumal chování čtyř implementovaných algoritmů v závislosti na parametrech řešených instancí a zhodnotil jejich kvalitu a závislost výpočetního času na těchto parametech. 

===== Source code =====


===== References =====
  * [[:school:fit:mipaa:ukol1|Úkol 1 - problém batohu]]
  * [[:school:fit:mipaa:ukol3|Úkol 3 - problému batohu 2: dynamické programování, metoda větví a hranic a aproximativní algoritmus ]]