1. Problém batohu metodou hrubé síly a jednoduchou heurestikou
Zadání:
- Naprogramujte řešení 0/1 problému batohu hrubou silou.
Na zkušebních datech pozorujte závislost výpočetního času na n.
- Naprogramujte řešení 0/1 problému batohu heuristikou podle poměru cena/váha. Pozorujte
- závislost výpočetního času na n
- průměrné zhoršení proti exaktní metodě
- maximální chybu.
Výsledkem bude krátká zpráva s naměřenými charakteristikami, doprovázená zdrojovými texty.
Měření nechť je orientační - doba chodu jednotlivých testů nemusí překračovat několik málo minut.
Rozsáhlejší experimenty jsou náplní pozdějších úloh.
Řešení - hrubou silou:
Projdeme všechny možnosti jak lze předměty do batohu vložit.
Těchto možností je 2^n kde n je počet předmětů, časová složitost je pak O(2^n).
Následující tabulka ukazuje naměřené hodnoty.
| n |
4 |
10 |
15 |
20 |
22 |
25 |
27 |
30 |
| t [s] |
0 |
0 |
0 |
0.8 |
3.6 |
34 |
248 |
- |
Čas uvedený v tabulce je průměrná hodnota z několika měření.
Měření pro 30 instancí nebylo dokončeno.
Hodnoty nejsou príliš přesné, protože během měření neměl program maximální prioritu, spíše naopak.
Přesto je z hodnot vidět, že bruteforce metoda vykazuje exponenciální složitost.
Řešení - jednoduchou heurestikou:
Naše heuristika je založena na setřídění předmětů podle poměru cena/váha sestupně.
Do batohu se pak snažíme vkládat prvky postupně z této posloupnosti.
Tato metoda nedává nejlepší řešení, ale výsledná kombinace předmětů se mu velice blíží.
Pro heurestiku jsme provedli měření pro všechny zadané instance (max n=40) s výslednými časy pod sekundu.
Nepřesnost heurestiky je znázorněna v tabulce, uvedené hodnoty jsou průměrem vždy pro 50 instancí a jsou spočteny podle vzorce:
ABS ( OTPIMALNI - HEURESTIKOU ) / OPTIMALNI * 100
| n |
relativní chyba [%] |
| 4 |
1,7954497 |
| 10 |
1,1925061 |
| 15 |
0,3619424 |
| 20 |
0,6016916 |
| 22 |
0,3632481 |
| 25 |
0,4647567 |
| 27 |
0,6017674 |
| 30 |
0,4670988 |
| 32 |
0,3829160 |
| 35 |
0,3948001 |
| 37 |
0,5077768 |
| 40 |
0,4171890 |
Závěr:
Z naměřených hodnot je vidět, že bruteforce je použitelný jen pro velmi málo instancí.
Heurestická analýza je naopak velice rychlá a přesto poměrně přesná.
Uvidíme jak ještě půjde heurestika vylepšit v dalších úlohách.
Přílohy:
zdrojový kód batoh.cpp
zakompresovaná data použitá v analýze data.zip