Tato stránka vyžaduje podporu CSS stylů

1. domácí úloha z předmětu PAA

Řešení problému batohu hrubou silou a jednoduchou heuristikou

Oto Válek

FEL ČVUT, letní semestr 2001/2002, cvičení St 12:45

1. Specifikace úlohy

Problém batohu je řešen hrubou silou a heuristikou podle poměru cena/váha. Byly použity připravené instance problému pro n = 4, 10, 15, 22, 25, 27, 30, 32, 35, 37, 40. Hrubou silou nebyl problém řešen pro n > 27 vzhledem k extrémní časové náročnosti.

Čas byl měřen funkcí ftime() ze std. C knihovny v prostředí WinNT. Byl použit kompilátor z MS VC 5.0 s defaultním nastavením a procesor AMD Athlon 1GHz.

2. Řešení hrubou silou

Algoritmus prochází v nejhorším případě všechny, tj. 2ⁿ možných konfigurací. Přestože přidávání předmětu bylo ukončeno při přetíženém batohu, odpovídala závislost naměřeného času na n poměrně přesně 2ⁿ. Podobně se chová i závislost maximální odchylhy od správného výsledku.

Tyto charakteristiky však silně závisí na volbě testovacích instancí (cen a vah předmětů a váhového limitu)

  n   t[ms]       2^n  t/2^n 
------------------------------
  4     0.0        16        
 10     0.6      1024  1706.6
 15    13.6     32768  2405.8
 20   425.2   1048576  2466.0
 22  1608.7   4194304  2607.2
 25 13193.6  33554432  2543.2
 27 55494.6 134217728  2418.6

3. Řešení jednoduchou heuristikou

Heuristika typu nejrychlejšího vzestupu v nejhorším případě přidá všechny věci, časová složitost je tedy O(n). Při použitých instancích malé velikosti byl čas výpočtu prakticky neměřitelný.

4. Závěr

Relativní odchylka (dif[%]) průměrné ceny nalezené heuristickým algoritmem od průměrné optimální ceny nalezené hrubou silou mírně klesá s rostoucím n. Z malého počtu vzorků nelze odhadnout přesný trend. Podobně se chová i maximální odchylka od správného výsledku (max[1]).

Tyto výsledky včk silně závisí na volbě testovacích instancí (cen a vah předmětů a váhového limitu)

  n   opt.    heur.  dif[1] dif[%] max[1]
-----------------------------------------
  4   353.0   332.9   20.1   7.194  163  
 10  1125.4  1092.2   33.2   2.932  199  
 15  1814.3  1798.8   15.5   0.796  133  
 20  2335.2  2305.7   29.5   1.265  181  
 22  2501.2  2465.7   35.6   1.431  221  
 25  2954.1  2916.8   37.3   1.256  147  
 27  3143.3  3114.5   28.8   0.907  128  
 30  3581.2  3547.1   34.1   0.959  132  
 32  3694.5  3670.2   24.4   0.688  131  
 35  4081.8  4044.5   37.3   0.949  138  
 37  4222.1  4196.2   25.9   0.605  103  
 40  4628.9  4600.0   28.9   0.619  120

5. Soubory

1batoh.zip - ZIP archiv zdrojových souborů v C++, zadaných a naměřených hodnot, tohoto dokumentu a Excel. tabulky s analýzou dat.