Úloha z předmětu 36PAA
Martin Tůma
Použitý algoritmus generuje všech 2n 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(2n).
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)).
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.
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.
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 |
Ř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á.
[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
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