Problém batohu 1

Úloha z předmětu 36PAA

Martin Tůma

Zadání

1. Naprogramujte řešení 0/1 problému batohu [1] hrubou silou [2]. Na zkušebních datech [4] pozorujte závislost výpočetního času na n.
2. Naprogramujte řešení 0/1 problému batohu heuristikou podle poměru cena/váha [3]. Pozorujte:
   • závislost výpočetního času na n. Grafy jsou vítány(i pro exaktní metodu).
   • průměrné zhoršení proti exaktní metodě
   • maximální relativní chybu. Absolutní chyba nic neříká!

Řešení

1. Řešení "hrubou silou"

Použitý algoritmus generuje všech 2ⁿ kombinací věcí umisťovaných do batohu a testuje obě podmínky (zda zvolená kombinace nepřetíží batoh a zda cenová funkce nabývá maxima). Složitost algoritmu je tedy O(2ⁿ).

2. Řešení heuristikou typu nejrychlejšího vzestupu

Věci jsou seřazeny podle daného kritéria (klesající poměr cena/hmotnost). Začíná se s věcí, která má toto kritérium nejlepší, a v každém kroku se do batohu vkládá věc s další nejlepší hodnotou, která se do batohu ještě vejde. Takto se pokračuje až do naplnění batohu. Složitost algoritmu je dána složitostí řazení, v případě použitého quicksortu je tedy O(n·log(n)).

Naměřené hodnoty

Měření probíhala v následujícím prostředí: PC s CPU Celeron M 1.47GHz, Linux 2.6.20, gcc 4.1.2. Naměřené časy u časových závislostí jsou udávány vždy pro celý vstupní soubor, tzn. 50 instancí problému.

Časové závislosti

n	4	10	15	20	22	25	27
t[s]	0.001	0.004	0.168	6.948	29.95	268.5	1158

Graf 1. Řešení "hrubou silou".

n	4	10	15	20	22	25	27	30	32	35	37	40
t[ms]	1.348	2.368	3.352	4.204	4.696	5.216	5.752	6.252	6.660	7.320	7.820	8.393

Graf 2. Řešení heuristikou typu nejrychlejšího vzestupu.

Relativní chyby heuristiky

Vstupní data	Průměrná relativní chyba	Maximální relativní chyba
knap_4.txt	0,021745	0,363636
knap_10.txt	0,012862	0,114801
knap_15.txt	0,004759	0,085427
knap_20.txt	0,006001	0,084337
knap_22.txt	0,006867	0,072289
knap_25.txt	0,004984	0,036789
knap_27.txt	0,005017	0,106017
knap_30.txt	0,005074	0,055138
knap_32.txt	0,003412	0,033408
knap_35.txt	0,002802	0,046092
knap_37.txt	0,003436	0,081967
knap_40.txt	0,001995	0,023372

Závěr

Řešení pomocí "hrubé síly" potvrdilo svojí výpočetní náročnost, pro n>27 již výpočet jediného řešení trvá řádově minuty. Naopak výpočet pomocí heuristiky typu nejrychlejšího vzestupu podle poměru cena/hmotnost je použitelný i pro řádově vyšší n. Relativní chyba oproti optimu se pro n>10 pohybuje v jednotkách procent a s rostoucím n klesá.

Reference

[1] http://service.felk.cvut.cz/courses/36PAA/knapsolv.html
[2] http://service.felk.cvut.cz/courses/36PAA/knapsolv.html#bruteforce
[3] http://service.felk.cvut.cz/courses/36PAA/knapsolv.html#greedy
[4] http://service.felk.cvut.cz/courses/36PAA/knapsolv.html#bench

Přílohy

1. batoh_brute.c - Program pro řešení problému hrubou silou.
2. batoh_h1.c - Program pro řešení problému pomocí heuristiky.
3. stats.sh - Script na výpočet relativních chyb heuristiky